从前文我们知道vector的迭代器是元素类型指针，而list的迭代器比较高级——是一个自己手搓的自定义类型。list的迭代器属于双向迭代器（Bidirectional Iterator）。

那么这里需要插叙一下有关迭代器类型的知识。在SGI版本的STL实现中，迭代器被分为了五种类别。例如，输入迭代器在读写方面仅支持读操作，在移动方面仅支持自增；输出迭代器在读写方面仅支持写操作，在移动方面仅支持自增。后续还有前向迭代器、双向迭代器和随机访问迭代器。按照以上顺序，从左到右所支持的操作逐渐进行扩展。例如，前向迭代器综合了输入、输出迭代器类型的功能支持读和写；双向迭代器在前向迭代器的基础上，在移动方面还支持自减操作；随机访问迭代器则在双向迭代器的功能基础上，在移动方面还支持跳转移动操作。综合来看，这五类迭代器呈现出“继承”结构，如下图所示（图片借鉴了侯捷所著的《STL源码剖析》一书）。

1、链表节点类型设计

这一节主要介绍list容器的存储节点类型是如何设计的。在SGI版本的STL中，将单位节点类型声明为__list_node<T>。在该类型中包含两个无类型指针prev和next，以及一个T类型对象data。其中，prev和next的声明可以替换为使用__list_node<T>*。其原因是为了兼容早期编译器，并减少模板类型依赖，所以将节点之间的链接指针定义为void*，然后再手动强转成其他类型。data用于存储实际的数据；prev和next分别指向上一个节点和下一个节点。

template <class T> struct __list_node{ typedef void* void_pointer; void_pointer prev; void_pointer next; T data; }; //更合理的版本如下 template <class T> struct __list_node{ __list_node* prev; __list_node* next; T data; };

2、迭代器类型设计

list容器的迭代器类型为__list_iterator<T, Ref, Ptr>。每一个迭代器内部都会存储一个指向__list_node<T>的指针node。该迭代器结构体定义有三种构造函数形式：第一种，默认构造：什么形参和函数体也没有；第二种，有参构造函数：接收形参link_type，即指向__list_node<T>的指针。该构造函数将传入参数的值传递给node；第三种，有参构造函数：接收形参为iterator类型的const引用。该构造函数将传入的迭代器的node传递给自身node。该结构体内部定义的别名link_type、iterator以及几个构造函数如下所示。

template <class T, class Ref, class Ptr> struct __list_iterator{ typedef __list_node<T>* link_type; link_type node; typedef __list_iterator<T, T&, T*> iterator; __list_iterator() {} __list_iterator(link_type x) : node(x) {} __list_iterator(const iterator& x) : node(x.node) {} ... };

在该迭代器内部不仅有iterator的重命名，还有self的重命名。其表示与本对象模板类型完全相同的类型。还有许多操作运算符重载函数：“==”和“!=”运算符重载函数用于判断两node指针是否指向相同位置，且接收参数是const self引用类型，即必须保证与对象完全相同类型；“*”运算符重载函数类似于指针的解引用操作，返回node指向的节点内部成员data的引用；“->”运算符重载函数返回指向成员data的地址，即可以通过该值对data内部成员进一步访问，若有的话；还有前缀和后缀的自增与自减运算符重载函数：各函数体内对node进行后移或前移。前缀返回该对象的引用，后缀则返回该对象的一个拷贝。

typedef Ref reference; typedef Ptr pointer; typedef __list_iterator<T, Ref, Ptr> self; bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } reference operator*() const { return (*node).data; } pointer operator->() const { return &(operator*()); } self& operator++(){ node = (link_type)((*node).next); return *this; } self operator++(int){ self tmp = *this; ++*this; return tmp; } self& operator--(){ node = (link_type)((*node).prev); return *this; } self operator--(int){ self tmp = *this; --*this; return tmp; }

3、list容器相关设计

