STL - list

C/C++

链表也即链式表，在数据结构中，我们知道线性表的物理存储结构有两种，顺序表(数组)和链式表(结点)。链表是在堆中为每一个元素分配内存，然后利用指针将所有元素串起来。根据这种物理存储结构，我们很容易明白：链表在插入、删除效率上比较高，但没有办法随机访问，因此访问速度慢。

特点

插入、删除效率较高

#include <list>
using namespace std;

构造函数

// constructors used in the same order as described above:
list<int> first;       // empty list of ints
list<int> second (4,100);       // four ints with value 100
list<int> third (second.begin(),second.end());  // iterating through second
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};
list<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

cout << "The contents of fifth are: ";
for (list<int>::iterator it = fifth.begin(); it != fifth.end(); it++)
cout << *it << ' ';

cout << '\n';

迭代器

list<int>::iterator it;
list<int>::reverse_iterator rit;
it = second.begin();
it = second.end();
rit = second.rbegin();
rit = second.rend();

容器大小

cout << second.empty() << endl;
cout << second.size() << endl;
cout << second.max_size() << endl;

元素操作

second.push_back(20);
second.pop_back();
second.push_front(30);
second.pop_front();

second.insert(second.begin(), 40);
second.insert(second.begin(), 2, 200);   //插入2个200
second.insert(second.begin(), third.begin(), third.end());

second.erase(second.begin());
second.erase(second.begin(), second.end());

second.swap(third);
second.resize(10);
second.clear();

 所有的插入操作都是插入到iterator指向的元素之前

其它操作

由于list是链式存储，因此不能随机访问，也即不支持索引访问。

//链表拼接
std::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 4

for (int i = 1; i <= 3; ++i)
    mylist2.push_back(i * 10);   // mylist2: 10 20 30

it = mylist1.begin();
it++;

//将mylist2拼接到mylist1的it指向元素前面
mylist1.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);

//删除（根据元素值删除，而不是iterator）
mylist2.remove(20);

//去除重复元素，必须是针对已经排序过的，因为这里只是去除连续重复的元素
mylist2.sort();
mylist2.unique();

mylist1.sort();
mylist1.merge(mylist2);   
//merge与splice一样，合并过后，mylist2为空
//同时，合并之前必须对各个list进行排序

mylist1.reverse();  //使得mylist1各个元素逆向