Last updated：2026-10-12

STL list source code analysis¶

0. Introduction¶

The source code corresponds to gcc-4.9.1

1.list¶

list is a doubly linked circular list, with the following structure:

list 1

A figure I drew myself:

list_all

The doubly linked circular list starts inserting from the node with value 3; the red box marks the last node (the node pointed to by end()). The yellow lines point to predecessor nodes, and the black lines point to successor nodes.

1.1 list source code¶

1.1.1 Class structure¶

 template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
 class list : protected _List_base<_Tp, _Alloc> 
 {

 }

list inherits _List_base.

1.1.2 Doubly linked circular list implementation¶

Constructors

(1) A list with no elements

explicit
list(const allocator_type &__a) _GLIBCXX_NOEXCEPT: _Base(_Node_alloc_type(__a)) {}

(2) A list with n elements, each given an initial value

explicit list(size_type __n, const value_type &__value = value_type(),const allocator_type &__a = allocator_type()) : _Base(_Node_alloc_type(__a)) 
{ _M_fill_initialize(__n, __value); }

(3) Initializing a list from a range

template<typename _InputIterator>
list(_InputIterator __first, _InputIterator __last,
     const allocator_type &__a = allocator_type())
        : _Base(_Node_alloc_type(__a)) {
    // Check whether it's an integral type.  If so, it's not an iterator.
    typedef typename std::__is_integer<_InputIterator>::__type _Integral;
    _M_initialize_dispatch(__first, __last, _Integral());
}

Creating a node

What it does: creates a new node, dynamically allocates memory, and returns the node.

_Node *_M_create_node(const value_type &__x) {
    _Node *__p = this->_M_get_node();
    __try
    {
        _M_get_Tp_allocator().construct
                (std::__addressof(__p->_M_data), __x);
    }
    __catch(...)
    {
        _M_put_node(__p);
        __throw_exception_again;
    }
    return __p;
}

Note the two important functions inside, _M_get_node and _M_put_node; looking them up we find these methods come from the base class, with source:

_List_node<_Tp> * _M_get_node() { return _M_impl._Node_alloc_type::allocate(1); }

void _M_put_node(_List_node<_Tp> *__p)   _GLIBCXX_NOEXCEPT
{ _M_impl._Node_alloc_type::deallocate(__p, 1); }

These correspond to dynamically allocating memory when creating a node; if an exception is thrown during creation, the memory is released.

Inserting a node

Node insertion includes:

Inserting n nodes with a specified node value at the tail, via the function _M_fill_initialize

Used in list's constructor:

explicit list(size_type __n, const value_type &__value = value_type(),const allocator_type &__a = allocator_type()) : _Base(_Node_alloc_type(__a)) 
{ _M_fill_initialize(__n, __value); }

Inserting a node with a specified node value at a specified position, via the function _M_insert

The push_back and push_front that everyone uses all the time call _M_insert underneath.

The difference between the two functions is:

this->_M_insert(end(), __x);  // push_back   尾部插入  
this->_M_insert(begin(), __x); // push_front 头部插入

The doubly linked circular list insertion function _M_hook (most important!!!)

The push_back, push_front, _M_insert mentioned earlier, and also insert, are all implemented using the most fundamental doubly linked list insertion function _M_hook.

Now let's dig into it:

The _M_fill_initialize source is as follows:

void _M_fill_initialize(size_type __n, const value_type &__x) {
    for (; __n; --__n)
        push_back(__x);
}

The push_back source is as follows:

void push_back(const value_type &__x) { this->_M_insert(end(), __x); }

And _M_insert inserts a node with initial value x at the specified position.

void _M_insert(iterator __position, const value_type &__x) {
    _Node *__tmp = _M_create_node(__x);
    __tmp->_M_hook(__position._M_node);
}

_M_hook is implemented in gcc-4.9.1/libstdc++-v3/src/c++98/list.cc; of course the other functions of _List_node_base, for example _M_unhook, are also in that file.

// 在指定的位置前插入this指向的节点
void_List_node_base::_M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT
{
  this->_M_next = __position;       
  this->_M_prev = __position->_M_prev;
  __position->_M_prev->_M_next = this;
  __position->_M_prev = this;
}

