本文主要借助对C++的标准模板库STL中实现的数据结构的学习和使用来加深对数据结构的理解，即联系数据结构的理论分析和详细的应用实现（STL），本文是系列总结的第二篇。主要针对线性表中的链表
STL std::list进行分析和总结。
因为前段时间对台大的机器学习基石和技法课程进行了学习，发如今详细的实现中经常涉及到各种类型的数据结构，比方线性表、二叉树、图等。在使用这些数据结构时感到有些吃力，主要是对一些主要的数据结构理解的不够，所以趁着暑假假期，近期一段时间总会抽出时间复习一下数据结构，參考的教材是王立柱编著的《C/C++与数据结构》，在详细的应用中採用的是C++标准模板库STL中相应实现的数据结构，主要參考的是MSDN文档。跟着教材的一步一步推进。如今已经复习完了链表一章节。详细的理论能够參看我的博文：
本次关注点在list模板类的使用。
回想动态数组类
上一篇总结STL vector动态数组类的时候忘记了对还有一种跟vector很类似的动态数组类deque进行说明。以下对此进行一下补充。
STL deque类须要包括&deque&和使用std。支持在数组的开头和末尾插入或删除元素，而vector仅仅能在末尾插入或删除，即仅仅有push_back和pop_back。deque同意使用push_front和pop_front在开头插入和删除元素。其余的操作大致类似，不再赘述！
template &
class Type,
class Allocator=allocator&Type&
class deque
&span style=&font-size:18&&// deque_push_front.cpp
// compile with: /EHsc
#include &deque&
#include &iostream&
#include &string&
int main( )
deque &int& c1;
c1.push_front( 1 );
if ( c1.size( ) != 0 )
cout && &First element: & && c1.front( ) &&
c1.push_front( 2 );
if ( c1.size( ) != 0 )
cout && &New first element: & && c1.front( ) &&
// move initialize a deque of strings
deque &string& c2;
string str(&a&);
c2.push_front( move( str ) );
cout && &Moved first element: & && c2.front( ) &&
}&/span&总结：在不知道须要存储多少个元素时，务必使用动态数组vector或deque。并牢记vector仅仅能使用push_back在一端扩容，而deque能够使用push_back和push_front在两端扩容。另外。訪问动态数组时，不要跨越其边界。
list 模板类
标准模板库以模板类std::list的方式向程序猿提供了一个双向链表。双向链表的主要长处是插入和删除元素的速度快，且时间固定，不像顺序表那样须要移动元素。从C++ 11起，还能够使用单向链表std::forward_list，仅仅沿着一个方向遍历。
template &
class Type,
class Allocator=allocator&Type&
class list
list的特点
链表是一系列节点，每一个节点除了包括对象或data之外，还包括指向下一个或者上一个节点的指针。list类的STL实现同意在开头、末尾和中间插入元素，且所需的时间固定。使用时包括&list&和std。
list的基本操作
list&int& listI list&float& listF等等。要声明一个指向list中元素的迭代器，能够进行例如以下操作：
list&int& :: const_iterator iElementInS 还记得const_iterator吧，在上一篇vector的分析中讲到过。指向一个仅仅读的元素，假设要对容器中的内容进行改动，能够使用iterator来进行。另一些与vector一样的初始化操作，能够參考上一篇博文，兴许关于STL容器进行编程或者解说时。实例化的方式大致一样。这样的模式也将长期出现，兴许博文便不再多提。
在list开头或末尾插入或删除元素
跟deque类相似。採用push_front/pop_front和push_back/pop_back的方法。
在list中间插入或删除元素
list的特点之中的一个。上面讲过。在中间插入或删除元素所需的时间是固定的，使用函数insert()和erase()。
从上面的分析看，基本上全部的容器类（vector。list，deque...）所使用的方法模式都类似，这对于触类旁通的学习非常有帮助。
list元素的反转和排序
list的一个独到之处就是指向元素的迭代器在list的元素又一次排列或插入元素后仍然有效，为实现这样的特点，list提供了成员方法sort和reverse。尽管STL也提供了这两种算法（在算法类中&algorithm&）。且这些算法相同能够使用在list类上。
使用reverse()反转元素的顺序排列
list提供了成员函数reverse，没有參数，功能是反转list中元素的排列顺序：
&span style=&font-size:18&&// list_reverse.cpp
// compile with: /EHsc
#include &list&
#include &iostream&
int main( )
list &int& c1;
list &int&::iterator c1_I
c1.push_back( 10 );
c1.push_back( 20 );
c1.push_back( 30 );
cout && &c1 =&;
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && & & && *c1_I
c1.reverse( );
cout && &Reversed c1 =&;
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && & & && *c1_I
}&/span&输出结果：
c1 = 10 20 30
Reversed c1 = 30 20 10
使用sort()对元素进行排序
list成员函数sort有两个版本号。一是没有參数，默认是升序排列。假设想降序排列，能够升序后採用reverse。还有一个版本号是接受一个二元谓词函数作为參数。制定排序的标准。比方以下一个二元谓词函数GeaterThan，指定的排序标准是降序排列
bool GeaterThan(const int& lsh, const int& rsh)
return(lsh & rsh);
&span style=&font-size:18&&// list_sort.cpp
// compile with: /EHsc
#include &list&
#include &iostream&
int main( )
list &int& c1;
list &int&::iterator c1_I
c1.push_back( 20 );
c1.push_back( 10 );
c1.push_back( 30 );
cout && &Before sorting: c1 =&;
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && & & && *c1_I
c1.sort( );
cout && &After sorting c1 =&;
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && & & && *c1_I
c1.sort( greater&int&( ) );
cout && &After sorting with 'greater than' operation, c1 =&;
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && & & && *c1_I
}&/span&输出为：
Before sorting: c1 = 20 10 30
After sorting c1 = 10 20 30
After sorting with 'greater than' operation, c1 = 30 20 10
对包括对象的list进行排序及删除当中的元素
在实际应用非常少使用STL容器来存储整数，而是存储用户自定义的类型，比方类或结构等。那么这样的排序怎样做呢?比方list中存储的是电话簿，当中每一个元素都是一个对象，包括名称、地址等内容，怎样确保能依照名称对其进行排序呢？
答案是採取下面两种方式之中的一个：
&1& 在list包括相应所属的类中，实现运算符&
&2& 提供一个排序二元谓词（一个函数。接受两个输入值，并返回一个bool值。指出第一个值是否比第二个值小）
在实际的sort调用中。首先推断有没有输入二元谓词，假设没有sort函数检查相应的list的对象元素中是否实现了运算符&。假设实现了则依照该运算符指定的排序标准进行排序。假设输入了二元谓词函数。则依照其标准进行排序。
在用remove进行删除的时候也是一样，仅仅须要提供给元素对象中的某一个变量。就能够直接删除全部的对象中该变量值相等的元素。即remove函数须要提供一个匹配标准才行，在对象类中实现==运算符。就是为remove时提供的删除标准。比方电话簿中的名字，在类中实现一个例如以下所看到的的重载运算符==
bool operator == (const ContactItem& itemToCompare) const
return(itemToCompare.strContactsName == this-&strContactsName);
forward_list模板类
从c++ 11之后，提供了forward_list来支持单向链表，包括头文件&forward_lsit&。用法与list非常类似，就好像vector与deque的关系。forward_list仅仅能沿着一个方向移动迭代器，且插入元素的时候仅仅能使用函数push_front()，而不能使用push_back。当然是用insert是能够在指定位置插入元素的。
假设须要频繁的插入和删除元素，尤其是在中间插入或删除，应当使用std::list，而不是使用std::vector。由于在这样的情况下vector须要调整内部缓冲区大小。以支持数组语法。还需运行开销高昂的复制操作。而list仅仅需建立或断开链接。
对于使用list等STL容器存储其对象的类，别忘了在当中实现运算符&和==，以提供默认排序的标准和删除谓词。
当无需频繁插入和删除元素时。请不要使用list。使用vector和deque的速度要更快。假设不想依据默认标准进行删除或排序，别忘了给sort和remove提供一个谓词函数。
*************************************************************************************************************************************
阅读(...) 评论()首先讲明，本文主要是对STL中list的用法进行简单梳理，熟悉一下STL和感受STL的用法。没有考虑STL的实现细节、时间复杂度分析等内容（这些内容作为后续的一个研究点）
其他STL容器和算法的用法不会再重复整理，这种API用法层面的东西，直接参考相关的即可。该网站很强大的一个点就是可以在查看语法的同时直接在上面的在线编译器上编写测试代码并运行查看结果！
另外可以简单通过对C++、Delphi面向对象中的类、对象、对象指针在概念和用法上的异同快速做个回顾
C语言中如果想使用链表、队列、栈、堆、哈希等数据结构必须自己实现，而C++中有STL标准库方便开发者直接使用
STL的一个重要特点是数据结构和算法的分离。尽管这是个简单的概念，但这种分离确实使得STL变得非常通用。例如，由于STL的sort()函数是完全通用的，你可以用它来操作几乎任何数据集合，包括链表、容器和数组
STL的一个重要特性是它不是面向对象的。为了具有足够通用性，STL主要依赖于模板而不是封装、继承和多态(虚函数)。这好像是一种倒退，但这正好是使得STL的组件具有广泛通用性的底层特性。另外，由于STL是基于模板，内联函数的使用使得生成的代码短小高效
STL有三个基本组件：迭代器、容器、算法
迭代器提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。迭代器就如同一个指针。事实上，C++的指针也是一种迭代器。但是迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符的方法的类对象
容器是一种数据结构，如list、vector、deques，以模板类的方法提供。为了访问容器中的数据，可以使用由容器类输出的迭代器
算法是用来操作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象。函数本身与它们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用
STL链表(list)
list是C++ STL中的部分内容。实际上，list容器就是一个双向链表，可以高效地进行插入删除元素
下面给一个简单的例子展示STL list的用法
#include &iostream&
#include &list&
typedef struct Node{
char key[32];
char value[256];
//is n1 less than n2 ?
bool lessthan(const TNode &n1, const TNode &n2){
for(int i=0; ; i++){
if(n1.key[i] == '\0')
if(n2.key[i] == '\0')
if(n1.key[i] == n2.key[i]){
}else if(n1.key[i] & n2.key[i]){
int main()
std::list&int& list_
std::list&TNode& list_
cout && "&int list&" &&
//insert 5 int into list
for(int i=0; i&5; i++){
list_int.insert(list_int.begin(), i);
//use iterator to output list
std::list&int&::
for(it=list_int.begin(); it!=list_int.end(); it++){
::cout && *it && ::
//sort int list
list_int.sort();
cout && "after sort list_int" &&
for(it=list_int.begin(); it!=list_int.end(); it++){
cout && *it &&
cout && endl && "&struct list&" &&
TNode node1{"1", "1"};
TNode node2{"23", "23"};
TNode node3{"345", "345"};
TNode node4{"1234", "1234"};
list_struct.insert(list_struct.begin(), node1);
list_struct.insert(list_struct.begin(), node2);
list_struct.insert(list_struct.begin(), node3);
list_struct.insert(list_struct.begin(), node4);
::list&TNode&::iterator it2;
for(it2=list_struct.begin(); it2!=list_struct.end(); it2++){
cout && TNode(*it2).key &&
//sort struct list
list_struct.sort(lessthan);
cout && "after sort list_struct" &&
for(it2=list_struct.begin(); it2!=list_struct.end(); it2++){
cout && TNode(*it2).key &&
通过上面这个小例子，看得出来使用很方便。关于std::list的给更多接口说明参见
执行g++ stl_list.cpp -o stl_list -std=c++0x编译程序，./stl_list运行程序。下面是在上编译的结果
关于sort()方法
当你的容器中元素是一些标准类型（int、float、char）或string时，你可以直接使用这些函数模板
但如果你是自己定义的类型或你需要按照其他方式排序，你可以有两种方法来达到效果
自己写比较函数
重载类型的&操作符
参考可以快速复习C++的运算符重载语法
新的需求如何解决？
假如我想要实现这样的场景：使用链表存储数据，然后每个数据有一个键值（字符串型的），可以根据该键值来查找到对应的数据，那么要怎么做？STL的List提供的find方法只能通过数据本身进行搜索，无法通过键值搜索
在Delphi中我们是这样实现的，定义一个结构体
PStrOrderListNode = ^TStrOrderListN
TStrOrderListNode = record
Left: PStrOrderListN
Right: PStrOrderListN //右结点
//数据，Pointer指向具体的数据，可以是整型、结构体、对象
使用TList来存储PStrOrderListNode结构的数据，根据Key: string实现对链表的排序，然后提供Search方法进行搜索，搜索的实现就很简单了：给定了要搜索的Key，明确链表本身是已经排好序的，那么使用二分查找方法即可根据Key找到对应的节点
在C++中基于STL的list也可以这么做，但这需要自己再在链表的基础上实现查找方法。而STL本身提供了一个针对键值对的数据结构map
关于map的用法、map是如何实现查找的，可以直接参考
如果本篇文章对您有所帮助，您可以通过微信(左)或支付宝(右)对作者进行打赏！
2015 - 2018C语言实现静态链表，仿照STL接口设计，操作未作封装 - 开源中国社区
当前访客身份：游客 [
当前位置：
发布于 日 13时,
& & 这里的静态是指结点所用的内存单元不是动态内存，即结点不是通过malloc或其他类似函数申请的内存。
在做之前我也以为这种方法实现起来比较简单；动手之后才知道其其实并不简单，它相对动态链表还要复杂一些，因为你要管理好那些“还没用到的内存区块”。&
&&&&一个明显的方案是把这些空闲的区块也“链接起来”组成一个链表（称之为 free list），每次新加入节点时，从 free list 的头部取出一个节点的空间交付使用；每次删除节点时，将删除的节点再“回收”到 free list上，这样我们就相当于有了一个，malloc和free的功能。&
& & 所有代码已测试通过，记录在此，以便日后查阅。&
MinGW(gcc4.6.1)编译通过
代码片段(2)
1.&[代码]static_link_list.c&&&&
// 静态链表 的实现
#include &stdio.h&
#define MAXN 16 // capacity of list.
// element type.
// define boolean type:
#define true -1
#define false 0
#define NPTR -1 // null pointer definition. can not between 0 to MAXN-1.
#define DEBUGVAL(x) printf("%s: %d\n", #x, (x)); // a macro for debug.
struct __node
}SLList[MAXN];
pointer ifree,
#define nextof(p) SLList[p].next
#define dataof(p) SLList[p].data
#define _alloc(d) dataof(ifree)=(d); ifree != NPTR ? ifree=nextof(ifree) : NPTR
#define _free(p)
nextof(p)= ifree = p
void init()
ifree = 0;
idata = NPTR;
for( i=0; i & MAXN-1; i++)
nextof(i) = i+1;
nextof(i) = NPTR;
// clear all nodes.
void clear() { init(); }
// push val to front.
bool push_front(element val)
pointer tmp,
if( ifree != NPTR ) {
np = _alloc(val);
nextof(np) =
// push val to end of list.
bool push_back(element val)
if( idata == NPTR ) { // 空表，直接写入
idata = _alloc(val);
nextof(idata) = NPTR;
if( ifree != NPTR ) { // 非空，先找到最后一个节点
pointer last = idata,
while( nextof(last) != NPTR ) last = nextof(last);
np = _alloc(val);
nextof(np) = NPTR;
nextof(last) =
// insert val to after p pointed node.
bool insert_after(pointer p, element val)
if( ifree != NPTR && p != NPTR ) {
pointer pn = _alloc(val);
nextof(pn) = nextof(p);
// insert to the position in front of p.
bool insert(pointer ptr, element val)
if( ifree == NPTR )
// 没有结点，直接返回
if( ptr == idata ) { // 有一个节点
pointer np = _alloc(val);
nextof(np) =
else { // 其他情况，先找 ptr 的前驱，再插入
pointer p =
p != NPTR ) {
if( nextof(p) == ptr ) { // find p -- the prev node of ptr.
return insert_after(p, val); // insert val after p.
p = nextof(p);
// find element, return the prev node pointer.
pointer find_prev(element val)
pointer p =
p != NPTR ) {
if( dataof( nextof(p) ) == val )
p = nextof(p);
return NPTR;
// find element, return the node
pointer find(element val)
pointer p =
p != NPTR ) {
if( dataof(p) == val )
p = nextof(p);
return NPTR;
// pop front element.
void pop_front()
if( idata != NPTR ) { // 将 data list 最前面的节点 移到 free list 上
pointer p =
idata = nextof(idata); // idata = nextof(idata);
nextof(p) =
// SLList[p].next =
pointer p =
idata = nextof(idata);
// pop back element.
void pop_back()
if( idata == NPTR )
if( nextof(idata) == NPTR ) { // only 1 node.
nextof(idata) =
idata = NPTR;
else { // 找到最后一个节点 p，以及它的前驱 q.
// TODO: find the lase nod p, and it's perv node q.
pointer p = idata,
while( nextof(p) != NPTR ) {
p = nextof( p );
// remove *p to free list, update nextof(q) to NPTR.
nextof(p) =
nextof(q) = NPTR;
void show()
pointer p =
for( ; p != NPTR; p = nextof(p) ) {
printf(" %3d ", dataof(p) );
printf("\n");
#define INFOSHOW
void info()
#ifdef INFOSHOW
DEBUGVAL(ifree);
DEBUGVAL(idata);
puts("====================\n"
"index\tdata\tnext\n"
"--------------------");
for(i=0; i&MAXN; i++) {
printf("%d\t%d\t%d\n", i, SLList[i].data, SLList[i].next);
puts("====================\n");
测试程序：
int main()
// push_front test:
puts("push_front test:");
for(i=0; i&MAXN+2; i++) {
push_front(2*i+1);
puts("pop_front test:");
for(i=0; i&MAXN+2; i++) {
pop_front();
#if 1 // push_back test:
puts("push_back test:");
for(i=0; i&MAXN+2; i++) {
push_back((i+1)*10);
puts("pop_back test:");
for(i=0; i&MAXN+1; i++)
pop_back();
#if 1 // insert test:
puts("insert test:");
for(i=0; i&MAXN+2; i++)
insert(idata, (i+1)*10);
puts("clear...\n");
#if 1 // insert_after test:
puts("insert_after test:");
push_back(-99);
for(i=0; i&MAXN+1; i++) {
insert_after(idata, i+1);
puts("clear...\n");
#if 1 // find test:
puts("find test:");
for(i=0; i&MAXN/2; i++) {
push_front(MAXN-i);
push_back(MAXN/2-i);
for(i=0; i&MAXN; i++) {
int val = rand()%(2*MAXN);
pointer p = find(val);
if( p != NPTR )
printf("%3d %3d found at %d\n", val, dataof(p), p);
printf("%3d not found\n", val);
puts("\nfind_prev test:");
for(i=0; i&MAXN; i++) {
int val = rand()%(2*MAXN);
pointer p = find_prev(val);
if( p != NPTR )
printf("%3d %3d found at %d's next.\n", val, dataof(nextof(p)), p);
printf("%3d not found\n", val);
#if 1 // find_prev and insert_after test:
puts("\nfind_prev and insert_after test:");
for(i=0; i&MAXN/2; i++) {
push_front(MAXN/2-i);
for(i=0; i&MAXN/2; i++) {
int val = rand()%(2*MAXN), n=-(i+1);
pointer p = find_prev(val);
if( p != NPTR ) {
printf("insert %d to front of %d:", n, val);
insert_after(p, n);
#if 1 // find and insert test:
puts("\nfind and insert test:");
for(i=0; i&MAXN/2; i++) {
push_front(MAXN/2-i);
for(i=0; i&MAXN/2; i++) {
int val = rand()%MAXN, n=-(i+1);
pointer p = find(val);
if( p != NPTR ) {
printf("insert %d to after of %d:", n, val);
insert_after(p, n);
puts("end of main().");
test_reslut.txt&~&6KB&&&&
push_front test:
pop_front test:
push_back test:
pop_back test:
insert test:
insert_after test:
find test:
====================
index data next
--------------------
====================
9 found at 14
3 found at 11
30 not found
4 found at 9
1 found at 15
12 found at 8
22 not found
14 found at 4
18 not found
16 found at 0
9 found at 14
17 not found
17 not found
27 not found
9 found at 14
11 found at 10
find_prev test:
19 not found
6 found at 3's next.
27 not found
28 not found
7 found at 1's next.
12 found at 10's next.
30 not found
25 not found
4 found at 7's next.
30 not found
13 found at 8's next.
28 not found
6 found at 3's next.
23 not found
7 found at 1's next.
30 not found
find_prev and insert_after test:
insert -4 to front of 8:
insert -5 to front of 3:
insert -8 to front of 6:
find and insert test:
insert -2 to after of 3:
insert -6 to after of 8:
insert -7 to after of 5:
end of main().
开源中国-程序员在线工具：
封装之后，传指针进去使用，还是相当不错的！
2楼：toil 发表于
malloc一大块以后，也可以自己管理内存（内存池），实现 静态链表呵。
3楼：xu4v 发表于
引用来自“萝卜大爱兔斯基”的评论malloc一大块以后，也可以自己管理内存（内存池），实现 静态链表呵。嗯，malloc和直接定义数组也差不多。这里free list实现的比较简单，直接连接起来的（单链表）。如果换其他方法，可能效率更高，像STL的allocator用的就是类似hash表的方法
4楼：xu4v 发表于
引用来自“萝卜大爱兔斯基”的评论封装之后，传指针进去使用，还是相当不错的！嗯，要封装成class更简单，直接用class将他们包起来就行了
5楼：戚继光 发表于
6楼：zhcosin 发表于
赞一个，boost 库里的 pool ，值得你研究一下。
7楼：xu4v 发表于
引用来自“zhcosin”的评论赞一个，boost 库里的 pool ，值得你研究一下。^v^,谢谢，正有此意，boost::pool的源码还没看，刚才查了一下，好像也是用 单链表 维护 free list 的
开源从代码分享开始
xu4v的其它代码不骄不躁，不屈不挠；严于律己，宽以待人
C++的标准模板库STL中实现的数据结构之链表std::list的分析与使用
本文主要借助对C++的标准模板库STL中实现的数据结构的学习和使用来加深对数据结构的理解，即联系数据结构的理论分析和具体的应用实现（STL），本文是系列总结的第二篇，主要针对线性表中的链表
STL std::list进行分析和总结。
由于前段时间对台大的机器学习基石和技法课程进行了学习，发现在具体的实现中常常涉及到各种类型的数据结构，比如线性表、二叉树、图等，在使用这些数据结构时感到有些吃力，主要是对一些基本的数据结构理解的不够，所以趁着暑假假期，最近一段时间总会抽空复习一下数据结构，参考的教材是王立柱编著的《C/C++与数据结构》，在具体的应用中采用的是C++标准模板库STL中对应实现的数据结构，主要参考的是MSDN文档。跟着教材的一步一步推进，现在已经复习完了链表一章节，具体的理论可以参看我的博文：
本次关注点在list模板类的使用。
回顾动态数组类
上一篇总结STL vector动态数组类的时候忘记了对另一种跟vector非常类似的动态数组类deque进行说明。下面对此进行一下补充。
STL deque类需要包含&deque&和使用std，支持在数组的开头和末尾插入或删除元素，而vector只能在末尾插入或删除，即只有push_back和pop_back。deque允许使用push_front和pop_front在开头插入和删除元素。其余的操作大致类似，不再赘述！
template &
class Type,
class Allocator=allocator&Type&
class deque
&span style="font-size:18"&// deque_push_front.cpp
// compile with: /EHsc
#include &deque&
#include &iostream&
#include &string&
int main( )
deque &int& c1;
c1.push_front( 1 );
if ( c1.size( ) != 0 )
cout && "First element: " && c1.front( ) &&
c1.push_front( 2 );
if ( c1.size( ) != 0 )
cout && "New first element: " && c1.front( ) &&
// move initialize a deque of strings
deque &string& c2;
string str("a");
c2.push_front( move( str ) );
cout && "Moved first element: " && c2.front( ) &&
}&/span&总结：在不知道需要存储多少个元素时，务必使用动态数组vector或deque，并牢记vector只能使用push_back在一端扩容，而deque可以使用push_back和push_front在两端扩容。另外，访问动态数组时，不要跨越其边界。
list 模板类
标准模板库以模板类std::list的方式向程序员提供了一个双向链表。双向链表的主要优点是插入和删除元素的速度快，且时间固定，不像顺序表那样需要移动元素。从C++ 11起，还可以使用单向链表std::forward_list，只沿着一个方向遍历。
template &
class Type,
class Allocator=allocator&Type&
class list
list的特点
链表是一系列节点，每个节点除了包含对象或data之外，还包含指向下一个或者上一个节点的指针，list类的STL实现允许在开头、末尾和中间插入元素，且所需的时间固定。使用时包含&list&和std。
list的基本操作
list&int& listI list&float& listF等等。要声明一个指向list中元素的迭代器，可以进行如下操作：
list&int& :: const_iterator iElementInS 还记得const_iterator吧，在上一篇vector的分析中讲到过，指向一个只读的元素，如果要对容器中的内容进行修改，可以使用iterator来进行。还有一些与vector一样的初始化操作，可以参考上一篇博文，后续关于STL容器进行编程或者讲解时，实例化的方式大致一样，这种模式也将长期出现，后续博文便不再多提。
在list开头或末尾插入或删除元素
跟deque类相似，采用push_front/pop_front和push_back/pop_back的方法。
在list中间插入或删除元素
list的特点之一，上面讲过，在中间插入或删除元素所需的时间是固定的，使用函数insert()和erase()。
从上面的分析看，基本上所有的容器类（vector，list，deque...）所使用的方法模式都类似，这对于触类旁通的学习很有帮助。
list元素的反转和排序
list的一个独到之处就是指向元素的迭代器在list的元素重新排列或插入元素后仍然有效，为实现这种特点，list提供了成员方法sort和reverse，虽然STL也提供了这两种算法（在算法类中&algorithm&），且这些算法同样可以使用在list类上。
使用reverse()反转元素的顺序排列
list提供了成员函数reverse，没有参数，功能是反转list中元素的排列顺序：
&span style="font-size:18"&// list_reverse.cpp
// compile with: /EHsc
#include &list&
#include &iostream&
int main( )
list &int& c1;
list &int&::iterator c1_I
c1.push_back( 10 );
c1.push_back( 20 );
c1.push_back( 30 );
cout && "c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && " " && *c1_I
c1.reverse( );
cout && "Reversed c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && " " && *c1_I
}&/span&输出结果：
c1 = 10 20 30
Reversed c1 = 30 20 10
使用sort()对元素进行排序
list成员函数sort有两个版本，一是没有参数，默认是升序排列，如果想降序排列，可以升序后采用reverse。另一个版本是接受一个二元谓词函数作为参数，制定排序的标准，比如下面一个二元谓词函数GeaterThan，指定的排序标准是降序排列
bool GeaterThan(const int& lsh, const int& rsh)
return(lsh & rsh);
&span style="font-size:18"&// list_sort.cpp
// compile with: /EHsc
#include &list&
#include &iostream&
int main( )
list &int& c1;
list &int&::iterator c1_I
c1.push_back( 20 );
c1.push_back( 10 );
c1.push_back( 30 );
cout && "Before sorting: c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && " " && *c1_I
c1.sort( );
cout && "After sorting c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && " " && *c1_I
c1.sort( greater&int&( ) );
cout && "After sorting with 'greater than' operation, c1 =";
for ( c1_Iter = c1.begin( ); c1_Iter != c1.end( ); c1_Iter++ )
cout && " " && *c1_I
}&/span&输出为：
Before sorting: c1 = 20 10 30
After sorting c1 = 10 20 30
After sorting with 'greater than' operation, c1 = 30 20 10
对包含对象的list进行排序及删除其中的元素
在实际应用很少使用STL容器来存储整数，而是存储用户自己定义的类型，比如类或结构等。那么这种排序如何做呢?比如list中存储的是电话簿，其中每个元素都是一个对象，包含名称、地址等内容，如何确保能按照名称对其进行排序呢？
答案是采取以下两种方式之一：
&1& 在list包含对应所属的类中，实现运算符&
&2& 提供一个排序二元谓词（一个函数，接受两个输入值，并返回一个bool值，指出第一个值是否比第二个值小）
在实际的sort调用中，首先判断有没有输入二元谓词，如果没有sort函数检查对应的list的对象元素中是否实现了运算符&，如果实现了则按照该运算符指定的排序标准进行排序。如果输入了二元谓词函数，则按照其标准进行排序；
在用remove进行删除的时候也是一样，只需要提供给元素对象中的某一个变量，就可以直接删除所有的对象中该变量值相等的元素。即remove函数需要提供一个匹配标准才行，在对象类中实现==运算符，就是为remove时提供的删除标准。比如电话簿中的名字，在类中实现一个如下所示的重载运算符==
bool operator == (const ContactItem& itemToCompare) const
return(itemToCompare.strContactsName == this-&strContactsName);
forward_list模板类
从c++ 11之后，提供了forward_list来支持单向链表，包含头文件&forward_lsit&，使用方法与list很类似，就好像vector与deque的关系。forward_list只能沿着一个方向移动迭代器，且插入元素的时候只能使用函数push_front()，而不能使用push_back，当然是用insert是可以在指定位置插入元素的。
如果需要频繁的插入和删除元素，尤其是在中间插入或删除，应当使用std::list，而不是使用std::vector，因为在这种情况下vector需要调整内部缓冲区大小，以支持数组语法，还需执行开销高昂的复制操作，而list只需建立或断开链接。
对于使用list等STL容器存储其对象的类，别忘了在其中实现运算符&和==，以提供默认排序的标准和删除谓词。
当无需频繁插入和删除元素时，请不要使用list，使用vector和deque的速度要更快。如果不想根据默认标准进行删除或排序，别忘了给sort和remove提供一个谓词函数。
*************************************************************************************************************************************
实训C++语言设计——STL链表、栈类、队列
(转)c++标准库——list容器
STL STD::list使用说明
VC++ STL使用介绍
C++ 标准模板库STL 队列 queue
使用方法与应用介绍（一）
std::list（双向循环链表）的使用？
STL list链表的用法详细解析
【C++】STL常用容器总结之四：链表list
C++ STL的实现
C++11中STL总结+(boost库）
没有更多推荐了，