迭代器的失效问题：对容器的操作影响了元素的存放位置，称为迭代器失效。迭代器失效的情况：
当容器调用erase()方法后，当前位置到容器末尾元素的所有迭代器全部失效。
当容器调用insert()方法后，当前位置到容器末尾元素的所有迭代器全部失效。
如果容器扩容，在其他地方重新又开辟了一块内存。原来容器底层的内存上所保存的迭代器全都失效。
迭代器失效
迭代器失效有三种情况，由于底层的存储数据结构，分三种情况
序列式迭代器失效。
序列式容器(std::vector和std::deque)，其对应的数据结构分配在连续的内存中，对其中的迭代器进行insert和erase操作都会使得删除点和插入点之后的元素挪位置，进而导致插入点和删除掉之后的迭代器全部失效。可以利用erase迭代器接口返回的是下一个有效的迭代器。
链表性迭代器失效。
链表型数据结构(std::list)使用链表进行数据存储，插入或者删除只会对当前的节点造成影响，不会影响其他的迭代器。可以利用erase迭代器接口返回的是下一个有效的迭代器，或者将当前的迭代器指向下一个erase(iter++)。
树形迭代器失效。
树形数据结构，如map, set,multimap,multiset等，使用红黑树进行数据存储，删除当前的迭代器，仅仅会使当前的迭代器失效。erase迭代器的返回值为 void，可以采用erase(iter++)的方式进行删除。
在实现上有两种模板，其一是通过 erase 获得下一个有效的 iterator，使用于序列式迭代器和链表式迭代器
// for (iter = cont.begin(); iter != cont.end();) { (*it)->doSomething(); if (shouldDelete(*iter)) iter = cont.erase(iter); //erase删除元素，返回下一个迭代器 else ++iter;}
复制代码
其二是，递增当前迭代器，适用于链表式迭代器和树形迭代器。
// 递增当前迭代器for (iter = cont.begin(); it != cont.end();) { (*iter)->doSomething(); if (shouldDelete(*iter)) cont.erase(iter++); else iter++;}
复制代码
下面按照分类对迭代器失效进行一些代码示例的展示。
序列迭代器
对于std::vector和std::deque,删除迭代器会导致删除点之后的所有迭代器失效。可以利用erase接口返回的是下一个有效的迭代器的信息进行处理。
/** * @brief: 序列迭代器失效处理 * 将erase返回的下一个有效的迭代器赋值给iter，来避免迭代器失效 * * 操作示例：将数据是偶数的迭代器删除*/void vector_iter_erase() { std::vector<int> vect {0, 1, 2, 3, 4, 5}; for (auto iter = vect.begin(); iter != vect.end();) { if (*iter & 1) { //
iter = vect.erase(iter); } else { iter++; } }
// 展示所有的有效数据 std::cout << "The vector item's "; for (auto iter = vect.begin(); iter != vect.end(); iter++) { std::cout << *iter << " "; } std::cout << std::endl;}
复制代码
链表迭代器
链表型数据结构(std::list)插入或者删除只会对当前的节点造成影响，不会影响其他的迭代器。可以利用erase迭代器接口返回的是下一个有效的迭代器，或者递增迭代器erase(iter++)。
/** * @brief: 链表迭代器失效处理，有两种方式： * 1. 将erase返回的下一个有效的迭代器赋值给iter，来避免迭代器失效 * 2. 将当前的迭代器iter++,指向下一个有效迭代器 * * 操作示例：将数据是偶数的迭代器删除*/void list_iter_erase() { std::list<int> lst {0, 1, 2, 3, 4, 5};#if 0 for (auto iter = lst.begin(); iter != lst.end();) { if (*iter & 1) { lst.erase(iter++); } else { iter++; } }#else for (auto iter = lst.begin(); iter != lst.end();) { if (*iter & 1) { iter = lst.erase(iter); } else { iter++; } }#endif
// 展示所有有效数据 std::cout << "The list item's "; for (auto iter = lst.begin(); iter != lst.end(); iter++) { std::cout << *iter << " "; } std::cout << std::endl;}
复制代码
树形迭代器
树形数据结构，如map, set,multimap,multiset等，删除当前的迭代器，仅仅会使当前的迭代器失效。erase迭代器的返回值为 void，可以采用erase(iter++)的方式进行删除。
/** * @brief: 树形迭代器失效处理，erase接口返回值时void * 指向下一个有效迭代器来避免迭代器失效 * * 操作示例：将数据是key是奇数的迭代器删除*/void map_iter_erase() { std::unordered_map<int, int> umap { {0, 1}, {1, 6}, {2, 6}, {3, 6}, {4, 8}, {5, 8} }; for (auto iter = umap.begin(); iter != umap.end();) { if (iter->first & 1) { umap.erase(iter++); } else { iter++; } }
std::cout << "The unordered_map item's " << std::endl; for (auto iter = umap.begin(); iter != umap.end(); iter++) { std::cout << "\t" << iter->first << " : " << iter->second << std::endl; } std::cout << std::endl;}
复制代码
参考资料
【C++ STL】迭代器失效的几种情况总结
评论