So the above breaks down into two functions; let's summarize the code above:

(1) Inserting a node with initial value x at the specified position

void _M_insert(iterator __position, const value_type &__x) {
    _Node *__tmp = _M_create_node(__x);
    __tmp->_M_next = __position;            // 第一步
    __tmp->_M_prev = __position->_M_prev;   // 第二步
    __position->_M_prev->_M_next = __tmp;   // 第三步
    __position->_M_prev = __tmp;            // 第四步
}

This insertion happens before the specified position (in code terms): for example, inserting a node with value 9 (which is __tmp in the code) before the specified node __position with value 7. The concrete insertion flow is described below.

list_insert

(2) Inserting n nodes with node value x one after another at the end

void _M_fill_initialize(size_type __n, const value_type &__x) {
    for (; __n; --__n)
        _M_insert(end(), __x);
}

For the code above, you may think of insert, of which there are three. The insert implementation lives in the file libstdc++-v3/include/bits/list.tcc.

First: insert a node with a specified element value before a specified iterator.

The implementation calls the earlier _M_hook function.

template<typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
insert(const_iterator __position, const value_type& __x)
#else
insert(iterator __position, const value_type& __x)
#endif
{
  _Node* __tmp = _M_create_node(__x);
  __tmp->_M_hook(__position._M_const_cast()._M_node);
  return iterator(__tmp);
}

Second: insert n nodes with a specified node value before a specified iterator.

void insert(iterator __position, size_type __n, const value_type &__x) {
    list __tmp(__n, __x, get_allocator());
    splice(__position, __tmp);
}

The implementation first calls the list constructor to create a list holding n nodes with the specified node value.

explicit list(size_type __n, const value_type &__value = value_type(),const allocator_type &__a = allocator_type()) : _Base(_Node_alloc_type(__a)) 
{ _M_fill_initialize(__n, __value); }

Then the splice function is used to insert into the current list from another list.

void splice(iterator __position, list &__x)
{
    if (!__x.empty()) {
        _M_check_equal_allocators(__x);

        this->_M_transfer(__position._M_const_cast(),
                          __x.begin(), __x.end());
    }
}

Tracing the code of _M_transfer, we can see:

// Moves the elements from [first,last) before position.
void
_M_transfer(iterator __position, iterator __first, iterator __last) {
    __position._M_node->_M_transfer(__first._M_node, __last._M_node);
}

Analyzing further, it comes from list's base class _List_node_base, and _M_transfer's implementation file is gcc-4.9.1/libstdc++-v3/src/c++98/list.cc:

void _List_node_base::
_M_transfer(_List_node_base * const __first,
    _List_node_base * const __last) _GLIBCXX_USE_NOEXCEPT
{
  if (this != __last)
  {
      // Remove [first, last) from its old position.
      __last->_M_prev->_M_next  = this;
      __first->_M_prev->_M_next = __last;
      this->_M_prev->_M_next    = __first;

      // Splice [first, last) into its new position.
      _List_node_base* const __tmp = this->_M_prev;
      this->_M_prev                = __last->_M_prev;
      __last->_M_prev              = __first->_M_prev;
      __first->_M_prev             = __tmp;
  }
}

Again the same figure:

list_all

From the earlier analysis, we know splice inserts the entire list represented by the figure before the specified iterator. For example, suppose we want to insert before the two nodes below; the concrete graphical steps are as follows:

The node represented by this is the node with value 8; the figure below describes inserting the entire list between node 10 and node 8.

__last represents the red-box node, which is the node pointed to by end(); we do not need that node, so in the processing below it gets removed from the whole list.

__first represents the node with value 3 in the figure.

Step 1: First, make the last valid node — that is, the node before the red box — have its next pointer point to the specified node 8.

step1

The corresponding code:

__last->_M_prev->_M_next  = this;

Step 2: _last's next pointer points to itself.

step2

The corresponding code:

__first->_M_prev->_M_next = __last;

Step 3: Make the node before the specified iterator have its next point to the original list's first node (__first).

step3

The corresponding code:

this->_M_prev->_M_next    = __first;

