C++/C++11中std::list双向链表的使用

std::list是双向链表，是一个允许在序列中任何一处位置以常量耗时插入或删除元素且可以双向迭代的顺序容器。std::list中的每个元素保存了定位前一个元素及后一个元素的信息，允许在任何一处位置以常量耗时进行插入或删除操作，但不能进行直接随机访问。

std::list和std::forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问：为了访问一个元素，我们只能遍历整个容器。而且与vector、deque和array相比，这两个容器的额外内存开销也很大。

std::list与std::forward_list相比，它提供双向迭代的能力，但具有更低的空间效率。

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions.

List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it.

They are very similar to forward_list: The main difference being that forward_list objects are single-linked lists, and thus they can only be iterated forwards, in exchange for being somewhat smaller and more efficient.

Compared to other base standard sequence containers (array, vector and deque), lists perform generally better in inserting, extracting and moving elements in any position within the container for which an iterator has already been obtained,and therefore also in algorithms that make intensive use of these, like sorting algorithms.

The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position.

一个容器就是一些特定类型对象的集合。顺序容器(sequential container)为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的位置相对应。

标准库中的顺序容器包括：

(1)、vector：可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。

(2)、deque：双端队列。支持快速随机访问。在头尾位置插入/删除速度很快。

(3)、list：双向链表。只支持双向顺序访问。在list中任何位置进行插入/删除操作速度都很快。

(4)、forward_list：单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快。

(5)、array：固定大小数组。支持快速随机访问。不能添加或删除元素。

(6)、string：与vector相似的容器，但专门用于保存字符。随机访问快。在尾部插入/删除速度快。

除了固定大小的array外，其它容器都提供高效、灵活的内存管理。我们可以添加和删除元素，扩张和收缩容器的大小。容器保存元素的策略对容器操作的效率有着固定的，有时是重大的影响。在某些情况下，存储策略还会影响特定容器是否支持特定操作。

例如，string和vector将元素保存在连续的内存空间中。由于元素是连续存储的，由元素的下标来计算其地址是非常快速的。但是，在这两种容器的中间位置添加或删除元素就会非常耗时：在一次插入或删除操作后，需要移动插入/删除位置之后的所有元素，来保持连续存储。而且，添加一个元素有时可能还需要分配额外的存储空间。在这种情况下，每个元素都必须移动到新的存储空间中。

list和forward_list两个容器的设计目的是令容器任何位置的添加和删除操作都很快速。作为代价，这两个容器不支持元素的随机访问：为了访问一个元素，我们只能遍历整个容器。而且，与vector、deque和array相比，这两个容器的额外内存开销也很大。

deque是一个更为复杂的数据结构。与string和vector类似，deque支持快速的随机访问。与string和vector一样，在deque的中间位置添加或删除元素的代价(可能)很高。但是，在deque的两端添加或删除元素都是很快的，与list或forward_list添加删除元素的速度相当。

forward_list和array是新C++标准增加的类型。与内置数组相比，array是一个种更安全、更容易使用的数组类型。与内置数组类似，array对象的大小是固定的。因此，array不支持添加和删除元素以及改变容器大小的操作。forward_list的设计目标是达到与最好的手写的单向链表数据结构相当的性能。因此，forward_list没有size操作，因为保存或计算其大小就会比手写链表多出额外的开销。对其他容器而言，size保证是一个快速的常量时间的操作。

通常，使用vector是最好的选择，除法你有很好的理由选择其他容器。

以下是一些选择容器的基本原则：

(1)、除法你有很好的理由选择其他容器，否则应该使用vector；

(2)、如果你的程序有很多小的元素，且空间的额外开销很重要，则不要使用list或forward_list；

(3)、如果程序要求随机访问元素，应使用vector或deque；

(4)、如果程序要求在容器的中间插入或删除元素，应使用list或forward_list；

(5)、如果程序需要在头尾位置插入或删除元素，但不会在中间位置进行插入或删除操作，则使用deque；

(6)、如果程序只有在读取输入时才需要在容器中间位置插入元素，随后需要随机访问元素，则：首先，确定是否真的需要在容器中间位置添加元素。当处理输入数据时，通常可以很容器地向vector追加数据，然后再调用标准库的sort函数来重排容器中的元素，从而避免在中间位置添加元素。如果必须在中间位置插入元素，考虑在输入阶段使用list，一旦输入完成，将list中的内容拷贝到一个vector中。