对链表存储节点类型和迭代器类型有了一定的了解后，下面开始对list容器的部分实现进行讲述。在内存申请和回收方面，代码中声明了一个空间配置器别名list_node_allocator和一个存储节点类型别名list_node。且在模板参数中传入list_node，表示以list_node结构体类型所占内存大小为单位进行内存空间处理。代码中有一个get_node()函数，主要作用是申请内存。进入get_node函数后，会调用list_node_allocator的allocate函数进行申请内存并返回，返回类型为link_type。而在每次回收内存时会调用put_node(link_type)函数。该函数接收link_type参数（指向list_node的指针）后，调用list_node_allocator的deallocate函数，进行内存回收。以上两个函数都会调用空间配置器内部方法。若单次内存空间大于128字节，该函数调用的是一级空间配置器的相关函数，否则调用二级空间配置器的相关函数。

template <class T， class Alloc = alloc> class list{ typedef __list_node<T> list_node; typedef simple_alloc<list_node, Alloc> list_node_allocator; link_type get_node() { return list_node_allocator::allocate(); } void put_node(link_type p) { list_node_allocator::deallocate(p); } ... } //alloc.h static T* allocate(void){ return (T*)Alloc::allocate(sizeof(T)); } static void deallocate(T* p){ Alloc::deallocate(p, sizeof(T)); }

在容器初始化方面，该容器实现了一个无参构造函数，且该函数内部通过间接调用函数empty_initialize()进行实现。在empty_initialize函数中，需要调用get_node方法申请一片存储list_node的内存空间，并返回指向该片内存的指针。因为初始并无元素，因此将prev和next都指向自己。由此可见，该list是一个双向循环链表。

link_type node; list() { empty_initialize(); } void empty_initialize(){ node = get_node(); node->next = node; node->prev = node; }

再来看看首插push_front(const T&)和尾插push_back(const T&)两个函数是如何实现的。这两个函数内部均调用insert(iterator, const T&)函数。insert函数先调用create_node(const T&)函数，得到指向已初始化的link_node的指针tmp，然后对tmp进行经典的双向链表插入操作后，返回tmp值，并通过隐式构造函数__list_iterator(iterator)创建一个新的迭代器返回给用户，表示指向当前插入区域的位置。而在create_node(const T&)函数中，依然是通过咱们上述的get_node函数进行内存空间的申请，然后调用construct.h文件定义的一个construct(T1*, const T2&)函数，在指定的内存空间（在本函数中及get_node()返回的空间首地址）中创建对应的T类型对象。此时，我们申请的内存空间立即有了“居民”——list_node类型对象。最后返回该片内存地址。

typedef __list_iterator<T, T&, T*> iterator; iterator begin() { return (link_type)((*node).next); } iterator end() { return node; } void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); } iterator insert(iterator position, const T& x){ link_type tmp = create_node(x); tmp->next = position.node; tmp->prev = position.node->prev; (link_type(position.node->prev))->next = tmp; position.node->prev = tmp; return tmp; } link_type create_node(const T& x){ link_type p = get_node(); construct(&p->data, x); return p; } //construct.h template <class T1, class T2> inline void construct(T1* p, const T2& value){ new (p) T1 (value); }

对于单独节点的销毁操作，则可调用destroy_node(link_type)函数。该函数通过调用construct.h文件中的destroy(T*)函数进行对象的析构，然后调用put_node(link_type)对内存回收。

void destroy_node(link_type p){ destroy(&p->data); put_node(p); } //construct.h template <class T> inline void destroy(T* pointer){ pointer->~T(); }

在list容器中也存在一个swap(list<T, Alloc>&)函数，作用是交换两个链表。因为在该list容器中仅需要通过一个成员对象node就可访问所有的数据，且所有需要访问数据的函数都需要通过node进行，所以仅需交换两list容器的node节点即可完成链表的交换。

在list容器当中也包含一个清除所有节点的函数clear()。该函数从头节点开始（node->next）一个接一个地删除。注意在本版本的实现中，每次抽取一个待删节点的时候不需要完整地维护整个链表，只需要保证链表上的节点是可以找到的。我想可能的原因是：clear()函数是要清空所有的元素，因此没有必要维护要删除的链表。除此之外，还有一个unique()函数。该函数的功能是删除连续重复的元素，具体实现方法也是比较常规的依次遍历思路，这里就不多说了。