Step 4: Save the specified iterator's predecessor node (corresponding to the node with value 10 in the figure).

_List_node_base* const __tmp = this->_M_prev;

Step 5: The specified iterator's predecessor node points to the original list's actual last node (the node before end()).

step5

The corresponding code:

this->_M_prev                = __last->_M_prev;

Step 6: Make the original list's last node's (the node pointed to by end()) prev point to itself.

step6

The corresponding code:

__last->_M_prev              = __first->_M_prev;

Step 7: Make the original list's first node's prev point to the node saved in step 4.

step7

The corresponding code:

__first->_M_prev             = __tmp;

With these seven steps, inserting a list before node 8 and node 10 is complete.

Third: insert data from a range of a list before a specified iterator.

template<typename _InputIterator>
void
insert(iterator __position, _InputIterator __first,
       _InputIterator __last) {
    list __tmp(__first, __last, get_allocator());
    splice(__position, __tmp);
}

The principle is the same; the only difference is that this __tmp calls another constructor.

Deleting nodes

Deleting a specified node

Deleting a specified node comes in two kinds: the first deletes via an iterator, the second via the element value.

(1) Deleting via an iterator, via the function erase

pop_front, pop_back, erase, and remove are all implemented on top of the _M_erase function.

this->_M_erase(begin());    // pop_front 不断删除起点的元素
this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); // pop_back移除最后一个元素

In libstdc++-v3/include/bits/list.tcc:

erase(iterator __position)
#endif
{
  iterator __ret = iterator(__position._M_node->_M_next);
  _M_erase(__position._M_const_cast());
  return __ret;
}

(2) Deleting via the element value, via the function remove

Special-case handling: when the deleted element's address equals the iterator's address, save it first; at the end, check whether the saved iterator is end(), and if not, delete it. Underneath, deletion is still done via _M_erase.

template<typename _Tp, typename _Alloc>
void list<_Tp, _Alloc>::remove(const value_type& __value)
{
  iterator __first = begin();
  iterator __last = end();
  iterator __extra = __last;
  while (__first != __last)
  {
      iterator __next = __first;
      ++__next;
      if (*__first == __value)
        {
          // _GLIBCXX_RESOLVE_LIB_DEFECTS
          // 526. Is it undefined if a function in the standard changes
          // in parameters?
          if (std::__addressof(*__first) != std::__addressof(__value))
        _M_erase(__first);
          else
        __extra = __first;
        }
      __first = __next;
  }
  if (__extra != __last)
    _M_erase(__extra);
}

Besides this remove, there is also remove_if, which deletes according to a condition.

template<typename _Tp, typename _Alloc>
template <typename _Predicate>
void list<_Tp, _Alloc>::
remove_if(_Predicate __pred)
{
    iterator __first = begin();
    iterator __last = end();
    while (__first != __last)
    {
        iterator __next = __first;
        ++__next;
        if (__pred(*__first))
          _M_erase(__first);
        __first = __next;
    }
}

Just remove the if from the remove above and add a check inside.

Used as follows:

bool isone(int one) {
    return one==2;
}
int main() {
    list<int> t;
    t={3,4,0,2,0,10,10};
    for(auto i:t) cout<<i<<" ";  // 3 4 0 2 0 10 10 
    cout<<endl;
    t.remove_if(isone);
    for(auto i:t) cout<<i<<" ";  // 3 4 0 0 10 10 
    cout<<endl;
}

Deleting a series of nodes
Deleting all nodes, via the function clear

(1) Detailed analysis of deleting a specified node

_M_erase(iterator __position)
_GLIBCXX_NOEXCEPT
{
    __position._M_node->_M_unhook();
    _Node *__n = static_cast<_Node *>(__position._M_node);
#if __cplusplus >= 201103L
    _M_get_Node_allocator().destroy(__n);
#else
    _M_get_Tp_allocator().destroy(std::__addressof(__n->_M_data));
#endif
    _M_put_node(__n);       // 释放内存
}

_M_unhook is implemented in gcc-4.9.1/libstdc++-v3/src/c++98/list.cc, as follows:

