一：List基础 List简介    list是一个双向链表容器，可高效地进行插入删除元素。    list不可以随机存取元素，所以不支持at.(pos)函数与[]操作符。It++(ok) it+5(err)   #include <list>   list对象的默认构造 list采用采用模板类实现,对象的默认构造形式：list<T> lstT;  如： list<int> lstInt;            //定义一个存放int的list容器。 list<float> lstFloat;     //定义一个存放float的list容器。 list<string> lstString;     //定义一个存放string的list容器。 ...                     //尖括号内还可以设置指针类型或自定义类型。 list头尾的添加移除操作     list.push_back(elem);       //在容器尾部加入一个元素     list.pop_back();              //删除容器中最后一个元素     list.push_front(elem);     //在容器开头插入一个元素     list.pop_front();              //从容器开头移除第一个元素     list<int> lstInt;     lstInt.push_back(1);     lstInt.push_back(3);     lstInt.push_back(5);     lstInt.push_back(7);     lstInt.push_back(9);     lstInt.pop_front();     lstInt.pop_front();     lstInt.push_front(11);     lstInt.push_front(13);     lstInt.pop_back();     lstInt.pop_back(); // lstInt    {13,11,5} list的数据存取    list.front();   //返回第一个元素。    list.back();  //返回最后一个元素。 list<int> lstInt;     lstInt.push_back(1);     lstInt.push_back(3);     lstInt.push_back(5);     lstInt.push_back(7);     lstInt.push_back(9);     int iFront = lstInt.front();    //1     int iBack = lstInt.back();        //9     lstInt.front() = 11;            //11     lstInt.back() = 19;            //19 list与迭代器     list.begin();                     //返回容器中第一个元素的迭代器。     list.end();                       //返回容器中最后一个元素之后的迭代器。     list.rbegin();         //返回容器中倒数第一个元素的迭代器。     list.rend();         //返回容器中倒数最后一个元素的后面的迭代器。     list<int> lstInt;     lstInt.push_back(1);     lstInt.push_back(3);     lstInt.push_back(5);     lstInt.push_back(7);     lstInt.push_back(9);     for (list<int>::iterator it=lstInt.begin(); it!=lstInt.end(); ++it)     {         cout << *it;         cout << " ";     }     for (list<int>::reverse_iterator rit=lstInt.rbegin(); rit!=lstInt.rend(); ++rit)     {         cout << *rit;         cout << " ";     } list对象的带参数构造     list(beg,end);    //构造函数将[beg, end)区间中的元素拷贝给本身。注意该区间是左闭右开的区间。     list(n,elem);   //构造函数将n个elem拷贝给本身。     list(const list &lst);  //拷贝构造函数。 list<int> lstIntA;     lstIntA.push_back(1);     lstIntA.push_back(3);     lstIntA.push_back(5);     lstIntA.push_back(7);     lstIntA.push_back(9);     list<int> lstIntB(lstIntA.begin(),lstIntA.end());        //1 3 5 7 9     list<int> lstIntC(5,8);                            //8 8 8 8 8     list<int> lstIntD(lstIntA);                        //1 3 5 7 9 list的赋值     list.assign(beg,end);    //将[beg, end)区间中的数据拷贝赋值给本身。注意该区间是左闭右开的区间。     list.assign(n,elem);  //将n个elem拷贝赋值给本身。     list& operator=(const list &lst);    //重载等号操作符     list.swap(lst);  // 将lst与本身的元素互换。     list<int> lstIntA,lstIntB,lstIntC,lstIntD;     lstIntA.push_back(1);     lstIntA.push_back(3);     lstIntA.push_back(5);     lstIntA.push_back(7);     lstIntA.push_back(9);     lstIntB.assign(lstIntA.begin(),lstIntA.end());        //1 3 5 7 9     lstIntC.assign(5,8);                            //8 8 8 8 8     lstIntD = lstIntA;                            //1 3 5 7 9     lstIntC.swap(lstIntD);                        //互换 list的大小     list.size();       //返回容器中元素的个数     list.empty();       //判断容器是否为空     list.resize(num);   //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。     list.resize(num, elem);  //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。     list<int> lstIntA;     lstIntA.push_back(1);     lstIntA.push_back(3);     lstIntA.push_back(5);     if (!lstIntA.empty())     {         int iSize = lstIntA.size();        //3         lstIntA.resize(5);            //1 3 5 0 0         lstIntA.resize(7,1);            //1 3 5 0 0 1 1         lstIntA.resize(2);            //1 3     } list的插入     list.insert(pos,elem);   //在pos位置插入一个elem元素的拷贝，返回新数据的位置。     list.insert(pos,n,elem);   //在pos位置插入n个elem数据，无返回值。     list.insert(pos,beg,end);   //在pos位置插入[beg,end)区间的数据，无返回值。     list<int> lstA;     list<int> lstB;     lstA.push_back(1);     lstA.push_back(3);     lstA.push_back(5);     lstA.push_back(7);     lstA.push_back(9);     lstB.push_back(2);     lstB.push_back(4);     lstB.push_back(6);     lstB.push_back(8);     lstA.insert(lstA.begin(), 11);        //{11, 1, 3, 5, 7, 9}     lstA.insert(++lstA.begin(),2,33);        //{11,33,33,1,3,5,7,9}     lstA.insert(lstA.begin() , lstB.begin() , lstB.end() );    //{2,4,6,8,11,33,33,1,3,5,7,9} list的删除     list.clear();        //移除容器的所有数据     list.erase(beg,end);  //删除[beg,end)区间的数据，返回下一个数据的位置。     list.erase(pos);    //删除pos位置的数据，返回下一个数据的位置。     lst.remove(elem);   //删除容器中所有与elem值匹配的元素。 删除区间内的元素 lstInt是用list<int>声明的容器，现已包含按顺序的1,3,5,6,9元素。 list<int>::iterator itBegin=lstInt.begin(); ++ itBegin; list<int>::iterator itEnd=lstInt.begin(); ++ itEnd; ++ itEnd; ++ itEnd; lstInt.erase(itBegin,itEnd); //此时容器lstInt包含按顺序的1,6,9三个元素。 假设 lstInt 包含1,3,2,3,3,3,4,3,5,3，删除容器中等于3的元素的方法一 for(list<int>::iterator it=lstInt.being(); it!=lstInt.end(); )    //小括号里不需写  ++it {    if(*it == 3)    {         it  =  lstInt.erase(it);       //以迭代器为参数，删除元素3，并把数据删除后的下一个元素位置返回给迭代器。          //此时，不执行  ++it；      }    else    {        ++it;    } } 删除容器中等于3的元素的方法二 lstInt.remove(3); 删除lstInt的所有元素 lstInt.clear();            //容器为空 list的反序排列     lst.reverse();     //反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。     list<int> lstA;          lstA.push_back(1);     lstA.push_back(3);     lstA.push_back(5);     lstA.push_back(7);     lstA.push_back(9);     lstA.reverse();            //9 7 5 3 1

