STL中list和我们传统意义上的链表一样可以进行动态节点添加和释放.

优点:适合动态删除和添加

缺点:不支持随机访问.

 

C++标准对list模板声明:

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

 

1)list的构造有多种方式和vector差不多,如下:

list<int > first;

list<int > second(4,100);

list<int > third( second.begin (),second. end());

list<int > fourth( third);

 

int myints [] = {16,2,77,29};

list<int > fifth ( myints, myints + sizeof( myints) / sizeof (int) );

 

2)list的内存分配方式(以vs2008中为例).

list不管以什么方式初始化,它总是会先分配一个头节点,节点内容为空, 并且头结点的前一个节点指向最后一个节点, 最后一个节点指向头节点.

以后不管是以insert, push_back, push_front插入数据,list都会使用std::allocator<T>分配器进行重新内存分配.

进行pop_front, pop_back, erase, clear, resize, assign删除的节点内存都会被释放掉.这和vector不太一样.

 

3)list成员函数splice是从一个list中移动元素到另一list中;

程序1:

输出:

splice操作是将一个list的中的元素直接拼接到另一list中,并不会重新申请释放内存.

 

4)list成员函数sort是将list中的元素进行排序(默认为升序),允许用户自定义比较规则.

在vs下我们看到排序使用了非递归的归并排序,使用了一个数组来保存中间序列最后遍历整个数组,将所有序列合并.

 

5)list成员函数reverse是对list进行翻转.成员函数 unique只能去除相邻的相同元素, 因此如果要去除相同元素最好保证list有序.

 

6)由于list适合添加和删除元素,list提供了remove和remove_if函数移除指定的元素.

程序:

输出:

 

总结:容器list适合频繁添加和删除元素情况.