void _List_node_base::_M_unhook() _GLIBCXX_USE_NOEXCEPT
{
  _List_node_base* const __next_node = this->_M_next;   // 第一步：保存后继节点
  _List_node_base* const __prev_node = this->_M_prev;   // 第二步：保存前驱节点
  __prev_node->_M_next = __next_node;                   // 第三步：前驱节点的next指向后继节点
  __next_node->_M_prev = __prev_node;                   // 第四步：后继节点的prev指向前驱节点
}

For example: to delete the node with value 9, the third and fourth steps illustrated:

list_erase

(2) Detailed analysis of deleting a series of elements

iterator
#if __cplusplus >= 201103L
erase(const_iterator __first, const_iterator __last) noexcept
#else
erase(iterator __first, iterator __last)
#endif
{
    while (__first != __last)
        __first = erase(__first);
    return __last._M_const_cast();
}

Uses erase to delete the data within the given iterator range.

(3) Detailed analysis of deleting all elements

Empties the elements and reinitializes, returning the list to its default state.

void clear()
_GLIBCXX_NOEXCEPT
{
    _Base::_M_clear();
    _Base::_M_init();
}

_M_clear is implemented in libstdc++-v3/include/bits/list.tcc:

_List_base<_Tp, _Alloc>::
_M_clear() _GLIBCXX_NOEXCEPT
{
  typedef _List_node<_Tp>  _Node;
  _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
  while (__cur != &_M_impl._M_node)
    {
      _Node* __tmp = __cur;         // 保存节点
      __cur = static_cast<_Node*>(__cur->_M_next);  // 往后遍历
    #if __cplusplus >= 201103L
      _M_get_Node_allocator().destroy(__tmp);
    #else
      _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
    #endif
      _M_put_node(__tmp);   // 释放内存
    }
}

_M_init's implementation: just make everything point to itself.

void _M_init()
_GLIBCXX_NOEXCEPT
{
    this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
    this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
}

Element access

Each of these is implemented in two versions: reference and const reference.

front returns the first element

reference front()
_GLIBCXX_NOEXCEPT
{ return *begin(); }
const_reference
front() const
_GLIBCXX_NOEXCEPT
{ return *begin(); }

Returns the last element

reference
back()
_GLIBCXX_NOEXCEPT
{
    iterator __tmp = end();
    --__tmp;
    return *__tmp;
}
const_reference
back() const
_GLIBCXX_NOEXCEPT
{
    const_iterator __tmp = end();
    --__tmp;
    return *__tmp;
}

Algorithms

unique

Removes all but the first element from each consecutive group of equal elements in the container.

Note that an element is only removed from the list container when it compares equal to the element immediately preceding it in the list container. This function is therefore especially useful for sorted lists.

template<typename _Tp, typename _Alloc>
template <typename _BinaryPredicate>
  void
  list<_Tp, _Alloc>::
  unique(_BinaryPredicate __binary_pred)
  {
    iterator __first = begin();
    iterator __last = end();
    if (__first == __last)
  return;
    iterator __next = __first;
    while (++__next != __last)
  {
    // 满足条件就删除
    if (__binary_pred(*__first, *__next))
       // 删除
      _M_erase(__next);
    else
      __first = __next;
    __next = __first;
  }
  }

An example:

// list::unique
#include <iostream>
#include <cmath>
#include <list>

// a binary predicate implemented as a function:
bool same_integral_part (double first, double second)
{ return ( int(first)==int(second) ); }

// a binary predicate implemented as a class:
struct is_near {
  bool operator() (double first, double second)
  { return (fabs(first-second)<5.0); }
};

