STL源码解析之list(1)

与vector相比list 的每个元素是一个独立的节点包含前驱和后继指针。节点可在内存中任意位置通过指针链接。一、list与vector对比操作vectorlist随机访问[i]O(1) – 极快O(n) – 需要遍历头部插入/删除O(n) – 移动所有后续元素O(1) – 只改几个指针尾部插入/删除O(1) – 摊销常数可能触发扩容O(1) – 双向链表尾节点中间插入/删除O(n) – 移动插入点后的元素O(1) – 前提是已找到位置迭代器查找给定值O(n) – 线性搜索O(n) – 线性搜索排序可用std::sortO(n log n)需用成员sort()O(n log n)内存开销很低仅存储元素可能少量预留空间高每个节点额外存储两个指针缓存友好性极好连续内存预取差节点分散缓存缺失多vector插入元素可能引起重新分配使所有迭代器、引用、指针失效。删除元素后被删元素之后的迭代器失效。list插入或删除节点仅影响指向被操作节点的迭代器其他迭代器始终有效。这是链表的重要优势。二、源码解析1list节点定义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::listint 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处nodeerase返回指向被删元素之后的下一个有效元素的迭代器若已无后续返回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)、迭代器失效、大块连续内存成为实际瓶颈。