STL 之 list

list 由双向链表实现，下面主要介绍 STL list 的一些操作。

说明：未给出的例子和函数声明请参见 http://www.cplusplus.com/reference/

实现：bits/stl_list.h, bits_stl/list.tcc (libstdc++ or include/c++)

1. 构造函数, assign(), size(), max_size(), resize()

1. 构造函数

explicit list (const allocator_type& alloc = allocator_type());

explicit list (size_type n, const value_type& val = value_type(),
                const allocator_type& alloc = allocator_type());

template <class InputIterator>
list (InputIterator first, InputIterator last,
        const allocator_type& alloc = allocator_type());

list (const list& x);

第四个为拷贝构造函数，其余三个除了

alloc 参数，其它见例子程序。关于 alloc 参数，先看 list 的类模板参数：

template < class T, class Alloc = allocator<T> > class list;

即通过类模板参数指定分配器类型，再通过构造函数参数指定分配器对象。

注意：这里的类模板参数和构造函数参数都有默认值，理清二者的区别和联系。（同前面博文中的deque）

默认分配器对象为 std::allocator, 详细见 g++ bits/stl_list.h

2. assign()

emplate <class InputIterator>
void assign (InputIterator first, InputIterator last);

void assign (size_type n, const value_type& val);

跟构造函数类似，注意一点：

老数据全部丢失

3. max_size()

list 能容纳的最大元素个数，这个值取决于系统或库的实现。当然，并不能保证程序在运行时就一定能达到这个值，比如运行过程中内存不足。

size()

4. resize()

void resize (size_type n, value_type val = value_type());

减少或增加 list 的元素个数至

size_type n, 如果不指定 val, 则取默认值，如 int 默认值为 0, 类似构造函数和 assign().

2. front(), back(), begin(), end()

1. front(), back() 返回的是引用，而 begin(), end() 返回的是迭代器（指针），见函数声明。

2. back() 指向最后一个元素，而 end() 指向最后一个元素的后面一位，用于判断是否是末端。

3. insert(), erase(), remove(), remove_if(), unique()

1. insert()

只需注意一点：插入的元素位于给定的迭代器指向的元素之前（Inserts given value into %list before specified iterator）。

2. remove(), remove_if(), erase()

erase() 是用迭代器指定节点进行删除， remove() 是按值（operator==）相等删除， remove_if() 是指定条件删除。

3. unique()

void unique();

template <class BinaryPredicate>
void unique (BinaryPredicate binary_pred);

删除重复的元素，只保留第一个。要么按照

operator== 处理，要么按照 binary_pred 指定的规则。

4. sort()

void sort();

template <class Compare>
void sort (Compare comp);

1. 如果不指定比较规则，则默认使用 

operator<, 排序结果为 升序；如果指定则按指定规则进行。

2. Sorts the elements of this list in NlogN

5. splice(), merge()

1. splice()

splice() 是从指定的位置拼接，不考虑顺序（注意：不是 split）；

2. merge()

void merge (list& x);

template <class Compare>
void merge (list& x, Compare comp);

1. 如果两个 list 均已排序，则合并后的 list 也按照同样的规则有序。规则要么是默认的

operator<, 要么是指定的（同 sort()）。如果无序，则合并之后也无序，这种情况下同 splice().

2. 对于相等的元素 this 的在前， x

3. 操作完成胡 x

4. The function does nothing if (&x == this).

6. swap(), reverse()

swap(): 交换两个 list(见例子)，这个方法有两个版本，一个是成员函数，一个是非成员函数

reverse(): 反转 list

7. 重载关系比较操作（非成员函数）

和前面博文中介绍的 deque 一样（），这个比较规则为 lexicographical_compare().