int main ()
{
  double mydoubles[]={ 12.15,  2.72, 73.0,  12.77,  3.14,
                       12.77, 73.35, 72.25, 15.3,  72.25 };
  std::list<double> mylist (mydoubles,mydoubles+10);

  mylist.sort();             //  2.72,  3.14, 12.15, 12.77, 12.77,
                             // 15.3,  72.25, 72.25, 73.0,  73.35

  mylist.unique();           //  2.72,  3.14, 12.15, 12.77
                             // 15.3,  72.25, 73.0,  73.35

  mylist.unique (same_integral_part);  //  2.72,  3.14, 12.15
                                       // 15.3,  72.25, 73.0

  mylist.unique (is_near());           //  2.72, 12.15, 72.25

  std::cout << "mylist contains:";
  for (std::list<double>::iterator it=mylist.begin(); it!=mylist.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

The above: after sorting, all duplicate elements are removed leaving one, whereas without sorting only duplicate and consecutive elements are removed.

merge

The merge source implementation uses the earlier _M_transfer function. Suppose there are now two lists, list1 and list2. Each element of list1 is compared with the elements of list2: if the list1 element's value is less than the list2 element's value, the list1 iterator is ++'d and nothing is done; if the list1 element's value is greater than the list2 element's value, then the iterator of that smaller list2 element is fed into _M_transfer each time, and through this function the smaller list2 element is inserted into list1 before the iterator just compared. In the end all the elements end up inserted into list1.

When list1 has been fully traversed while list2 has not, a single _M_transfer suffices, inserting the list2 chain from the current iterator to the final end at the tail of list1.

template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
merge(list&& __x)
#else
merge(list& __x)
#endif
{
  // _GLIBCXX_RESOLVE_LIB_DEFECTS
  // 300. list::merge() specification incomplete
  if (this != &__x)
  {
      _M_check_equal_allocators(__x);

      iterator __first1 = begin();
      iterator __last1 = end();
      iterator __first2 = __x.begin();
      iterator __last2 = __x.end();
      while (__first1 != __last1 && __first2 != __last2)
        if (*__first2 < *__first1)
         {
            iterator __next = __first2;
            _M_transfer(__first1, __first2, ++__next);
            __first2 = __next;
         }
        else
          ++__first1;
      if (__first2 != __last2)
        _M_transfer(__last1, __first2, __last2);
   }
}

Usage:

int main() {
    list<int> l1 = {2,3,5,7};
    list<int> l2 = {1,10,9,5};
    l1.sort();
    l2.sort();
    l1.merge(l2);
    for(auto i:l1) cout<<i<<" ";    // 1 2 3 5 5 7 9 10
    return 0;
}

sort

Since the STL's own sorting algorithm sort accepts random access iterators as input, but the doubly linked list container is accessed with bidirectional iterators, the STL's own sort cannot be used, and a sorting algorithm of its own must be defined. From the source dissection we can see that this sorting algorithm's idea resembles merge sort.

The splice called inside sort is:

void splice(const_iterator __position, list& __x, const_iterator __i) noexcept
{ splice(__position, std::move(__x), __i); }

Analyzing further:

void
splice(iterator __position, list &__x, iterator __i)
{
    iterator __j = __i._M_const_cast();
    ++__j;
    if (__position == __i || __position == __j)
        return;

    if (this != &__x)
        _M_check_equal_allocators(__x);

    this->(__position._M_const_cast(),
                      __i._M_const_cast(), __j);
}

What gets called in the end is _M_transfer.

There is also a swap function inside sort that swaps two lists; its implementation lives in gcc-4.9.1/libstdc++-v3/src/c++98/list.cc:

void
_List_node_base::swap(_List_node_base& __x,
          _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT
{
      if ( __x._M_next != &__x )
    {
      if ( __y._M_next != &__y )
        {
          // Both __x and __y are not empty.
          std::swap(__x._M_next,__y._M_next);
          std::swap(__x._M_prev,__y._M_prev);
          __x._M_next->_M_prev = __x._M_prev->_M_next = &__x;
          __y._M_next->_M_prev = __y._M_prev->_M_next = &__y;
        }
      else
        {
              // __x is not empty, __y is empty.
              __y._M_next = __x._M_next;
              __y._M_prev = __x._M_prev;
              __y._M_next->_M_prev = __y._M_prev->_M_next = &__y;
              __x._M_next = __x._M_prev = &__x;
            }
        }
      else if ( __y._M_next != &__y )
        {
          // __x is empty, __y is not empty.
          __x._M_next = __y._M_next;
          __x._M_prev = __y._M_prev;
          __x._M_next->_M_prev = __x._M_prev->_M_next = &__x;
          __y._M_next = __y._M_prev = &__y;
        }
}

The concrete implementation idea: determine whether each list is empty or not, then update the next and prev pointers.

Now for the mighty sort:

template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
sort() {
    // Do nothing if the list has length 0 or 1.
    if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
        && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) {
        list __carry; // 辅助链表，用于从a中提取元素以及临时保存两个链表的合并结果
        list __tmp[64]; // 保存着当前每一个归并层次的结果, i号链表保存的元素个数为2的i次方或者0
        list *__fill = &__tmp[0]; // 表示当前最大归并排序的层次，while循环之后__fill变成log2(list.size())
        list *__counter;

        do {
            __carry.splice(__carry.begin(), *this, begin()); //把当前链表的第一个节点放在carry链表头

            for (__counter = &__tmp[0];
                 __counter != __fill && !__counter->empty();
                 ++__counter) {
                __counter->merge(__carry);  // 两个有序链表合并
                __carry.swap(*__counter); // 类似于交换链表carry和counter[i]内容  
            }
            __carry.swap(*__counter); // 类似于交换链表carry和counter[i]内容  
            if (__counter == __fill)
                ++__fill;
        } while (!empty());
        // 每两个进行归并，依次网上，直到最后*(__fill-1)保存最后的排序结果。然后交换到当前list中。
        for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
            __counter->merge(*(__counter - 1));
        swap(*(__fill - 1)); 
    }
}

The code above is rather hard to digest; after searching online, in G2.9:

template <class T, class Alloc>
void list<T, Alloc> :: sort(){
    // 判断链表是否为空或者只有一个元素
    if(node->next == node || link_type(node->next)->next == node){
        return;
    }

    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.swap(counter[i]);
        if(i == fill){
            ++fill;
        } 
    }

    for(int i = 1; i < fill; ++i){
        counter[i].merge(counter[i-1]);
    }
    swap(counter[fill-1]);
}

The corresponding external implementation:

void sortList(list<int> &l) {
    if (l.size() <= 1) {
        return;
    }
    list<int> carry;       // 辅助链表，用于从a中提取元素以及临时保存两个链表的合并结果
    list<int> counter[64]; // 保存着当前每一个归并层次的结果, i号链表保存的元素个数为2的i次方或者0
    int fill = 0;          // 表示当前最大归并排序的层次，while循环之后fill变成log2(a.size())

    while (!l.empty()) {
        carry.splice(carry.begin(), l, l.begin()); // 将链表a中的第一个元素移动至carry开头
        int i = 0;
        // 从小往大不断合并非空归并层次直至遇到空层或者到达当前最大归并层次
        while (i < fill && !counter[i].empty()) {
            counter[i].merge(carry);    // 链表合并，结果链表是有序的，必须保证合并前两个链表是有序的
            carry.swap(counter[i++]);   // 链表元素互换
        }
        carry.swap(counter[i]);
        if (i == fill) {       // i到达当前最大归并层次，说明得增加一层
            ++fill;
        }
    }

    for (int i = 1; i < fill; ++i) {  // 将所有归并层次的结果合并得到最终结果counter[fill - 1]
        counter[i].merge(counter[i - 1]);
    }
    l.swap(counter[fill - 1]);
}

For this part you can refer to

https://blog.csdn.net/chenhanzhun/article/details/39337331

which gives a detailed illustrated walkthrough.

Converting the G4.9 version to the corresponding external implementation once more:

void sortList1(list<int> &l) {
    typedef list<int> list;
    if (l.size() <= 1) {
        return;
    }
    list __carry;
    list __tmp[64];
    list *__fill = &__tmp[0];
    list *__counter;
    do {
        __carry.splice(__carry.begin(), l, l.begin());
        for (__counter = &__tmp[0];
             __counter != __fill && !__counter->empty();
             ++__counter) {
            __counter->merge(__carry);
            __carry.swap(*__counter);
        }
        __carry.swap(*__counter);
        if (__counter == __fill) ++__fill;
    } while (!l.empty());

    for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
        __counter->merge(*(__counter - 1));

    l.swap(*(__fill - 1));
}

Usage:

int main() {
    list<int> l = {7, 5, 8, 1};
    cout << "===============排序前==============" << endl;
    for (auto i:l) cout << i << " ";
    cout << endl;
    sortList1(l);
    cout << "===============排序后==============" << endl;
    for (auto i:l) cout << i << " ";
    cout << endl;

    return 0;
}

Operator overloading

template<typename _Tp, typename _Alloc>
inline bool
operator==(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) {
    typedef typename list<_Tp, _Alloc>::const_iterator const_iterator;
    const_iterator __end1 = __x.end();
    const_iterator __end2 = __y.end();

    const_iterator __i1 = __x.begin();
    const_iterator __i2 = __y.begin();
    while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
        ++__i1;
        ++__i2;
    }
    return __i1 == __end1 && __i2 == __end2;
}

