学步园

问题:    
    有一个stl容器, 有一个已经获取到的容器的迭代器, 当向stl容器中新增元素或删除元素时, 先前拿到的迭代器还有用吗? 也就是迭代器是否失效了?
   
迭代器失效,有两个层面的意思,
    1) 无法通过迭代器++,--操作遍历整个stl容器. 记作: 第一层失效
    2) 无法通过迭代器存取迭代器所指向的内存. 记作: 第二层失效

关于这个问题, 不同的容器对应的结果是不同的. 我们分别分析.

vector
    vector是个连续内存存储的容器. 如果vector容器的中间某个元素被删除或从中间插入一个元素. 有可能导致内存空间不够用而重新分配一块大的内存.
    这个动作将导致先前获取的迭代器, 第一层和第二层均失效.

map
    map内部是红黑树结构, 当map中新插入或删除元素后, 树的结构会相应的调整.
    但是, 通过先前的迭代器, 仍然可以通过++可以遍历map. 能遍历到值>当前迭代器的节点. (没有看具体stl内部实现,初步代码验证正确)
    迭代器指向的用户数据内存始终有效.

list
   同理map, 通过++只能遍历链表右侧的节点. 迭代器指向的用户数据内存也始终有效.

后记:为什么会有这篇文章?
   是因为最近在做一个LRU cache系统, 希望利用stl提供的hash_map和list来实现, 中间涉及到迭代器的是否失效问题.

特别注意,

1) 这里的结论仅使用于单线程的stl编程. 如果是多线程的, 就不是简单的迭代器失效问题了, 直接core了. stl是非线程安全的. 
2) 这里讨论的先前获取的迭代器,一定是没有被erase的, 如果一旦erase, 那么迭代器肯定失效. 注意, erase其他迭代器不影响先前获取的迭代器.

map的测试代码:

#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <arpa/inet.h>
#include <sstream>
#include <vector>
#include <map>
#include <list>
#include <unistd.h> // for usleep

using namespace std;


#ifndef foreach
#define foreach(container,it) \
            for(typeof((container).begin()) it = (container).begin();it!=(container).end();++it)
#endif
int main()
{
    map<int , int> im;

    im[1] = 1;
    im[10] = 10;
    im[20] = 20;
    im[21] = 21;

    map<int, int>::iterator it;
    map<int, int>::iterator it1;
    map<int, int>::iterator it2;
    map<int, int>::iterator it3;

    it1 = im.find(1);
    it2 = im.find(10);
    it3 = im.find(20);

    //--------------------------------
    // 边遍历便插入测试
    //--------------------------------
    int i = 30;
    foreach(im,it)
    {
        printf("it->first:%d, it->second:%d\n", it->first, it->second);
        if (i<40)
        {
            im[++i] = i;
            im[-i] = -i;
        }
    }

    printf("-----------------\n");

    //--------------------------------
    // 遍历完成后,拿着以前的iterator测试
    //--------------------------------
    for(it=it3; it!=im.end(); ++it)
    {
        printf("it->first:%d, it->second:%d\n", it->first, it->second);
    }
    return 0;
}

输出:

it->first:1, it->second:1
it->first:10, it->second:10
it->first:20, it->second:20
it->first:21, it->second:21
it->first:31, it->second:31
it->first:32, it->second:32
it->first:33, it->second:33
it->first:34, it->second:34
it->first:35, it->second:35
it->first:36, it->second:36
it->first:37, it->second:37
it->first:38, it->second:38
it->first:39, it->second:39
it->first:40, it->second:40
-----------------
it->first:20, it->second:20
it->first:21, it->second:21
it->first:31, it->second:31
it->first:32, it->second:32
it->first:33, it->second:33
it->first:34, it->second:34
it->first:35, it->second:35
it->first:36, it->second:36
it->first:37, it->second:37
it->first:38, it->second:38
it->first:39, it->second:39
it->first:40, it->second:40