Ir para o conteúdo

Última atualização：2026-10-12

Análise do código-fonte do STL list

0. Introdução

A versão correspondente do código-fonte é gcc-4.9.1

1. list

list é uma lista ligada circular bidirecional, com a seguinte estrutura:

list 1

A figura que desenhei é a seguinte:

list_all

A lista ligada circular bidirecional começa a inserir a partir do nó de valor 3; a moldura vermelha representa o último nó (o nó apontado por end()). As linhas amarelas indicam o apontamento para o nó predecessor, e as linhas pretas indicam o apontamento para o nó sucessor.

1.1 Código-fonte do list

1.1.1 Estrutura da classe

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

 }

list herda de _List_base.

1.1.2 Implementação da lista ligada circular bidirecional

【Construtores】

（1）list sem nenhum elemento

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

（2）list com n elementos e valores iniciais atribuídos

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）inicializar um list a partir de um intervalo

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());
}

【Criação de nós】

O que faz: cria um novo nó com alocação dinâmica de memória e retorna o nó.

_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 que dentro dele há duas funções importantes, _M_get_node e _M_put_node; ao consultá-las, descobrimos que esses métodos vêm da classe base, cujo código-fonte é:

_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); }

Correspondem, respectivamente, à criação do nó com alocação dinâmica de memória e à liberação da memória caso uma exceção seja lançada durante a criação.

【Inserção de nós】

A inserção de nós inclui:

  • inserir no final n nós com um valor de nó especificado, com a função correspondente _M_fill_initialize

Usada no construtor do list:

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); }
  • inserir em uma posição especificada um nó com valor de nó especificado, com a função correspondente _M_insert

O push_back e o push_front, que todos usam com frequência, chamam na camada subjacente a função _M_insert.

A diferença entre as duas funções é:

this->_M_insert(end(), __x);  // push_back   尾部插入  
this->_M_insert(begin(), __x); // push_front 头部插入
  • a função de inserção da lista ligada circular bidirecional _M_hook (a mais importante!!!)

Funções como push_back, push_front, _M_insert, mencionadas antes, e também insert são todas implementadas com a função de inserção mais básica de lista ligada bidirecional, _M_hook.

Vamos estudá-la em profundidade:

O código-fonte de _M_fill_initialize é o seguinte:

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

O código-fonte de push_back é o seguinte:

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

Quanto a _M_insert, insere na posição especificada um nó com valor inicial x.

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

A implementação de _M_hook está em gcc-4.9.1/libstdc++-v3/src/c++98/list.cc; naturalmente, outras funções de _List_node_base, como _M_unhook, também estão nesse arquivo.

// 在指定的位置前插入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;
}

Portanto, o acima se desdobra em duas funções; resumamos o código anterior:

（1）inserir na posição especificada um nó com valor inicial x

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;            // 第四步
}

Essa inserção é feita antes da posição especificada (em termos de código): por exemplo, inserir um nó de valor 9 (que corresponde no código a __tmp) antes do nó __position de valor 7 especificado; o fluxo concreto da inserção é explicado a seguir.

list_insert

（2）inserir no final, sucessivamente, n nós com valor de nó x

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

Com o código acima, talvez vocês associem o insert, que tem três versões. O arquivo de implementação do insert é libstdc++-v3/include/bits/list.tcc.

  • Primeiro: inserir antes do iterador especificado um nó com o valor de elemento especificado.

A implementação chama a função _M_hook anterior.

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);
}
  • Segundo: inserir antes do iterador especificado n nós com o valor de nó especificado.
void insert(iterator __position, size_type __n, const value_type &__x) {
    list __tmp(__n, __x, get_allocator());
    splice(__position, __tmp);
}

A implementação primeiro chama o construtor do list, criando um list com n nós do valor de nó especificado.

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); }

Em seguida, usa a função splice para inserir no list atual a partir de outro 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());
    }
}

Rastreando o código de _M_transfer, pode-se saber:

// 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);
}

Analisando de novo, vemos que ela vem da classe base do list, _List_node_base, e o arquivo de implementação de _M_transfer é 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;
  }
}

Novamente a figura anterior:

list_all

Pela análise anterior, sabemos que splice insere o list inteiro representado pela figura acima antes do iterador especificado; por exemplo, se quisermos inserir antes dos dois nós abaixo, os passos gráficos concretos são os seguintes:

O nó representado por this é o nó de valor 8; a figura abaixo descreve a inserção do list inteiro entre o nó 10 e o nó 8.