The implementation idea: iteratively check whether both iterators have reached the end.

The rest are the other operator overloads, which are fairly simple and need no elaboration. lexicographical_compare is implemented in c++-v3/src/c++98/stl_algobase.h; this function tests lexicographically whether [frist1,last1) is less than [first2,last2). It compares using opeartor< or comp. Its behavior: if the two sequences differ in length and the shorter is identical to the head of the longer — for example example and examplee — then the longer one is lexicographically greater than the shorter.

template <class InputIterator1, class InputIterator2>
bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2)
{
    while (first1!=last1)
    {
        if (first2==last2 || *first2<*first1) return false;
        else if (*first1<*first2) return true;
        ++first1; ++first2;
    }
    return (first2!=last2);
}

Usage:

int main() {
     vector<char> v1{'h','e','l','l','o'};
    vector<char> v2{'h','e','l','l','o','o'};
    vector<char> v3{'h','e','l','m','o'};
    cout<<"v1=";
    for(char i:v1)
        cout<<i<<" ";
    cout<<endl;
    cout<<"v2=";
    for(char i:v2)
        cout<<i<<" ";
    cout<<endl;
    cout<<"v3=";
    for(char i:v3)
        cout<<i<<" ";
    cout<<endl;

    if(lexicographical_compare(v1.begin(),v1.end(),v2.begin(),v2.end()))
        cout<<"v1 is less than v2 "<<endl;
    else
        cout<<"v2 is less than v1 "<<endl;

    if(lexicographical_compare(v1.begin(),v1.end(),v3.begin(),v3.end()))
        cout<<"v1 is less than v3 "<<endl;
    else
        cout<<"v3 is less than v1 "<<endl;
}

