首页 > 代码库 > STL源码分析--list

STL源码分析--list

2024-07-19 21:22:08   219人阅读

相较于vector的连续线性空间，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。
      list不仅是一个双向链表，而且还是一个环状双向链表。另外，还有一个重要性质，插入操作和接合操作都不会造成原有的list迭代器失效，这在vector是不成立的。因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效。甚至list的元素删除操作（erase），也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。
以下是list的节点、迭代器数据结构设计以及list的源码剖析：
[cpp] view plaincopy
  1. ////////////////////////////////////////////////////////////////////////////////  
  2. // list结点, 提供双向访问能力  
  3. ////////////////////////////////////////////////////////////////////////////////  
  4. //  --------           --------           --------           --------  
  5. //  | next |---------->| next |---------->| next |---------->| next |  
  6. //  --------           --------           --------           --------  
  7. //  | prev |<----------| prev |<----------| prev |<----------| prev |  
  8. //  --------           --------           --------           --------  
  9. //  | data |           | data |           | data |           | data |  
  10. //  --------           --------           --------           --------  
  11. ////////////////////////////////////////////////////////////////////////////////  
  12.   
  13. template <class T>  
  14. struct __list_node  
  15. {  
  16.     typedef void* void_pointer;  
  17.     void_pointer next;  
  18.     void_pointer prev;  
  19.     T data;  
  20. };  
  21.   
  22. // 至于为什么不使用默认参数, 这个是因为有一些编译器不能提供推导能力,  
  23. // 而作者又不想维护两份代码, 故不使用默认参数  
  24. template<class T, class Ref, class Ptr>  
  25. struct __list_iterator  
  26. {  
  27.     typedef __list_iterator<T, T&, T*>             iterator;   // STL标准强制要求  
  28.     typedef __list_iterator<T, Ref, Ptr>           self;  
  29.   
  30.     typedef bidirectional_iterator_tag iterator_category;  
  31.     typedef T value_type;  
  32.     typedef Ptr pointer;  
  33.     typedef Ref reference;  
  34.     typedef __list_node<T>* link_type;  
  35.     typedef size_t size_type;  
  36.     typedef ptrdiff_t difference_type;  
  37.   
  38.     link_type node;   //迭代器内部当然要有一个普通指针，指向list的节点  
  39.   
  40.     __list_iterator(link_type x) : node(x) {}  
  41.     __list_iterator() {}  
  42.     __list_iterator(const iterator& x) : node(x.node) {}  
  43.   
  44.     // 在STL算法中需要迭代器提供支持  
  45.     bool operator==(const self& x) const { return node == x.node; }  
  46.     bool operator!=(const self& x) const { return node != x.node; }  
  47.   
  48.     // 以下对迭代器取值（dereference）,取的是节点的数据值  
  49.     reference operator*() const { return (*node).data; }  
  50.   
  51.     // 以下是迭代器的成员存取运算子的标准做法  
  52.     pointer operator->() const { return &(operator*()); }  
  53.   
  54.     // 前缀自加，对迭代器累加1，就是前进一个节点  
  55.     self& operator++()  
  56.     {  
  57.         node = (link_type)((*node).next);  
  58.         return *this;  
  59.     }  
  60.   
  61.     // 后缀自加, 需要先产生自身的一个副本, 然会再对自身操作, 最后返回副本  
  62.     self operator++(int)  
  63.     {  
  64.         self tmp = *this;  
  65.         ++*this;  
  66.         return tmp;  
  67.     }  
  68.   
  69.     // 前缀自减  
  70.     self& operator--()  
  71.     {  
  72.         node = (link_type)((*node).prev);  
  73.         return *this;  
  74.     }  
  75.   
  76.     self operator--(int)  
  77.     {  
  78.         self tmp = *this;  
  79.         --*this;  
  80.         return tmp;  
  81.     }  
  82. };  
  83.   
  84. ////////////////////////////////////////////////////////////////////////////////  
  85. // list不仅是个双向链表, 而且还是一个环状双向链表  
  86. ////////////////////////////////////////////////////////////////////////////////  
  87. //       end()              头结点             begin()  
  88. //         ↓                  ↓                  ↓  
  89. //      --------           --------           --------           --------  
  90. // ---->| next |---------->| next |---------->| next |---------->| next |------  
  91. // |    --------           --------           --------           --------     |  
  92. // |  --| prev |<----------| prev |<----------| prev |<----------| prev |<--| |  
  93. // |  | --------           --------           --------           --------   | |  
  94. // |  | | data |           | data |           | data |           | data |   | |  
  95. // |  | --------           --------           --------           --------   | |  
  96. // |  |                                                                     | |  
  97. // |  | --------           --------           --------           --------   | |  
  98. // ---|-| next |<----------| next |<----------| next |<----------| next |<--|--  
  99. //    | --------           --------           --------           --------   |  
  100. //    ->| prev |---------->| prev |---------->| prev |---------->| prev |----  
  101. //      --------           --------           --------           --------  
  102. //      | data |           | data |           | data |           | data |  
  103. //      --------           --------           --------           --------  
  104. ////////////////////////////////////////////////////////////////////////////////  
  105.   
  106. // 默认allocator为alloc, 其具体使用版本请参照<stl_alloc.h>  
  107. template <class T, class Alloc = alloc>  
  108. class list  
  109. {  
  110. protected:  
  111.     typedef void* void_pointer;  
  112.     typedef __list_node<T> list_node;  
  113.   
  114.     // 专属之空间配置器，每次配置一个节点大小  
  115.     typedef simple_alloc<list_node, Alloc> list_node_allocator;  
  116.   
  117. public:  
  118.     typedef T value_type;  
  119.     typedef value_type* pointer;  
  120.     typedef value_type& reference;  
  121.     typedef list_node* link_type;  
  122.     typedef size_t size_type;  
  123.     typedef ptrdiff_t difference_type;  
  124.   
  125.     typedef __list_iterator<T, T&, T*>             iterator;  
  126.   
  127. protected:  
  128.     link_type node ;     // 只要一个指针，便可表示整个环状双向链表  
  129.     // 分配一个新结点, 注意这里并不进行构造,  
  130.     // 构造交给全局的construct, 见<stl_stl_uninitialized.h>  
  131.     link_type get_node() { return list_node_allocator::allocate(); }  
  132.   
  133.     // 释放指定结点, 不进行析构, 析构交给全局的destroy  
  134.     void put_node(link_type p) { list_node_allocator::deallocate(p); }  
  135.   
  136.     // 产生（配置并构造）一个节点, 首先分配内存, 然后进行构造  
  137.     // 注: commit or rollback  
  138.     link_type create_node(const T& x)  
  139.     {  
  140.         link_type p = get_node();  
  141.         construct(&p->data, x);  
  142.         return p;  
  143.     }  
  144.   
  145.     // 析构结点元素, 并释放内存  
  146.     void destroy_node(link_type p)  
  147.     {  
  148.         destroy(&p->data);  
  149.         put_node(p);  
  150.     }  
  151.   
  152. protected:  
  153.     // 用于空链表的建立  
  154.     void empty_initialize()  
  155.     {  
  156.         node = get_node();   // 配置一个节点空间，令node指向它  
  157.         node->next = node;   // 令node头尾都指向自己，不设元素值  
  158.         node->prev = node;  
  159.     }  
  160.   
  161.   // 创建值为value共n个结点的链表  
  162.   // 注: commit or rollback  
  163.     void fill_initialize(size_type n, const T& value)  
  164.     {  
  165.         empty_initialize();  
  166.         __STL_TRY  
  167.         {  
  168.             // 此处插入操作时间复杂度O(1)  
  169.             insert(begin(), n, value);  
  170.         }  
  171.         __STL_UNWIND(clear(); put_node(node));  
  172.     }  
  173.       
  174.   
  175. public:  
  176.     list() { empty_initialize(); }  
  177.   
  178.     iterator begin() { return (link_type)((*node).next); }  
  179.   
  180.     // 链表成环, 当指所以头节点也就是end  
  181.     iterator end() { return node; }  
  182.   
  183.     // 头结点指向自身说明链表中无元素  
  184.     bool empty() const { return node->next == node; }  
  185.   
  186.     // 使用全局函数distance()进行计算, 时间复杂度O(n)  
  187.     size_type size() const  
  188.     {  
  189.         size_type result = 0;  
  190.         distance(begin(), end(), result);  
  191.         return result;  
  192.     }  
  193.   
  194.     size_type max_size() const { return size_type(-1); }  
  195.     reference front() { return *begin(); }  
  196.     reference back() { return *(--end()); }  
  197.   
  198.     ////////////////////////////////////////////////////////////////////////////////  
  199.     // 在指定位置插入元素  
  200.     ////////////////////////////////////////////////////////////////////////////////  
  201.     //       insert(iterator position, const T& x)  
  202.     //                       ↓  
  203.     //                 create_node(x)  
  204.     //                 p = get_node();-------->list_node_allocator::allocate();  
  205.     //                 construct(&p->data, x);  
  206.     //                       ↓  
  207.     //            tmp->next = position.node;  
  208.     //            tmp->prev = position.node->prev;  
  209.     //            (link_type(position.node->prev))->next = tmp;  
  210.     //            position.node->prev = tmp;  
  211.     ////////////////////////////////////////////////////////////////////////////////  
  212.   
  213.     iterator insert(iterator position, const T& x)  
  214.     {  
  215.         link_type tmp = create_node(x);   // 产生一个节点  
  216.         // 调整双向指针，使tmp插入进去  
  217.         tmp->next = position.node;  
  218.         tmp->prev = position.node->prev;  
  219.         (link_type(position.node->prev))->next = tmp;  
  220.         position.node->prev = tmp;  
  221.         return tmp;  
  222.     }  
  223.   
  224.   // 指定位置插入n个值为x的元素, 详细解析见实现部分  
  225.   void insert(iterator pos, size_type n, const T& x);  
  226.   void insert(iterator pos, int n, const T& x)  
  227.   {  
  228.       insert(pos, (size_type)n, x);  
  229.   }  
  230.   void insert(iterator pos, long n, const T& x)  
  231.   {  
  232.       insert(pos, (size_type)n, x);  
  233.   }  
  234.   
  235.   // 在链表前端插入结点  
  236.   void push_front(const T& x) { insert(begin(), x); }  
  237.   // 在链表最后插入结点  
  238.   void push_back(const T& x) { insert(end(), x); }  
  239.   
  240.   // 移除迭代器position所指节点  
  241.   iterator erase(iterator position)  
  242.   {  
  243.       link_type next_node = link_type(position.node->next);  
  244.       link_type prev_node = link_type(position.node->prev);  
  245.       prev_node->next = next_node;  
  246.       next_node->prev = prev_node;  
  247.       destroy_node(position.node);  
  248.       return iterator(next_node);  
  249.   }  
  250.   
  251.   // 擦除一个区间的结点, 详细解析见实现部分  
  252.   iterator erase(iterator first, iterator last);  
  253.   
  254.   void resize(size_type new_size, const T& x);  
  255.   void resize(size_type new_size) { resize(new_size, T()); }  
  256.   void clear();  
  257.   
  258.   // 删除链表第一个结点  
  259.   void pop_front() { erase(begin()); }  
  260.   // 删除链表最后一个结点  
  261.   void pop_back()  
  262.   {  
  263.       iterator tmp = end();  
  264.       erase(--tmp);  
  265.   }  
  266.   
  267.   list(size_type n, const T& value) { fill_initialize(n, value); }  
  268.   list(int n, const T& value) { fill_initialize(n, value); }  
  269.   list(long n, const T& value) { fill_initialize(n, value); }  
  270.   
  271.   ~list()  
  272.   {  
  273.     // 释放所有结点  // 使用全局函数distance()进行计算, 时间复杂度O(n)  
  274.   size_type size() const  
  275.   {  
  276.     size_type result = 0;  
  277.     distance(begin(), end(), result);  
  278.     return result;  
  279.   }  
  280.   clear();  
  281.   // 释放头结点  
  282.   put_node(node);  
  283.   }  
  284.   
  285.   list<T, Alloc>& operator=(const list<T, Alloc>& x);  
  286.   
  287. protected:  
  288.   
  289.     ////////////////////////////////////////////////////////////////////////////////  
  290.     // 将[first, last)内的所有元素移动到position之前  
  291.     // 如果last == position, 则相当于链表不变化, 不进行操作  
  292.     ////////////////////////////////////////////////////////////////////////////////  
  293.     // 初始状态  
  294.     //                   first                             last  
  295.     //                     ↓                                 ↓  
  296.     //      --------   --------   --------     --------   --------   --------  
  297.     //      | next |-->| next |-->| next |     | next |-->| next |-->| next |  
  298.     //  ... --------   --------   -------- ... --------   --------   -------- ...  
  299.     //      | prev |<--| prev |<--| prev |     | prev |<--| prev |<--| prev |  
  300.     //      --------   --------   --------     --------   --------   --------  
  301.     //  
  302.     //                           position  
  303.     //                               ↓  
  304.     //      --------   --------   --------   --------   --------   --------  
  305.     //      | next |-->| next |-->| next |-->| next |-->| next |-->| next |  
  306.     //  ... --------   --------   --------   --------   --------   -------- ...  
  307.     //      | prev |<--| prev |<--| prev |<--| prev |<--| prev |<--| prev |  
  308.     //      --------   --------   --------   --------   --------   --------  
  309.     //  
  310.     // 操作完成后状态  
  311.     //                           first  
  312.     //                             |  
  313.     //               --------------|--------------------------------------  
  314.     //               | ------------|------------------------------------ |   last  
  315.     //               | |           ↓                                   | |     ↓  
  316.     //      -------- | |        --------   --------     --------       | |  --------   --------  
  317.     //      | next |-- |  ----->| next |-->| next |     | next |-----  | -->| next |-->| next |  
  318.     //  ... --------   |  |     --------   -------- ... --------    |  |    --------   -------- ...  
  319.     //      | prev |<---  |  ---| prev |<--| prev |     | prev |<-- |  -----| prev |<--| prev |  
  320.     //      --------      |  |  --------   --------     --------  | |       --------   --------  
  321.     //                    |  |                                    | |  
  322.     //                    |  ------                               | |  
  323.     //                    ------- |  ------------------------------ |  
  324.     //                          | |  |                              |  
  325.     //                          | |  |  -----------------------------  
  326.     //                          | |  |  |  
  327.     //                          | |  |  |  position  
  328.     //                          | |  |  |     ↓  
  329.     //      --------   -------- | |  |  |  --------   --------   --------   --------  
  330.     //      | next |-->| next |-- |  |  -->| next |-->| next |-->| next |-->| next |  
  331.     //  ... --------   --------   |  |     --------   --------   --------   -------- ...  
  332.     //      | prev |<--| prev |<---  ------| prev |<--| prev |<--| prev |<--| prev |  
  333.     //      --------   --------            --------   --------   --------   --------  
  334.     ////////////////////////////////////////////////////////////////////////////////  
  335.     void transfer(iterator position, iterator first, iterator last)  
  336.     {  
  337.         if (position != last)   // 如果last == position, 则相当于链表不变化, 不进行操作  
  338.         {  
  339.             (*(link_type((*last.node).prev))).next = position.node;  
  340.             (*(link_type((*first.node).prev))).next = last.node;  
  341.             (*(link_type((*position.node).prev))).next = first.node;  
  342.             link_type tmp = link_type((*position.node).prev);  
  343.             (*position.node).prev = (*last.node).prev;  
  344.             (*last.node).prev = (*first.node).prev;  
  345.             (*first.node).prev = tmp;  
  346.         }  
  347.     }  
  348.   
  349. public:  
  350.     // 将链表x移动到position所指位置之前  
  351.     void splice(iterator position, list& x)  
  352.     {  
  353.         if (!x.empty())  
  354.             transfer(position, x.begin(), x.end());  
  355.     }  
  356.   
  357.     // 将链表中i指向的内容移动到position之前  
  358.     void splice(iterator position, list&, iterator i)  
  359.     {  
  360.         iterator j = i;  
  361.         ++j;  
  362.         if (position == i || position == j) return;  
  363.         transfer(position, i, j);  
  364.     }  
  365.   
  366.     // 将[first, last}元素移动到position之前  
  367.     void splice(iterator position, list&, iterator first, iterator last)  
  368.     {  
  369.         if (first != last)  
  370.             transfer(position, first, last);  
  371.     }  
  372.   
  373.     void remove(const T& value);  
  374.     void unique();  
  375.     void merge(list& x);  
  376.     void reverse();  
  377.     void sort();  
  378.   
  379. };  
  380.   
  381. // 销毁所有结点, 将链表置空  
  382. template <class T, class Alloc>  
  383. void list<T, Alloc>::clear()  
  384. {  
  385.   link_type cur = (link_type) node->next;  
  386.   while (cur != node)  
  387.   {  
  388.     link_type tmp = cur;  
  389.     cur = (link_type) cur->next;  
  390.     destroy_node(tmp);  
  391.   }  
  392.   // 恢复node原始状态  
  393.   node->next = node;  
  394.   node->prev = node;  
  395. }  
  396.   
  397. // 链表赋值操作  
  398. // 如果当前容器元素少于x容器, 则析构多余元素,  
  399. // 否则将调用insert插入x中剩余的元素  
  400. template <class T, class Alloc>  
  401. list<T, Alloc>& list<T, Alloc>::operator=(const list<T, Alloc>& x)  
  402. {  
  403.   if (this != &x)  
  404.   {  
  405.     iterator first1 = begin();  
  406.     iterator last1 = end();  
  407.     const_iterator first2 = x.begin();  
  408.     const_iterator last2 = x.end();  
  409.     while (first1 != last1 && first2 != last2) *first1++ = *first2++;  
  410.     if (first2 == last2)  
  411.       erase(first1, last1);  
  412.     else  
  413.       insert(last1, first2, last2);  
  414.   }  
  415.   return *this;  
  416. }  
  417.   
  418.   
  419. // 移除容器内所有的相邻的重复结点  
  420. // 时间复杂度O(n)  
  421. // 用户自定义数据类型需要提供operator ==()重载  
  422. template <class T, class Alloc>  
  423. void list<T, Alloc>::unique()  
  424. {  
  425.   iterator first = begin();  
  426.   iterator last = end();  
  427.   if (first == last) return;  
  428.   iterator next = first;  
  429.   while (++next != last)  
  430.   {  
  431.     if (*first == *next)  
  432.       erase(next);  
  433.     else  
  434.       first = next;  
  435.     next = first;  
  436.   }  
  437. }  
  438.   
  439. // 假设当前容器和x都已序, 保证两容器合并后仍然有序  
  440. template <class T, class Alloc>  
  441. void list<T, Alloc>::merge(list<T, Alloc>& x)  
  442. {  
  443.   iterator first1 = begin();  
  444.   iterator last1 = end();  
  445.   iterator first2 = x.begin();  
  446.   iterator last2 = x.end();  
  447.   
  448.   // 注意：前提是，两个lists都已经递增排序  
  449.   while (first1 != last1 && first2 != last2)  
  450.     if (*first2 < *first1)  
  451.     {  
  452.       iterator next = first2;  
  453.       transfer(first1, first2, ++next);  
  454.       first2 = next;  
  455.     }  
  456.     else  
  457.       ++first1;  
  458.   if (first2 != last2)  
  459.       transfer(last1, first2, last2);  
  460. }  

STL源码分析--list


联系
我们