__last representa o nó da moldura vermelha, que é o nó apontado por end(); não precisamos dele, de modo que, no processamento posterior, ele será retirado do list inteiro.

__first representa, na figura, o nó de valor 3.

Passo 1: primeiro, fazer o next do último nó válido, isto é, o nó anterior ao da moldura vermelha, apontar para o nó 8 especificado.

step1

O código correspondente é:

__last->_M_prev->_M_next  = this;

Passo 2: o next de _last aponta para ele mesmo.

step2

O código correspondente é:

__first->_M_prev->_M_next = __last;

Passo 3: fazer o next do nó anterior ao iterador especificado apontar para o primeiro nó do list original (__first).

step3

O código correspondente é:

this->_M_prev->_M_next    = __first;

Passo 4: salvar o nó predecessor do iterador especificado (correspondente, na figura, ao nó de valor 10).

_List_node_base* const __tmp = this->_M_prev;

Passo 5: o predecessor do iterador especificado passa a apontar para o que era o último nó real do list original (o nó anterior a end()).

step5

O código correspondente é:

this->_M_prev                = __last->_M_prev;

Passo 6: fazer o prev do último nó do list original (o nó apontado por end()) apontar para ele mesmo.

step6

O código correspondente é:

__last->_M_prev              = __first->_M_prev;

Passo 7: fazer o prev do primeiro nó do list original apontar para o nó salvo no passo 4.

step7

O código correspondente é:

__first->_M_prev             = __tmp;

Assim, após essas sete etapas, fica concluída a inserção de um list antes do nó 8 e do nó 10.

  • Terceiro: inserir os dados de um intervalo de um list antes do iterador especificado.
template<typename _InputIterator>
void
insert(iterator __position, _InputIterator __first,
       _InputIterator __last) {
    list __tmp(__first, __last, get_allocator());
    splice(__position, __tmp);
}

O princípio é o mesmo; a única diferença é que este __tmp chama outro construtor.

【Remoção de nós】

  • remover um nó especificado

A remoção de um nó especificado divide-se em duas: a primeira é por iterador, e a segunda, por valor de elemento.

（1）Remoção por iterador; a função correspondente é erase

A implementação subjacente de pop_front, pop_back, erase e remove baseia-se na função _M_erase.

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

Em 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）Remoção por valor de elemento; a função correspondente é remove

Tratamento do caso especial: quando o endereço do elemento removido é igual ao endereço do iterador, ele é salvo primeiro; por fim, verifica-se se o iterador salvo é end(); se não for, ele é removido. Na camada subjacente, a remoção continua sendo feita por _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);
}

Além deste remove, há também o remove_if, que remove conforme uma condição.

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;
    }
}

Basta retirar o if do remove acima e acrescentar dentro uma condição.

Uso:

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;
}
  • remover uma série de nós
  • remover todos os nós; a função correspondente é clear

（1）Análise detalhada da remoção de um nó especificado

_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);       // 释放内存
}

A implementação de _M_unhook está em gcc-4.9.1/libstdc++-v3/src/c++98/list.cc, da seguinte forma:

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指向前驱节点
}

Por exemplo: para remover o nó de valor 9, a ilustração do terceiro e do quarto passos:

list_erase

（2）Análise detalhada da remoção de uma série de elementos

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();
}

Use erase para remover os dados dentro do intervalo de iteradores dado.

（3）Análise detalhada da remoção de todos os elementos

Esvazia os elementos e reinicializa, voltando ao estado padrão do list.

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

A implementação de _M_clear está em: 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);   // 释放内存
    }
}

A implementação de _M_init: basta fazer tudo apontar para si mesmo.

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;
}

【Acesso a elementos】

Cada um implementa duas versões: referência e referência constante.

  • front retorna o primeiro elemento
reference front()
_GLIBCXX_NOEXCEPT
{ return *begin(); }
const_reference
front() const
_GLIBCXX_NOEXCEPT
{ return *begin(); }
  • retorna o último elemento
reference
back()
_GLIBCXX_NOEXCEPT
{
    iterator __tmp = end();
    --__tmp;
    return *__tmp;
}
const_reference
back() const
_GLIBCXX_NOEXCEPT
{
    const_iterator __tmp = end();
    --__tmp;
    return *__tmp;
}

【Algoritmos】

  • unique

Remove de cada grupo de elementos iguais e consecutivos do contêiner todos os elementos, exceto o primeiro.