The other overloaded operators:

template<typename _Tp, typename _Alloc>
inline bool
operator<(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) {
    return std::lexicographical_compare(__x.begin(), __x.end(),
                                        __y.begin(), __y.end());
}

/// Based on operator==
template<typename _Tp, typename _Alloc>
inline bool
operator!=(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) { return !(__x == __y); }

/// Based on operator<
template<typename _Tp, typename _Alloc>
inline bool
operator>(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) { return __y < __x; }

/// Based on operator<
template<typename _Tp, typename _Alloc>
inline bool
operator<=(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) { return !(__y < __x); }

/// Based on operator<
template<typename _Tp, typename _Alloc>
inline bool
operator>=(const list<_Tp, _Alloc> &__x, const list<_Tp, _Alloc> &__y) { return !(__x < __y); }

1.2 list base class source code¶

_list_base contains a struct, _List_impl, and _List_impl contains a List_node_base.

class _List_base
{
protected:
  typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
    _Node_alloc_type;

  typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

  struct _List_impl
  : public _Node_alloc_type
  {
    __detail::_List_node_base _M_node;

    _List_impl()
    : _Node_alloc_type(), _M_node()
    { }

    _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT
    : _Node_alloc_type(__a), _M_node()
    { }

    #if __cplusplus >= 201103L
    _List_impl(_Node_alloc_type&& __a) _GLIBCXX_NOEXCEPT
    : _Node_alloc_type(std::move(__a)), _M_node()
    { }
    #endif
  };

  _List_impl _M_impl;
};

The figure that finally emerges is:

list's iterator_design

So if you evaluate:

sizeof(list<int>)=16

The reason:

list's own sizeof is 1, so the sizeof comes from the base class _list_base; _list_base contains a struct, _List_impl, and _List_impl contains a _List_node_base.