如果你不确定应该使用哪种容器，那么可以在程序中只使用vector和list公共的操作：使用迭代器，不使用下标操作，避免随机访问。这样，在必要时选择使用vector或list都很方便。

一般来说，每个容器都定义在一个头文件中，文件名与类型名相同。即，deque定义在头文件deque中，list定义在头文件list中，以此类推。容器均定义为模板类。

顺序容器几乎可以保存任意类型的元素。特别是，我们可以定义一个容器，其元素的类型是另一个容器。这种容器的定义与任何其他容器类型完全一样：在尖括号中指定元素类型(此种情况下，是另一种容器类型)。

除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue和priority_queue。适配器(adaptor)是标准库中的一个通用概念。容器、迭代器和函数都有适配器。本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。

下面是从其他文章中copy的std::list测试代码，详细内容介绍可以参考对应的reference：

#include "list.hpp"
#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <cmath>//
// reference: http://www.cplusplus.com/reference/list/list/
// compare only integral part:
static bool mycomparison(double first, double second)
{return (int(first)<int(second));
}// comparison, not case sensitive.
static bool compare_nocase(const std::string& first, const std::string& second)
{unsigned int i = 0;while ((i<first.length()) && (i<second.length())) {if (tolower(first[i])<tolower(second[i])) return true;else if (tolower(first[i])>tolower(second[i])) return false;++i;}return (first.length() < second.length());
}// a predicate implemented as a function:
static bool single_digit(const int& value) { return (value<10); }// a predicate implemented as a class:
struct is_odd {bool operator() (const int& value) { return (value % 2) == 1; }
};// a binary predicate implemented as a function:
static 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 test_list_1()
{
{ // list::list: Constructs a list container object, initializing its contents depending on the constructor version usedstd::list<int> first;                                // empty list of intsstd::list<int> second(4, 100);                       // four ints with value 100std::list<int> third(second.begin(), second.end());  // iterating through secondstd::list<int> fourth(third);                       // a copy of third// the iterator constructor can also be used to construct from arrays:int myints[] = { 16, 2, 77, 29 };std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int));std::cout << "The contents of fifth are: ";for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)std::cout << *it << ' ';std::cout << '\n';
}{ // list::assign: Assigns new contents to the list container, replacing its current contents, and modifying its size accordingly// list::size: Returns the number of elements in the list container.std::list<int> first;std::list<int> second;first.assign(7, 100);                      // 7 ints with value 100second.assign(first.begin(), first.end()); // a copy of firstint myints[] = { 1776, 7, 4 };first.assign(myints, myints + 3);            // assigning from arraystd::cout << "Size of first: " << int(first.size()) << '\n';std::cout << "Size of second: " << int(second.size()) << '\n';
}{ // list::back: Returns a reference to the last element in the list container// list::front: Returns a reference to the first element in the list container.std::list<int> mylist;mylist.push_back(10);while (mylist.back() != 0) {mylist.push_back(mylist.back() - 1);}std::cout << "mylist contains:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';mylist.push_back(77);mylist.push_back(22);mylist.front() -= mylist.back();std::cout << "mylist.front() is now " << mylist.front() << '\n';}{ // list::begin: Returns an iterator pointing to the first element in the list container// list::cbegin: C++11, Returns a const_iterator pointing to the first element in the container// list::crbegin: C++11, Returns a const_reverse_iterator pointing to the last element in the container (i.e., its reverse beginning)// list::rbegin: Returns a reverse iterator pointing to the last element in the container (i.e., its reverse beginning).// list::end: Returns an iterator referring to the past-the-end element in the list container// list::cend: C++11, Returns a const_iterator pointing to the past-the-end element in the container// list::crend: C++11, Returns a const_reverse_iterator pointing to the theoretical element// preceding the first element in the container (which is considered its reverse end)// list::rend: Returns a reverse iterator pointing to the theoretical element preceding the first element// in the list container (which is considered its reverse end).int myints[] = { 75, 23, 65, 42, 13 };std::list<int> mylist(myints, myints + 5);std::cout << "mylist contains:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';for (auto it = mylist.cbegin(); it != mylist.cend(); ++it)std::cout << ' ' << *it;std::cout << '\n';for (auto rit = mylist.crbegin(); rit != mylist.crend(); ++rit)std::cout << ' ' << *rit;std::cout << '\n';std::cout << "mylist backwards:";for (std::list<int>::reverse_iterator rit = mylist.rbegin(); rit != mylist.rend(); ++rit)std::cout << ' ' << *rit;std::cout << '\n';
}{ // list::clear: Removes all elements from the list container (which are destroyed),// and leaving the container with a size of 0std::list<int> mylist;std::list<int>::iterator it;mylist.push_back(100);mylist.push_back(200);mylist.push_back(300);std::cout << "mylist contains:";for (it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';mylist.clear();mylist.push_back(1101);mylist.push_back(2202);std::cout << "mylist contains:";for (it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';
}{ // list::emplace: C++11, The container is extended by inserting a new element at position.// This new element is constructed in place using args as the arguments for its construction.// list::emplace_back: C++11, Inserts a new element at the end of the list, right after its current last element.// This new element is constructed in place using args as the arguments for its construction.// list::emplace_front: Inserts a new element at the beginning of the list, right before its current first element.// This new element is constructed in place using args as the arguments for its construction.std::list< std::pair<int, char> > mylist;mylist.emplace(mylist.begin(), 100, 'x');mylist.emplace(mylist.begin(), 200, 'y');std::cout << "mylist contains:";for (auto& x : mylist)std::cout << " (" << x.first << "," << x.second << ")";std::cout << '\n';mylist.emplace_back(10, 'a');mylist.emplace_back(20, 'b');mylist.emplace_back(30, 'c');std::cout << "mylist contains:";for (auto& x : mylist)std::cout << " (" << x.first << "," << x.second << ")";std::cout << std::endl;mylist.emplace_front(10, 'a');mylist.emplace_front(20, 'b');mylist.emplace_front(30, 'c');std::cout << "mylist contains:";for (auto& x : mylist)std::cout << " (" << x.first << "," << x.second << ")";std::cout << std::endl;
}{ // list::empty: Returns whether the list container is empty (i.e. whether its size is 0).std::list<int> mylist;int sum(0);for (int i = 1; i <= 10; ++i) mylist.push_back(i);while (!mylist.empty()) {sum += mylist.front();mylist.pop_front();}std::cout << "total: " << sum << '\n';
}{ // list::erase: Removes from the list container either a single element (position) or a range of elements ([first,last)).std::list<int> mylist;std::list<int>::iterator it1, it2;// set some values:for (int i = 1; i<10; ++i) mylist.push_back(i * 10);// 10 20 30 40 50 60 70 80 90it1 = it2 = mylist.begin(); // ^^std::advance(it2, 6);            // ^                 ^++it1;                      //    ^              ^it1 = mylist.erase(it1);   // 10 30 40 50 60 70 80 90//    ^           ^it2 = mylist.erase(it2);   // 10 30 40 50 60 80 90//    ^           ^++it1;                      //       ^        ^--it2;                      //       ^     ^mylist.erase(it1, it2);     // 10 30 60 80 90//        ^std::cout << "mylist contains:";for (it1 = mylist.begin(); it1 != mylist.end(); ++it1)std::cout << ' ' << *it1;std::cout << '\n';
}{ // list::get_allocator: Returns a copy of the allocator object associated with the list containerstd::list<int> mylist;int * p;// allocate an array of 5 elements using mylist's allocator:p = mylist.get_allocator().allocate(5);// assign some values to arrayfor (int i = 0; i<5; ++i) p[i] = i;std::cout << "The allocated array contains:";for (int i = 0; i<5; ++i) std::cout << ' ' << p[i];std::cout << '\n';mylist.get_allocator().deallocate(p, 5);
}{ // list::insert: The container is extended by inserting new elements before the element at the specified positionstd::list<int> mylist;std::list<int>::iterator it;// set some initial values:for (int i = 1; i <= 5; ++i) mylist.push_back(i); // 1 2 3 4 5it = mylist.begin();++it;           // it points now to number 2           ^mylist.insert(it, 10);                        // 1 10 2 3 4 5// "it" still points to number 2                      ^mylist.insert(it, 2, 20);                      // 1 10 20 20 2 3 4 5--it;         // it points now to the second 20            ^std::vector<int> myvector(2, 30);mylist.insert(it, myvector.begin(), myvector.end());// 1 10 20 30 30 20 2 3 4 5//               ^std::cout << "mylist contains:";for (it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';
}{ // list::max_size: Returns the maximum number of elements that the list container can hold.// list::resize: Resizes the container so that it contains n elements// list::size_type: A type that counts the number of elements in a list.unsigned int i;std::list<int> mylist;i = 111111;if (i<mylist.max_size()) mylist.resize(i);else std::cout << "That size exceeds the limit.\n";std::list <int>::size_type ii;ii = mylist.max_size();std::cout << "Maximum possible length of the list is " << ii << "." << std::endl;
}{ // list::merge: Merges x into the list by transferring all of its elements at their respective ordered positions// into the container (both containers shall already be ordered).std::list<double> first, second;first.push_back(3.1);first.push_back(2.2);first.push_back(2.9);second.push_back(3.7);second.push_back(7.1);second.push_back(1.4);first.sort();second.sort();first.merge(second);// (second is now empty)second.push_back(2.1);first.merge(second, mycomparison);std::cout << "first contains:";for (std::list<double>::iterator it = first.begin(); it != first.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';
}{ // list::sort: Sorts the elements in the list, altering their position within the containerstd::list<std::string> mylist;std::list<std::string>::iterator it;mylist.push_back("one");mylist.push_back("two");mylist.push_back("Three");mylist.sort();std::cout << "mylist contains:";for (it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';mylist.sort(compare_nocase);std::cout << "mylist contains:";for (it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';
}{ // list::operator=: Assigns new contents to the container, replacing its current contents, and modifying its size accordingly.std::list<int> first(3);      // list of 3 zero-initialized intsstd::list<int> second(5);     // list of 5 zero-initialized intssecond = first;first = std::list<int>();std::cout << "Size of first: " << int(first.size()) << '\n';std::cout << "Size of second: " << int(second.size()) << '\n';
}{ // list::push_back: Adds a new element at the end of the list container, after its current last element.// list::push_front: Inserts a new element at the beginning of the list, right before its current first element.// list::pop_back: Removes the last element in the list container, effectively reducing the container size by one.// list::pop_front: Removes the first element in the list container, effectively reducing its size by onstd::list<int> mylist;int sum(0);mylist.push_back(100);mylist.push_back(200);mylist.push_back(300);while (!mylist.empty()) {sum += mylist.back();mylist.pop_back();}std::cout << "The elements of mylist summed " << sum << '\n';mylist.push_back(100);mylist.push_back(200);mylist.push_back(300);mylist.push_front(200);mylist.push_front(300);std::cout << "Popping out the elements in mylist:";while (!mylist.empty()) {std::cout << ' ' << mylist.front();mylist.pop_front();}std::cout << "\nFinal size of mylist is " << mylist.size() << '\n';
}{ // list::remove: Removes from the container all the elements that compare equal to val.// This calls the destructor of these objects and reduces the container size by the number of elements removed.// list::remove_if: Removes from the container all the elements for which Predicate pred returns true.// This calls the destructor of these objects and reduces the container size by the number of elements removed.int myints[] = { 89, 15, 36, 7, 17, 20, 39, 4, 1 };std::list<int> mylist(myints, myints + 9);mylist.remove(89);std::cout << "mylist contains:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';mylist.remove_if(single_digit);           // 15 36 17 20 39mylist.remove_if(is_odd());               // 36 20std::cout << "mylist contains:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';
}{ // list::reverse: reverses the order of the elements in the list container.std::list<int> mylist;for (int i = 1; i<10; ++i) mylist.push_back(i);mylist.reverse();std::cout << "mylist contains:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';
}{ // list::splice: Transfers elements from x into the container, inserting them at positionstd::list<int> mylist1, mylist2;std::list<int>::iterator it;// set some initial values:for (int i = 1; i <= 4; ++i)mylist1.push_back(i);      // mylist1: 1 2 3 4for (int i = 1; i <= 3; ++i)mylist2.push_back(i * 10);   // mylist2: 10 20 30it = mylist1.begin();++it;                         // points to 2mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// "it" still points to 2 (the 5th element)mylist2.splice(mylist2.begin(), mylist1, it);// mylist1: 1 10 20 30 3 4// mylist2: 2// "it" is now invalid.it = mylist1.begin();std::advance(it, 3);           // "it" points now to 30mylist1.splice(mylist1.begin(), mylist1, it, mylist1.end());// mylist1: 30 3 4 1 10 20std::cout << "mylist1 contains:";for (it = mylist1.begin(); it != mylist1.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';std::cout << "mylist2 contains:";for (it = mylist2.begin(); it != mylist2.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';
}{ // list::swap: Exchanges the content of the container by the content of x,// which is another list of the same type. Sizes may differ.std::list<int> first(3, 100);   // three ints with a value of 100std::list<int> second(5, 200);  // five ints with a value of 200first.swap(second);std::swap(first, second);std::cout << "first contains:";for (std::list<int>::iterator it = first.begin(); it != first.end(); it++)std::cout << ' ' << *it;std::cout << '\n';std::cout << "second contains:";for (std::list<int>::iterator it = second.begin(); it != second.end(); it++)std::cout << ' ' << *it;std::cout << '\n';
}{ // list::unique: Remove duplicate valuesdouble 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.35mylist.unique();           //  2.72,  3.14, 12.15, 12.77// 15.3,  72.25, 73.0,  73.35mylist.unique(same_integral_part);  //  2.72,  3.14, 12.15// 15.3,  72.25, 73.0mylist.unique(is_near());           //  2.72, 12.15, 72.25std::cout << "mylist contains:";for (std::list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';
}{ // Performs the appropriate comparison operation between the list containers lhs and rhsstd::list<int> a = { 10, 20, 30 };std::list<int> b = { 10, 20, 30 };std::list<int> c = { 30, 20, 10 };if (a == b) std::cout << "a and b are equal\n";if (b != c) std::cout << "b and c are not equal\n";if (b<c) std::cout << "b is less than c\n";if (c>b) std::cout << "c is greater than b\n";if (a <= b) std::cout << "a is less than or equal to b\n";if (a >= b) std::cout << "a is greater than or equal to b\n";
}return 0;
}//
// reference: https://msdn.microsoft.com/en-us/library/802d66bt.aspx
int test_list_2()
{using namespace std;// Create an empty list c0  list <int> c0;// Create a list c1 with 3 elements of default value 0  list <int> c1(3);// Create a list c2 with 5 elements of value 2  list <int> c2(5, 2);// Create a list c3 with 3 elements of value 1 and with the   // allocator of list c2  list <int> c3(3, 1, c2.get_allocator());// Create a copy, list c4, of list c2  list <int> c4(c2);// Create a list c5 by copying the range c4[ first,  last)  list <int>::iterator c4_Iter = c4.begin();c4_Iter++;c4_Iter++;list <int> c5(c4.begin(), c4_Iter);// Create a list c6 by copying the range c4[ first,  last) and with   // the allocator of list c2  c4_Iter = c4.begin();c4_Iter++;c4_Iter++;c4_Iter++;list <int> c6(c4.begin(), c4_Iter, c2.get_allocator());cout << "c1 =";for (auto c : c1)cout << " " << c;cout << endl;cout << "c2 =";for (auto c : c2)cout << " " << c;cout << endl;cout << "c3 =";for (auto c : c3)cout << " " << c;cout << endl;cout << "c4 =";for (auto c : c4)cout << " " << c;cout << endl;cout << "c5 =";for (auto c : c5)cout << " " << c;cout << endl;cout << "c6 =";for (auto c : c6)cout << " " << c;cout << endl;// Move list c6 to list c7  list <int> c7(move(c6));cout << "c7 =";for (auto c : c7)cout << " " << c;cout << endl;// Construct with initializer_list  list<int> c8({ 1, 2, 3, 4 });cout << "c8 =";for (auto c : c8)cout << " " << c;cout << endl;return 0;
}

GitHub： https://github.com/fengbingchun/Messy_Test