STL源码解析之list(1)
与vector相比，list 的每个元素是一个独立的节点，包含前驱和后继指针。节点可在内存中任意位置，通过指针链接。
一、list与vector对比
| 操作 | vector | list |
|---|---|---|
随机访问（[i]） | O(1) – 极快 | O(n) – 需要遍历 |
| 头部插入/删除 | O(n) – 移动所有后续元素 | O(1) – 只改几个指针 |
| 尾部插入/删除 | O(1) – 摊销常数（可能触发扩容） | O(1) – 双向链表尾节点 |
| 中间插入/删除 | O(n) – 移动插入点后的元素 | O(1) – 前提是已找到位置（迭代器） |
| 查找给定值 | O(n) – 线性搜索 | O(n) – 线性搜索 |
| 排序 | 可用std::sort（O(n log n)） | 需用成员sort()（O(n log n)） |
| 内存开销 | 很低（仅存储元素，可能少量预留空间） | 高（每个节点额外存储两个指针） |
| 缓存友好性 | 极好（连续内存，预取） | 差（节点分散，缓存缺失多） |
vector插入元素可能引起重新分配，使所有迭代器、引用、指针失效。删除元素后，被删元素之后的迭代器失效。
list插入或删除节点，仅影响指向被操作节点的迭代器，其他迭代器始终有效。这是链表的重要优势。
二、源码解析
1）list节点定义
template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; void_pointer prev; T data;STL list是一个双向链表，next指向下一个节点，prev指向前一个节点
2）前向遍历与后向遍历
self& operator++() { node = (link_type)((*node).next); return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } self& operator--() { node = (link_type)((*node).prev); return *this; } self operator--(int) { self tmp = *this; --*this; return tmp; }std::list<int> lst = {1, 2, 3, 4, 5}; for (auto it = lst.begin(); it != lst.end(); ++it) { std::cout << *it << " "; } // 输出: 1 2 3 4 5 for (auto it = lst.rbegin(); it != lst.rend(); ++it) { std::cout << *it << " "; } // 输出: 5 4 3 2 13）插入操作
在postion处插入元素
iterator insert(iterator position, const T& x) { link_type tmp = create_node(x); // 調整雙向指標，使 tmp 安插進去。 tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->next = tmp; position.node->prev = tmp; return tmp; }在链表头部插入一个元素
void push_front(const T& x) { insert(begin(), x); }在链表尾部插入一个元素
void push_back(const T& x) { insert(end(), x); }4）删除操作
删除position处node
erase返回：指向被删元素之后的下一个有效元素的迭代器（若已无后续，返回end()）
iterator erase(iterator position) { link_type next_node = link_type(position.node->next); link_type prev_node = link_type(position.node->prev); prev_node->next = next_node; next_node->prev = prev_node; destroy_node(position.node); return iterator(next_node); }删除链表首部
void pop_front() { erase(begin()); }删除链表尾部
void pop_back() { iterator tmp = end(); erase(--tmp); }list插入/删除只修改指针，从不拷贝或移动元素本身。对比vector：当元素类型拷贝/移动成本高时（如包含大量数据的结构），vector的重新分配或插入/删除操作会付出高昂的元素移动代价。
list本身也有局限性，对比vector的主要代价
内存开销大：每个元素多存两个指针（prev/next），对于小对象内存浪费严重。
缓存不友好：节点在堆中分散，遍历时缓存命中率低，速度远慢于
vector。不支持随机访问：获取第 N 个元素需要 O(n) 遍历。
经验法则：默认使用
vector，除非你明确需要list的上述优点，并且vector的缺点（中间插入/删除 O(n)、迭代器失效、大块连续内存）成为实际瓶颈。