Note que um elemento só é removido do contêiner lista quando comparado com os elementos imediatamente adjacentes no contêiner lista. Por isso, esta função é especialmente útil para listas ordenadas.

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;
  }
  }

Um exemplo:

// 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;
}

No caso acima, após a ordenação, todos os elementos duplicados são removidos, restando apenas um; sem ordenar, apenas os elementos duplicados e consecutivos são removidos.

  • merge

A implementação do merge usa a função _M_transfer anterior. Suponha que existam agora dois lists, list1 e list2. Os elementos de list1 são comparados com os de list2: se o elemento de list1 for menor que o de list2, o iterador de list1 recebe ++ e nada mais é feito; mas, se o elemento de list1 for maior que o de list2, então, a cada vez, o iterador correspondente ao menor elemento de list2 é passado à função _M_transfer, que insere o menor elemento de list2 antes do iterador de list1 recém-comparado; assim, no final, todos os elementos acabam inseridos em list1.

Quando list1 já foi inteiramente percorrido e list2 ainda não, basta executar _M_transfer uma vez, inserindo no final de list1 o trecho da lista ligada de list2 que vai do iterador atual até o end.

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);
   }
}

Uso:

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

Como o algoritmo de ordenação sort da própria STL aceita como iterador de entrada um iterador de acesso aleatório, mas a forma de acesso do contêiner lista ligada bidirecional é por iterador bidirecional, não é possível usar o sort da própria STL: é preciso definir um algoritmo de ordenação próprio para o seu modo de acesso. Da análise do código-fonte, vemos que a ideia desse algoritmo de ordenação é semelhante à do merge sort.

A chamada de splice dentro de sort é:

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

Análise mais aprofundada:

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);
}

O que é chamado por último é _M_transfer.

Em sort há ainda uma função swap, que completa a troca de duas listas ligadas; o código de implementação está em 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;
        }
}

A ideia concreta da implementação é verificar se as duas listas ligadas estão vazias ou não e, então, modificar os ponteiros next e prev.

Vejamos agora o poderoso 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)); 
    }
}

O código acima parece difícil de entender; pesquisando na internet, descobri a versão do 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]);
}

A implementação externa correspondente é:

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]);
}

Esta parte pode ser consultada em

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

com ilustrações detalhadas do processo.

Convertendo de novo o G4.9 na implementação externa correspondente:

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));
}

Uso:

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;
}

【Sobrecarga de operadores】

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;
}

A ideia de implementação é verificar, iterando, se os dois iteradores chegaram ao fim.

Restam as sobrecargas dos outros operadores, que são relativamente simples e não serão detalhadas. Entre elas, lexicographical_compare está implementada em c++-v3/src/c++98/stl_algobase.h; essa função testa, em ordem lexicográfica, se [frist1,last1) é menor que [first2,last2). A função usa operator< ou comp para comparar. O seu comportamento é semelhante a: se as duas sequências têm comprimentos diferentes e a sequência curta é exatamente igual ao começo da sequência longa — por exemplo, example e examplee —, então a de maior comprimento é lexicograficamente maior que a mais curta.

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);
}

Uso:

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;
}

Os outros operadores sobrecarregados são:

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 Código-fonte da classe base do list

Em _list_base há uma estrutura: _List_impl, e dentro de _List_impl há um 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;
};

A figura formada ao final é:

list's iterator_design

Portanto, se calcularmos:

sizeof(list<int>)=16

a razão é:

o sizeof de list é 1, então o sizeof vem da classe base _list_base; em _list_base há uma estrutura: _List_impl, e dentro de _List_impl há um _List_node_base.

Sabemos que _List_node_base tem dois ponteiros; em 64 bits, cada um com 8 bytes, são 16 bytes no total.

2. Análise do Iterator do list

2.1 iterator

Definição do iterator do list

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;
};

Funções sobrecarregadas internas:

// 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 Desenho dos nós

O _List_node interno do iterator; aqui dá para ver que ele herda de _List_node_base.

_List_node guarda a parte de dados

_List_node_base guarda os ponteiros anterior e posterior

/// 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
};

Código de _List_node_base:

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

Ao projetar o iterador, mantém-se sempre o princípio de intervalo fechado no início e aberto no fim: por exemplo, iter->begin() aponta para o primeiro elemento e iter->end() aponta para o elemento seguinte ao último elemento real; por isso, o desenho final acrescenta propositalmente um nó vazio no final do list circular, para conformar-se ao princípio da STL de fechado no início e aberto no fim.

Tópicos relacionados

Comentários