STL源码解析之list(1)

与vector相比，list 的每个元素是一个独立的节点，包含前驱和后继指针。节点可在内存中任意位置，通过指针链接。

一、list与vector对比

• 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 1

3）插入操作

在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)、迭代器失效、大块连续内存）成为实际瓶颈。