STL源码之list容器深入学习

上一篇总结了vector的相关内容，这一次我们接着容器的相关知识进行学习。list和vector是两个最常使用的容器，list较vector要复杂的多。但复杂的背后给我们带来的是使用上的便捷：

（1）每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。
（2）对于任何位置的元素插入或元素移除，list永远是常数时间。

1. list的节点node
   我们知道，list本身和list的节点是不同的结构，需要分开设计，下面是SGI STL list的节点(node)结构：
   
   C++

   template <class T> struct __list_node { typedef void* void_pointer; void_pointer prev; //类型为void*， 其实可设为__list_node<T>* void_pointer next; T data; };

   1 2 3 4 5 6 7

   template <class T> struct __list_node { typedef void* void_pointer; void_pointer prev; //类型为void*， 其实可设为__list_node<T>* void_pointer next; T data; };

   
   节点示意图如下：
2. list的迭代器
   介绍list迭代器源码之前，我们先来学习一下list迭代器的相关知识点：
   （1）list不能像vector一样以普通指针作为迭代器，因为其节点不保证在存储空间中连续存在。
   （2）list迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。
   （3）由于STL list是一个双向链表(double linked-list)，迭代器必须具备前移、后移的能力，所以list提供的是Bidirectional Iterator。
   （4）list还有一个重要的性质：插入操作(insert)和接合操作(splice)都不会造成原有的list迭代器失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效。
   （5）甚至list的元素删除操作(erase)，也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。知道上述性质之后，我们接着来学习list迭代器源码：
   
   C++

   template <class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node; //迭代器内部当然要有一个普通指针，指向list的节点 //constructor __list_iterator(link_type x) : node(x) { } __list_iterator() { } __list_iterator (const iterator& x) : node(x.node) { } bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } //以下对迭代器取值(reference)，取的是节点的数据值 reference operator*() const { return (*node).data; } //以下是迭代器的成员存取(member access)运算子的标准做法 pointer operator->() const { return &(operator*()); } //对迭代器累加1，就是前进一个节点 self& operator++() { node = (link_type) ((*node).next); return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } //对迭代器递减1，就是后退一个节点 self& operator--() { node = (lint_type)((*node).prev); return *this; } self& operator--(int) { self tmp = *this; --*this; return tmp; } }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

   template <class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; typedef __list_iterator<T, Ref, Ptr> self; typedef bidirectional_iterator_tag iterator_category; typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef __list_node<T>* link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; link_type node; //迭代器内部当然要有一个普通指针，指向list的节点 //constructor __list_iterator(link_type x) : node(x) { } __list_iterator() { } __list_iterator (const iterator& x) : node(x.node) { } bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } //以下对迭代器取值(reference)，取的是节点的数据值 reference operator*() const { return (*node).data; } //以下是迭代器的成员存取(member access)运算子的标准做法 pointer operator->() const { return &(operator*()); } //对迭代器累加1，就是前进一个节点 self& operator++() { node = (link_type) ((*node).next); return *this; } self operator++(int) { self tmp = *this; ++*this; return tmp; } //对迭代器递减1，就是后退一个节点 self& operator--() { node = (lint_type)((*node).prev); return *this; } self& operator--(int) { self tmp = *this; --*this; return tmp; } }

3. list的数据结构
   （1）SGI STL不仅是一个双向链表，而且还是一个环状双向链表。所以它只需要一个指针，便可以完整表现整个链表：
   
   C++

   template <class T, class Alloc = alloc> //缺省使用alloc为配置器 class list { protected: typedef __list_node<T> list_node; public: typedef list_node* link_type; protected: link_type node; //只要一个指针，便可表示整个环状双向链表 ... }

   1 2 3 4 5 6 7 8 9 10 11

   template <class T, class Alloc = alloc> //缺省使用alloc为配置器 class list { protected: typedef __list_node<T> list_node; public: typedef list_node* link_type; protected: link_type node; //只要一个指针，便可表示整个环状双向链表 ... }

   
   （2）如果让指针node指向刻意置于尾端的一个空白节点，node便能符合STL对于“前闭后开”区间的要求，称为last迭代器，如图：有了这个设计，那么下面几个函数就好实现了：
   
   C++

   iterator begin() { return (link_type)((*node).next); } iterator end() { return node; } bool empty() const { return node->next == node; } size_type size() const { size_type result = 0; distance(begin(), end(), result); //全局函数 return result; } //取头节点的内容（元素值） reference front() { return *begin(); } //取尾节点的内容(元素值) reference back() { return *(--end()); }

   1 2 3 4 5 6 7 8 9 10 11 12

   iterator begin() { return (link_type)((*node).next); } iterator end() { return node; } bool empty() const { return node->next == node; } size_type size() const { size_type result = 0; distance(begin(), end(), result); //全局函数 return result; } //取头节点的内容（元素值） reference front() { return *begin(); } //取尾节点的内容(元素值) reference back() { return *(--end()); }

4. list的构造与内存管理：constructor, push_back, insert
   （1）list缺省使用alloc作为空间配置器，并据此另外定义一个list_node_allocator（类似于vector中的data_allacator的作用），为的是更方便以节点大小为配置单位。
   （2）不管是list_node_allocator还是data_allocator，其本质都是simple_alloc接口。
   
   C++

   template <class T, class Alloc = alloc> //缺省使用alloc为配置器 class list { protected: typedef __list_node<T> list_node; //专属之空间配置器，每次配置一个节点大小 typedef simple_alloc<list_node, Alloc> list_node_allocator; ... };

   1 2 3 4 5 6 7 8

   template <class T, class Alloc = alloc> //缺省使用alloc为配置器 class list { protected: typedef __list_node<T> list_node; //专属之空间配置器，每次配置一个节点大小 typedef simple_alloc<list_node, Alloc> list_node_allocator; ... };

   
   （3）于是，list_node_allocator(n)表示配置n个节点空间。以下四个函数分别用来配置、释放、构造、销毁一个节点：
   
   C++

   protected: //配置一个节点并传回 link_type get_node() { return list_node_allocator::allocate(); } //释放一个节点 void put_node(link_type p) { list_node_allocator::deallocate(p); } //产生（配置并构造）一个节点，带有元素值 link_type create_node(const T& x) { link_type p = get_node(); construct(&p->data, x); //全局函数，构造/析构基本工具 return p; } //销毁（析构并释放）一个节点 void destroy_node(lint_type p) { destroy(&p->data); //全局函数，构造/析构基本工具 put_node(p); //等价于list_node_allocator::deallocate(p); }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   protected: //配置一个节点并传回 link_type get_node() { return list_node_allocator::allocate(); } //释放一个节点 void put_node(link_type p) { list_node_allocator::deallocate(p); } //产生（配置并构造）一个节点，带有元素值 link_type create_node(const T& x) { link_type p = get_node(); construct(&p->data, x); //全局函数，构造/析构基本工具 return p; } //销毁（析构并释放）一个节点 void destroy_node(lint_type p) { destroy(&p->data); //全局函数，构造/析构基本工具 put_node(p); //等价于list_node_allocator::deallocate(p); }

   
   （4）list提供有许多constructor，其中一个是default constructor，允许我们不指定任何参数做出一个空的list：
   
   C++

   public: list() { empty_initialize(); } //产生一个空链表 protected: void empty_initialize() { node = get_node(); //配置一个节点空间，令node指向它 node->next = node; //令node头尾都指向自己，不设元素值 node->prev = node; }

   1 2 3 4 5 6 7 8 9

   public: list() { empty_initialize(); } //产生一个空链表 protected: void empty_initialize() { node = get_node(); //配置一个节点空间，令node指向它 node->next = node; //令node头尾都指向自己，不设元素值 node->prev = node; }

   
   如图所示空链表的结构：

   （5）当我们以push_back()将新元素插入与list尾端时，此函数内部调用insert():
   void push_back(const T& x) { insert(end(), x); }
   insert()是一个重载函数，有多重形式，其中最简单的一种如下，首先配置并构造一个节点，然后在尾端进行适当的指针操作，将新节点插入进去：

   C++

   //函数目的:在迭代器position所指位置插入一个节点内容为x iterator insert(iterator position, const T& x) { link_type tmp = create_node(x); //产生一个节点（设其内容为x） //调整双向指针，是tmp插进去（画一个链表会很直观） tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->next = tmp; position.node->prev = tmp; return tmp; }

   1 2 3 4 5 6 7 8 9 10

   //函数目的:在迭代器position所指位置插入一个节点内容为x iterator insert(iterator position, const T& x) { link_type tmp = create_node(x); //产生一个节点（设其内容为x） //调整双向指针，是tmp插进去（画一个链表会很直观） tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->next = tmp; position.node->prev = tmp; return tmp; }

   （6）注意，插入完成后，新节点将位于哨兵迭代器(标示出插入点)所指的节点的前方——这是STL对于“插入操作”的标准规范。
   （7）由于list不像vector那样有可能在空间不足时重新配置、数据移动的操作，所以插入前的所有迭代器在插入操作之后都仍然有效。

5. list的元素操作：push_front, push_back, erase, pop_front, pop_back, clear, remove, unique, splice, merge, reverse, sort
   （1）list所提供的元素操作很多，这里只挑其中几个讲解，源码如下：
   C++

   //插入一个节点，作为头节点 void push_front(const T& x) { insert(begin(), x); } //插入一个节点，作为尾节点 void push_back(const T& x) { insert(end(), x); } //移除迭代器position所指节点 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); } //清除所有节点(整个链表) template <class T, class Alloc> void list<T, Alloc>::clear() { link_type cur = (link_type) node->next; //begin() while (cur != node) { //遍历每一个节点 link_type tmp = cur; cur = (link_type) cur->next; destroy_node(tmp); //销毁（析构并释放）一个节点 } //恢复node原始状态 node->next = node; node->prev = node; } //将数值为value的所有元素移除 template <class T, class Alloc> void list<T,Alloc>::remove(const T& value) { iterator first = begin(); iterator last = end(); while(first != last) { //遍历每一个节点 iterator next = first; ++next; if(*first == value ) erase(first); //找到就移除 first = next; } } //移除数值相同的连续元素。注意，只有“连续而相同的元素”，才会被移除剩一个 template <class T, class Alloc> void list<T, Alloc>::unique() { iterator first = begin(); iterator last = end(); if (first == last) return; //空链表，什么都不必做 iterator next = first; while(++next != last) { //遍历每一个节点 if(*first == *next) //如果在此区段中有相同的元素 erase(next); //移除之 else first = next; //调整指针 next = first; //修正区段范围 } }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

   //插入一个节点，作为头节点 void push_front(const T& x) { insert(begin(), x); } //插入一个节点，作为尾节点 void push_back(const T& x) { insert(end(), x); }   //移除迭代器position所指节点 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); }   //清除所有节点(整个链表) template <class T, class Alloc> void list<T, Alloc>::clear() { link_type cur = (link_type) node->next; //begin() while (cur != node) { //遍历每一个节点 link_type tmp = cur; cur = (link_type) cur->next; destroy_node(tmp); //销毁（析构并释放）一个节点 } //恢复node原始状态 node->next = node; node->prev = node; }   //将数值为value的所有元素移除 template <class T, class Alloc> void list<T,Alloc>::remove(const T& value) { iterator first = begin(); iterator last = end(); while(first != last) { //遍历每一个节点 iterator next = first; ++next; if(*first == value ) erase(first); //找到就移除 first = next; } }   //移除数值相同的连续元素。注意，只有“连续而相同的元素”，才会被移除剩一个 template <class T, class Alloc> void list<T, Alloc>::unique() { iterator first = begin(); iterator last = end(); if (first == last) return; //空链表，什么都不必做 iterator next = first; while(++next != last) { //遍历每一个节点 if(*first == *next) //如果在此区段中有相同的元素 erase(next); //移除之 else first = next; //调整指针 next = first; //修正区段范围 } }

   （2）list内部提供一个所谓的迁移操作（transfer）：将某连续范围的元素迁移到某个特定位置之前。这个操作为其他的复杂操作如splice, sort, merge奠定了良好的基础。下面是transfer源码：

   C++

   protected: //将[first, last)内所有元素移动到position之前 void transfer(iterator position, iterator first, iterator last) { if (position != last) { (*(link_type((*last.node).prev))).next = position.node; (*(link_type((*first.node).prev))).next = last.node; (*(link_type((*position.node).prev))).next = first.node; link_type tmp = link_type((*position.node).prev); (*last.node).prev = (*first.node).prev; (*first.node).node = tmp; } }

   1 2 3 4 5 6 7 8 9 10 11 12

   protected: //将[first, last)内所有元素移动到position之前 void transfer(iterator position, iterator first, iterator last) { if (position != last) { (*(link_type((*last.node).prev))).next = position.node; (*(link_type((*first.node).prev))).next = last.node; (*(link_type((*position.node).prev))).next = first.node; link_type tmp = link_type((*position.node).prev); (*last.node).prev = (*first.node).prev; (*first.node).node = tmp; } }

   上面的代码，看起来是一头雾水，建议大家自己在纸上画出一个链表，会容易理解。并且这个transfer并非公开接口。list公开提供的是splice操作（就是对transfer的一个封装）
   （3）下面再列出几个splice版本：

   C++

   public: //将x接合于position所指位置之前，x必须不同于*this void splice(iterator position, list& x) { if (!x.empty()) transfer(position, x.begin(), x.end()); } //将i所指元素接合于position所指位置之前，position和i可指向同一个list void aplice(iterator position, list&, iterator i) { iterator j = i; ++j; if (position == i || position == j) return; transfer(position, i, j); } //将[first, last)内所有元素接合于position所指位置之前 //position和[first, last)可指向同一个list， //但position不能位于[first, last)之内 void splice(iterator position, list&, iterator first, iterator last) { if (first != last) transfer(position, first, last); }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

   public: //将x接合于position所指位置之前，x必须不同于*this void splice(iterator position, list& x) { if (!x.empty()) transfer(position, x.begin(), x.end()); }   //将i所指元素接合于position所指位置之前，position和i可指向同一个list void aplice(iterator position, list&, iterator i) { iterator j = i; ++j; if (position == i || position == j) return; transfer(position, i, j); }   //将[first, last)内所有元素接合于position所指位置之前 //position和[first, last)可指向同一个list， //但position不能位于[first, last)之内 void splice(iterator position, list&, iterator first, iterator last) { if (first != last) transfer(position, first, last); }

   （4）有了transfer()，那么merge(), reverse(), sort()就容易实现多了：

   C++

   //merge()将x合并到*this身上， 两个lists的内容都必须先经过递增排序 template <class T, class Alloc> void list<T, Alloc>::merge(list<T, Alloc>& x) { iterator first1 = begin(); iterator last1 = end(); iterator first2 = x.begin(); iterator last2 = x.end(); //注意：前提是，两个lists都已经递增排序 while (first1 != last1 && first2 != last2) if (*first2 < *first1) { iterator next = first2; transfer(first1, first2, ++next); first2 = next; } else ++first1; if (first2 != last2) transfer(last1, first2, last2); } //reverse()将*this的内容逆向重置 template <class T, class Alloc> void list<T, Alloc>::reverse() { //以下判断，如果是空链表，或仅有一个元素，就不进行任何操作 //使用size() == 0 || size() == 1来判断虽然也可以，但是比较慢 if(node->next == node || link_type(node->next)->next == node) return; iterator first = begin(); ++first; while(first != end()) { iterator old = first; ++first; transfer(begin(), old, first); } }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

   //merge()将x合并到*this身上， 两个lists的内容都必须先经过递增排序 template <class T, class Alloc> void list<T, Alloc>::merge(list<T, Alloc>& x) { iterator first1 = begin(); iterator last1 = end(); iterator first2 = x.begin(); iterator last2 = x.end(); //注意：前提是，两个lists都已经递增排序 while (first1 != last1 && first2 != last2) if (*first2 < *first1) { iterator next = first2; transfer(first1, first2, ++next); first2 = next; } else ++first1; if (first2 != last2) transfer(last1, first2, last2); }   //reverse()将*this的内容逆向重置 template <class T, class Alloc> void list<T, Alloc>::reverse() { //以下判断，如果是空链表，或仅有一个元素，就不进行任何操作 //使用size() == 0 || size() == 1来判断虽然也可以，但是比较慢 if(node->next == node || link_type(node->next)->next == node) return; iterator first = begin(); ++first; while(first != end()) { iterator old = first; ++first; transfer(begin(), old, first); } }

   list不能使用STL算法sort()， 必须使用自己的sort() member function， 因为STL算法sort()只接受RandomAccessIterator。本函数采用quick sort()。

   C++

   template <class T, class Alloc> void list<T, Alloc>::sort() { //以下判断，如果是空链表，或仅有一个元素，就不进行任何操作 //使用size() == 0 || size() == 1来判断虽然也可以，但是比较慢 if(node->next == node || link_type(node->next)->next == node) return; //一些新的lists，作为中介数据存放区 list<T, Alloc> carry; list<T, Alloc> counter[64]; int fill = 0; while (!empty()) { carry.splice(carry.begin(), *this, begin()); int i = 0; while (i < fill && !counter[i].empty()) { counter[i].merge(carry); carry.swap(counter[i++]); } carry.swab(couter[i]); if (i == fill) ++fill; } for (int i = 1; i < fill; ++i) couter[i].merge(couter[i-1]); swap(couter[fill-1]); }

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

   template <class T, class Alloc> void list<T, Alloc>::sort() { //以下判断，如果是空链表，或仅有一个元素，就不进行任何操作 //使用size() == 0 || size() == 1来判断虽然也可以，但是比较慢 if(node->next == node || link_type(node->next)->next == node) return; //一些新的lists，作为中介数据存放区 list<T, Alloc> carry; list<T, Alloc> counter[64]; int fill = 0; while (!empty()) { carry.splice(carry.begin(), *this, begin()); int i = 0; while (i < fill && !counter[i].empty()) { counter[i].merge(carry); carry.swap(counter[i++]); } carry.swab(couter[i]); if (i == fill) ++fill; } for (int i = 1; i < fill; ++i) couter[i].merge(couter[i-1]); swap(couter[fill-1]); }

    

   参考：STL源码剖析