［转］小心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。

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。