list(链表)底层实现与迭代器失效分析
请说明std::list的底层数据结构(双向链表)、节点分配特点、迭代器类型,以及在插入、删除、splice等操作中迭代器的失效情况。
回答
孤独的心
底层结构:std::list是双向链表,每个节点包含prev/next指针和数据。
节点分配:每个节点单独动态分配(非连续内存),插入不会触发已有元素拷贝或移动。对缓存不友好。
迭代器类型:双向迭代器(Bidirectional Iterator),不支持随机访问(没有operator+/-),但支持++和--。
迭代器失效规则:
- 插入操作:不会使任何已有迭代器失效(包括被插入位置的迭代器)。
- 删除操作:只会使被删除元素的迭代器失效,其他迭代器仍然有效。
- splice操作(合并/移动节点):不会失效任何迭代器(被移动节点的原始迭代器仍然有效,指向同一节点)。
性能: | 操作 | 时间复杂度 | |------|-----------| | 任意位置插入/删除 | O(1)(已知迭代器位置) | | 查找 | O(n) | | 随机访问 | 不支持(需遍历) | | 排序 | O(n log n),但list::sort是归并排序 |
适用场景:需要频繁在中间插入/删除,且不需要随机访问。