We know _List_node_base holds two pointers; on 64-bit, each is 8 bytes, 16 bytes in total.

2.list's Iterator dissection¶

2.1 iterator¶

The definition of list's iterator

template<typename _Tp>
struct _List_iterator
{
  typedef _List_iterator<_Tp>                _Self;
  typedef _List_node<_Tp>                    _Node;

  typedef ptrdiff_t                          difference_type;
  typedef std::bidirectional_iterator_tag    iterator_category;
  typedef _Tp                                value_type;
  typedef _Tp*                               pointer;
  typedef _Tp&                               reference;

   // The only member points to the %list element.
   __detail::_List_node_base* _M_node;         
   //  _List_node(节点的数据部分) -> _List_node_base(前指针与后指针)

  _List_iterator() _GLIBCXX_NOEXCEPT
  : _M_node() { }

  explicit
  _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
  : _M_node(__x) { }

  _Self
  _M_const_cast() const _GLIBCXX_NOEXCEPT
  { return *this; }

  // The only member points to the %list element.
  __detail::_List_node_base* _M_node;
};

Internal overloaded functions:

// Must downcast from _List_node_base to _List_node to get to _M_data.
// 重载*操作符
reference operator*() const _GLIBCXX_NOEXCEPT
{ 
    return static_cast<_Node*>(_M_node)->_M_data; 
}

// 重载->操作符
pointer operator->() const _GLIBCXX_NOEXCEPT
{ 
    return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); 
}

// 重载前置++操作符  ++i
_Self& operator++() _GLIBCXX_NOEXCEPT   
{ 
    _M_node = _M_node->_M_next;
    return *this;
}

// 重载后置++操作符 i++
_Self operator++(int) _GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;             // 记录原值  *调用的是拷贝构造函数
    _M_node = _M_node->_M_next;      // 进行操作
    return __tmp;                    // 返回原值
}

// 重载前置--操作符  --i
_Self& operator--() _GLIBCXX_NOEXCEPT
{
    _M_node = _M_node->_M_prev;
    return *this;
}
// 重载后置--操作符  --i
_Self operator--(int) _GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;
    _M_node = _M_node->_M_prev;
    return __tmp;
}
// 重载++操作符
bool operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT
{ 
    return _M_node == __x._M_node; 
}
// 重载!=操作符
bool operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT
{ 
    return _M_node != __x._M_node; 
}

2.2 Node design¶

The _List_node inside the iterator — here we can see it inherits from _List_node_base.

_List_node holds the data part

_List_node_base holds the forward and backward pointers

/// An actual node in the %list.
template<typename _Tp>
struct _List_node : public __detail::_List_node_base
{
  ///< User's data.
  _Tp _M_data;

#if __cplusplus >= 201103L
  template<typename... _Args>
    _List_node(_Args&&... __args)
: __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...) 
    { }
#endif
};

The _List_node_base code:

namespace __detail
{
    _GLIBCXX_BEGIN_NAMESPACE_VERSION
    /// Common part of a node in the %list. 
    struct _List_node_base
    {
      _List_node_base* _M_next;
      _List_node_base* _M_prev;

      static void
      swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT;

      void
      _M_transfer(_List_node_base* const __first,
          _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT;

      void
      _M_reverse() _GLIBCXX_USE_NOEXCEPT;

      void
      _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT;

      void
      _M_unhook() _GLIBCXX_USE_NOEXCEPT;
    };

    _GLIBCXX_END_NAMESPACE_VERSION
} // namespace detail

When the iterator was designed, the half-open principle was always maintained: for example iter->begin() points to the first element, and iter->end() points to the element after the actual last one. Hence the final design deliberately adds a blank node at the tail of the circular list, to conform to the STL's half-open (front-inclusive, back-exclusive) principle.

STL list source code analysis¶

0. Introduction¶

1.list¶

1.1 list source code¶

1.1.1 Class structure¶

1.1.2 Doubly linked circular list implementation¶

1.2 list base class source code¶

2.list's Iterator dissection¶

2.1 iterator¶

2.2 Node design¶

Related Topics¶

Comments