下面将介绍一个对于list容器比较重要的函数transfer(iterator position, iterator first, iterator last)。该函数的功能是将first到last区间内的元素缝接到position位置（包括first管理的节点，但不包括last管理的节点）。具体的步骤如下：1、将迭代器last管理节点的prev节点的next指向迭代器position管理节点；2、将迭代器first管理节点的prev节点的next指向last管理节点；3、将迭代器position管理节点的prev节点的next指向first管理节点；4、使用临时link_type类型tmp，记录position管理节点的prev节点；5、将position管理节点的prev指向last管理节点的prev节点；6、将last管理节点的prev指向first管理节点的prev节点；7、将first管理节点的prev指向tmp。引入一个临时变量tmp的原因是避免断链——个人尝试过不引入临时变量进行指向转化，发现无法完成。其原因是：每个prev重定向操作都依赖其他待操作节点地prev进行访问，形成了一个闭环。该transfer函数在后续的各种操作函数均有使用。

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); (*position.node).prev = (*last.node).prev; (*last.node).prev = (*first.node).prev; (*first.node).prev = tmp; } }

下面讲述splice相关方法。该函数主要功能是将某一连续的元素串或单个元素缝接到目标位置。其中包含三种重载函数：第一种，splice(iterator position, list& x)：该函数用于将另一list容器的元素缝接到迭代器所指位置position，通过间接调用transfer(iterator, iterator, iterator)函数实现。第二种，splice(iterator, list&, iterator)：该函数用于将某一list的某一位置的元素缝接到本list的某一位置。若待插元素已经在目标位置，则可以直接返回无需下一步操作；否则依然间接调用transfer函数。第三种，splice(iterator, list&, iterator, iterator)：该函数用于将某一区间的所有元素缝接到目标位置。主要还是通过调用transfer函数实现。值得注意的是，三个函数的重载对于条件“是否不同链表”有不同的适应性。例如，第一个函数不允许同一链表；第二个函数允许同一链表；第三个函数对于同一链表关于position位置包含在区间内的情况未定义。

void splice(iterator position, list& x){ if(!x.empty()) transfer(position, x.begin(), x.end()); } void splice(iterator position, list&, iterator i){ iterator j = i; ++j; if(position == i || position == j) return; transfer(position, i, j); } void splice(iterator position, list&, iterator first, iterator last){ if(first != last) transfer(position, first, last); }

list容器提供了merge(list&)函数，其作用是将两个递增有序的链表进行合并，实现思路可参考归并排序。除了提供合并操作外，还提供了reverse()函数，用于将链表元素反转。其主要通过transfer函数不断将后续节点插入到begin()位置，从而实现链表反转。

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(); //两list都递增有序 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); } template <class T, class Alloc> void list<T, Alloc>::reverse(){ 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容器还提供了一个sort()函数，用于将无序的链表变成有序。该函数创建一个临时链表carry和存储链表的数组counter（list<T, Alloc>[]）用于记录中间结果。carry主要作用是存储原链表的首元素或counter记录的有序链表；counter的作用是存储算法过程中通过合并或swap得到的有序链表组，并且这些链表组的并集等于原链表，且交集为空。具体算法流程如下：1、若原链表不为空，则从该链表读取首元素给carry；若原链表为空则跳4。2、判断此时是否第一次进入循环：若是，则链表carry调用swap(counter[0])，转存在counter[0]中，并执行fill++，跳转到2；若不是，则继续往下。3、判断counter[i]是否为空：若不为空，对链表counter[i]调用merge(carry)，将carry链表合并到counter[i]上，从而获得一个有序的子链表。然后对carry调用swap(counter[i++])，将该有序子链表交换给carry存储，跳转到3；若counter[i]为空，则对carry执行swap(counter[i])，将有序子链表存储在counter[fill++]，跳转1。4、遍历counter数组，每两个子链表依次进行merge操作，从而得到最终有序的链表。最后原链表this调用swap(counter[fill-1])获取最终有序的链表。注意，counter从低索引到高索引存储的链表元素的数量呈现2^i的趋势。

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

以上就是关于SGI版本STL中list容器的实现原理。其中主要介绍了链表节点的结构定义、list迭代器的定义以及list容器的各比较重要的函数实现。