二：List的源码 （转:http://blog.csdn.net/terence1212/article/details/52302501）

List的节点结构如下：

template <class T> struct __list_node { typedef void* void_pointer; void_pointer next; //型别为void*，也可以设为__list_node<T>* void_pointer prev; T data; }; 12345678

从节点结构可以看出，List就是一个双向链表

在Vector中，由于是连续的存储空间，支持随机存取，所以其迭代器可以直接用普通指针代替。但是，在List中行不通。List必须有能力指向List的节点，并有能力进行正确的递增、递减、取值和成员存取等操作。

List是一个双向链表，迭代器必须具备前移、后退的能力，所以List的迭代器是一个Bidirectional Iterator！在Vector中如果进行插入和删除操作后迭代器会失效，List有一个重要的性质就是插入和接合操作都不会造成原有的List迭代器失效。而且，再删除一个节点时，也仅有指向被删除元素的那个迭代器失效，其他迭代器不受任何影响。下面来看看List迭代器的源码。

template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_iterator<T, T&, T*> iterator; // 支持Iterator_traits typedef __list_iterator<T, const T&, const T*> const_iterator; typedef __list_iterator<T, Ref, Ptr> self; // 以下为支持Iterator_traits而定义的一些类型 typedef bidirectional_iterator_tag iterator_category; //List的迭代器类型为双向迭代器 typedef T value_type; typedef Ptr pointer; typedef Ref reference; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef __list_node<T>* link_type; // 这个是迭代器实际管理的资源指针 link_type node; // 迭代器构造函数 __list_iterator(link_type x) : node(x) {} __list_iterator() {} __list_iterator(const iterator& x) : node(x.node) {} // 在STL算法中需要迭代器提供支持 bool operator==(const self& x) const { return node == x.node; } bool operator!=(const self& x) const { return node != x.node; } // 重载operator *, 返回实际维护的数据 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; } } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263

List的迭代器实现了==,!=,++,–,取值和成员调用等操作，由于是存放在不连续的内存空间，所以并不支持vector那样的p+n的操作。

List的数据结构

List的数据结构个List的节点数据结构是分开定义的，SGI的List不仅是一个双向链表，而且还是一个环状双向链表，所以它只需要一个指针，就能完整表现一个链表。

template <class T, class Alloc = alloc> class list { protected: typedef void* void_pointer; typedef __list_node<T> list_node; // 这个提供STL标准的allocator接口 typedef simple_alloc<list_node, Alloc> list_node_allocator; // 链表的头结点，并不存放数据 link_type node; //....以下还有一堆List的操作函数 } 123456789101112131415

List构造函数

List提供了一个空构造函数，如下：

list() { empty_initialize(); } // 用于空链表的建立 void empty_initialize() { node = get_node(); node->next = node; // 前置节点指向自己 node->prev = node; // 后置节点指向自己 } 123456789

另外，List还提供了带参的构造函数，支持如下初始化操作：

List<int> myList(5,1); // 初始化5个1的链表，{1,1,1,1,1} 1

其构造函数源码如下：

// 带参构造函数 list(size_type n, const T& value) { fill_initialize(n, value); } // 创建值为value共n个结点的链表 void fill_initialize(size_type n, const T& value) { empty_initialize(); // 先创建一个空链表 insert(begin(), n, value); // 插入n个值为value的节点 } // 在指定位置插入n个值为x的节点 void insert(iterator pos, int n, const T& x) { insert(pos, (size_type)n, x); } // 在position前插入n个值为x的元素 template <class T, class Alloc> void list<T, Alloc>::insert(iterator position, size_type n, const T& x) { for ( ; n > 0; --n) insert(position, 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; } 1234567891011121314151617181920212223242526272829303132333435

STL的List提供了很多种构造函数，此处我列举了其中一个，以此为例。

List的其他操作函数

get_node

此函数用来配置一个节点。

// 配置一个节点并返回 link_type get_node() { return list_node_allocator::allocate(); } 1234

put_node

此函数用来释放一个节点。

// 释放指定结点, 不进行析构, 析构交给全局的destroy, void put_node(link_type p) { list_node_allocator::deallocate(p); } 1234

create_node

此函数用来配置并构造一个节点，并初始化其值

// 配置一个节点，并初始化其值为x link_type create_node(const T& x) { link_type p = get_node(); construct(&p->data, x); //全局函数 return p; } 1234567

destory_node

此函数用来析构一个节点。

// 析构结点元素, 并释放内存 void destroy_node(link_type p) { destroy(&p->data); //全局函数 put_node(p); } 123456

insert

此函数用来在制定位置插入一个节点(上面提到过这个函数，这里重复一下，List的主要插入工作都交给这个函数)，该函数是一个重载函数，其有多种形式。

// 好吧，到这里才是真正的插入操作 // 很简单的双向链表插入操作 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; } // 其还有如下多种形式的重载函数 // 在[first,last]区间内插入元素 template <class T, class Alloc> template <class InputIterator> void list<T, Alloc>::insert(iterator position, InputIterator first, InputIterator last) { for ( ; first != last; ++first) insert(position, *first); } // 在position位置插入元素，元素调用该型别默认构造函数 iterator insert(iterator position) { return insert(position, T()); } 12345678910111213141516171819202122

push_back

在尾部插入元素，有了上面的insert函数之后，push_back就比较容易实现了。

// 在链表最后插入结点 void push_back(const T& x) { insert(end(), x); } 12

pop_front

// 在链表前端插入结点 void push_front(const T& x) { insert(begin(), x); } 12

earse

移除迭代器所指的元素

// 擦除指定结点 iterator erase(iterator position) { // 双向链表移除节点的操作 link_type next_node = link_type(position.node->next); link_type prev_node = link_type(position.node->prev); prev_node->next = next_node; next_node->prev = prev_node; destroy_node(position.node); return iterator(next_node); } // 上述函数还有一个重载版本，移除区间内所有的节点 // 擦除[first, last)间的结点 template <class T, class Alloc> list<T, Alloc>::iterator list<T, Alloc>::erase(iterator first, iterator last) { while (first != last) erase(first++); return last; } 1234567891011121314151617181920

pop_front

移除头节点元素，有了上述的erase函数，就很方便的实现了。

// 删除链表第一个结点 void pop_front() { erase(begin()); } 12

pop_back

移除链表中最后一个元素

// 删除链表最后一个结点 void pop_back() { iterator tmp = end(); erase(--tmp); } 123456

clear

清除链表中的所有节点，也就是一个一个的清除

// 销毁所有结点, 将链表置空 template <class T, class Alloc> void list<T, Alloc>::clear() { link_type cur = (link_type) node->next; while (cur != node) { //遍历每一个节点 link_type tmp = cur; cur = (link_type) cur->next; destroy_node(tmp); } node->next = node;// 移除后注意要保持链表是一个循环链表 node->prev = node; } 12345678910111213

remove

将链表中值为value的节点移除

// 移除特定值的所有结点 // 时间复杂度O(n) template <class T, class Alloc> void list<T, Alloc>::remove(const T& value) { iterator first = begin(); iterator last = end(); while (first != last) { //保证链表非空 iterator next = first; ++next; if (*first == value) erase(first); //擦除该节点 first = next; } } 1234567891011121314

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

这里借用侯捷先生的《STL源码剖析》中的一幅图来说明这个过程。

splice

List提供的接合函数是Splice，上述transfer是非公开的函数。splice函数有如下几个版本:

// 将链表x移动到position之前 void splice(iterator position, list& x) { if (!x.empty()) transfer(position, x.begin(), x.end()); //仅仅调用了transfer函数 } // 将链表中i指向的内容移动到position之前 void splice(iterator position, list&, iterator i) { iterator j = i; ++j; if (position == i || position == j) return; transfer(position, i, j); } // 将[first, last}元素移动到position之前 void splice(iterator position, list&, iterator first, iterator last) { if (first != last) transfer(position, first, last); } 12345678910111213141516171819202122

merge

此函数用来合并两个链表，这里两个链表必须是已拍好序的。

// 假设当前容器和x都已序, 保证两容器合并后仍然有序 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(); while (first1 != last1 && first2 != last2) if (*first2 < *first1) { iterator next = first2; transfer(first1, first2, ++next); //将first2节点迁移到first1之后 first2 = next; } else ++first1; if (first2 != last2) transfer(last1, first2, last2); //如果first2还有剩余的，直接接合再链表1尾部 } 123456789101112131415161718

reverse

此函数用来反转链表，其具体实现如下：

// 将链表倒置 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); // 插入到begin()之后 } } 12345678910111213

sort

此函数对链表进行升序排序，具体实现如下：

// 按照升序排序 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; // 把carry中的新元素和counter中的结果逐一进行归并 while (i < fill && !counter[i].empty()) { counter[i].merge(carry); carry.swap(counter[i++]); } // 把归并后的结果存放在counter[i]中 carry.swap(counter[i]); // 已经达到2*fill，fill自增1 if (i == fill) ++fill; } // 将counter中的所有元素进行归并 for (int i = 1; i < fill; ++i) counter[i].merge(counter[i - 1]); // 将counter链表和本链表进行交换 swap(counter[fill - 1]); } // 交换本链表和链表x void swap(list<T, Alloc>& x) { swap(node, x.node); } 1234567891011121314151617181920212223242526272829303132

这里可以举个例子来说明一下这个过程：(以链表5,3,6,4,7,9,1,2,8)

carry每次从数组中取一个数，然后归并到counter数组中，该算法最多只能排序2的64次方个数。