［转］小心deque，vector等序列容器的iterator失效 - saturnman的日志 - 网易博客

［转］小心deque，vector等序列容器的iterator失效

c++学习笔记 2010-02-04 00:22:37 阅读204 评论0   字号：大中小 订阅

先看一段关于deque的代码

view plaincopy to clipboardprint?
class A  
{  
public:  
    char m [64];  
};  
int main()  
{  
    A dv;  
    deque<A, alloc> a(33, dv);  
    deque<A, alloc>::iterator iter = a.begin()+10;  
    memset(iter->m, 0, sizeof(iter->m));  
    strcpy(iter->m, "hello world!");  
    for(int i = 0; i<15;i++)  
    a.push_back(dv);  
    printf("%s\n", iter->m);  
    deque<A, alloc>::iterator iter1 = a.begin()+10;  
    printf("%s\n", iter1->m);  
    return 1;  
} 
class A
{
public:
    char m [64];
};
int main()
{
    A dv;
    deque<A, alloc> a(33, dv);
    deque<A, alloc>::iterator iter = a.begin()+10;
    memset(iter->m, 0, sizeof(iter->m));
    strcpy(iter->m, "hello world!");
    for(int i = 0; i<15;i++)
    a.push_back(dv);
    printf("%s\n", iter->m);
    deque<A, alloc>::iterator iter1 = a.begin()+10;
    printf("%s\n", iter1->m);
    return 1;
}
 

虽然输出了两行hello world!,但结果的确是错误的，因为第一个hello world!是用未清理的内存输出的

这是为什么呢？

deque是一个双向队列，表面上来看是使用了连续的存储空间，比如支持下标操作，RandomIterator等，实际上deque的内存是由若 干块内存块组成的，每一个内存块都容纳了若干个我们要放入的元素，所以在deque里要记录我一共使用了几块内存块，他们都在哪里，我们称之为 map，map也是有数量限制的。迭代子为了支持+n操作，也会保存自己元素所属内存块地址的指针，当然也会想办法知道上一块和下一块的指针实际上是通 过+1,-1这样的操作就可以达到。当插入一个元素时，deque要考虑当前的若干内存块是否满，如果满则开辟新的内存块，并把内存块的地址记录到 deque的map信息中。前边提到map的数量有限制，如果map超过数量怎么办呢？类似vector做法，开辟一个新map，把旧map的内容(各个 内存块的地址)拷贝过去。然后释放旧map的内存。就是这一步操作，导致了iterator失效。因为iterator里保存的是旧map的地址，根据旧 地址的得到的内存块的地址也是错误的。自然得到的值也是错误的。那为什么上面的例子没错呢？每一内存虽然释放，但内容没变，还是和新map内容一样，都指 向了存储内存块的地址。所以仍可以得到hello world。