写点什么

CPP 进阶: 迭代器失效

作者:正向成长
  • 2022 年 3 月 28 日
  • 本文字数:2185 字

    阅读完需:约 7 分钟

迭代器的失效问题:对容器的操作影响了元素的存放位置,称为迭代器失效。迭代器失效的情况:

  • 当容器调用erase()方法后,当前位置到容器末尾元素的所有迭代器全部失效。

  • 当容器调用insert()方法后,当前位置到容器末尾元素的所有迭代器全部失效。

  • 如果容器扩容,在其他地方重新又开辟了一块内存。原来容器底层的内存上所保存的迭代器全都失效。

迭代器失效

迭代器失效有三种情况,由于底层的存储数据结构,分三种情况

  1. 序列式迭代器失效。

序列式容器(std::vectorstd::deque),其对应的数据结构分配在连续的内存中,对其中的迭代器进行inserterase操作都会使得删除点和插入点之后的元素挪位置,进而导致插入点和删除掉之后的迭代器全部失效。可以利用erase迭代器接口返回的是下一个有效的迭代器。

  1. 链表性迭代器失效。

链表型数据结构(std::list)使用链表进行数据存储,插入或者删除只会对当前的节点造成影响,不会影响其他的迭代器。可以利用erase迭代器接口返回的是下一个有效的迭代器,或者将当前的迭代器指向下一个erase(iter++)

  1. 树形迭代器失效。

树形数据结构,如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::vectorstd::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;}
复制代码


参考资料

  1. 【C++ STL】迭代器失效的几种情况总结

发布于: 刚刚阅读数: 3
用户头像

正向成长

关注

正向成长 2018.08.06 加入

想要坚定地做大规模数据处理(流数据方向),希望结合结合批处理的传统处理方式,以及之后流批混合处理方向进行学习和记录。

评论

发布
暂无评论
CPP进阶:迭代器失效_迭代器失效_正向成长_InfoQ写作平台