STL中list非连续内存存储原因及迭代器++相关疑问

嘿，这个问题问到点子上了，我来给你拆解清楚两个核心点：

STL里的list本质是双向循环链表，它放弃连续内存是为了发挥链表的核心优势，主要原因有这几个：

• 插入/删除效率极高：如果用连续内存（比如vector那种），在中间位置插入或删除元素时，后面所有元素都得移动，时间复杂度是O(n)；而list只需要修改目标节点的前后指针，就能完成操作，时间复杂度是O(1)（前提是已经找到目标节点）。
• 无需处理扩容开销：连续内存容器（比如vector）满了之后，得重新分配一块更大的内存，把旧数据拷贝过去，这个过程不仅耗时，还可能产生内存碎片；list的每个节点都是单独分配内存的，用多少申请多少，完全不用操心扩容。
• 内存利用率更灵活：连续内存需要一块足够大的连续空闲内存块，要是内存里只有零散的小空间，就没法分配；而list可以把这些零散的内存块串起来用，对内存的适应性更强。
• 迭代器特性匹配：list的迭代器是双向迭代器，只能支持++/--操作，不支持随机访问（比如it+5这种），这和链表的结构完全匹配；如果用连续内存，那迭代器就会是随机访问迭代器，反而不符合list的设计定位。

这个观点完全错误，原因得从list迭代器的实现逻辑说起：
你看到的it++，并不是像vector那样直接把内存地址加上sizeof(T)，而是调用了list迭代器的operator++()方法。这个方法内部做的事情是：取出当前迭代器指向的链表节点的next指针，把迭代器指向这个next节点的地址。

举个直观的例子，你可以在遍历的时候打印每个元素的内存地址：

void printCollection(T coll){ 
    auto it=coll.begin(); 
    while(it != coll.end()) { 
        cout << *it << ' ' << &(*it) << endl; // 打印元素地址
        it++; 
    } 
    cout << endl; 
}

运行后你会发现，list元素的地址是完全不连续的，而如果是vector，地址会是连续递增的。

简单说：it++看起来是“移动到下一个元素”，但这个“移动”是通过链表节点的指针跳转实现的，和内存是否连续没有半毛钱关系～

内容的提问来源于stack exchange，提问作者Ahmed Elemam