双向循环链表list.doc

list是双向循环链表，每一个元素都知道前面一个元素和后面一个元素。在STL中，list和vector一样，是两个常被使用的容器。和vector不一样的是，list不支持对元素的任意存取。list中提供的成员函数与vector类似，不过list提供对表首元素的操作push_front、pop_front，这是vector不具备的。和vector另一点不同的是，list的迭代器不会存在失效的情况，他不像vector会保留备份空间，在超过容量额度时重新全部分配内存，导致迭代器失效；list没有备份空间的概念，出入一个元素就申请一个元素的空间，所以它的迭代器不会失效。还是举C+之vector中的例子：int data6=3,5,7,9,2,4; list lidata(data, data+6); lidata.push_back(6); .list初始化时，申请的空间大小为6，存放下了data中的6个元素，当向lidata插入第7个元素“6”时，list申请新的节点单元，插入到list链表中，数据存放结构如图1所示：图1 list的存储结构 list每次增加一个元素，不存在重新申请内存的情况，它的成本是恒定的。而vector每当增加关键元素的时候，都需要重新申请新的更大的内存空间，会调用元素的自身的复制构造函数，存在构造成本。在销毁旧内存的时候，会调用析构函数，存在析构成本。所以在存储复杂类型和大量元素的情况下，list比vector更有优势！ List是一个双向链表,双链表既可以向前又向后链接他的元素。 List将元素按顺序储存在链表中. 与 向量(vector)相比, 它允许快速的插入和删除，但是随机访问却比较慢。assign() 给list赋值back() 返回最后一个元素begin() 返回指向第一个元素的迭代器clear() 删除所有元素empty() 如果list是空的则返回trueend() 返回末尾的迭代器erase() 删除一个元素front() 返回第一个元素get_allocator() 返回list的配置器insert() 插入一个元素到list中max_size() 返回list能容纳的最大元素数量merge() 合并两个listpop_back() 删除最后一个元素pop_front() 删除第一个元素push_back() 在list的末尾添加一个元素push_front() 在list的头部添加一个元素rbegin() 返回指向第一个元素的逆向迭代器remove() 从list删除元素remove_if() 按指定条件删除元素rend() 指向list末尾的逆向迭代器resize() 改变list的大小reverse() 把list的元素倒转size() 返回list中的元素个数sort() 给list排序splice() 合并两个listswap() 交换两个listunique() 删除list中重复的元素List使用实例1#include #include #include #include using namespace std;/创建一个list容器的实例LISTINTtypedef list LISTINT;/创建一个list容器的实例LISTCHARtypedef list LISTCHAR;int main(int argc, char *argv)/-/用list容器处理整型数据/-/用LISTINT创建一个名为listOne的list对象LISTINT listOne;/声明i为迭代器LISTINT:iterator i;/从前面向listOne容器中添加数据listOne.push_front (2);listOne.push_front (1);/从后面向listOne容器中添加数据listOne.push_back (3);listOne.push_back (4);/从前向后显示listOne中的数据coutlistOne.begin()- listOne.end():endl;for (i = listOne.begin(); i != listOne.end(); +i)cout *i ;cout endl;/从后向后显示listOne中的数据LISTINT:reverse_iterator ir;coutlistOne.rbegin()-listOne.rend():endl;for (ir =listOne.rbegin(); ir!=listOne.rend();ir+) cout *ir ;cout endl;/使用STL的accumulate(累加)算法int result = accumulate(listOne.begin(), listOne.end(),0);coutSum=resultendl;cout-endl;/-/用list容器处理字符型数据/-/用LISTCHAR创建一个名为listOne的list对象LISTCHAR listTwo;/声明i为迭代器LISTCHAR:iterator j;/从前面向listTwo容器中添加数据listTwo.push_front (A);listTwo.push_front (B);/从后面向listTwo容器中添加数据listTwo.push_back (x);listTwo.push_back (y);/从前向后显示listTwo中的数据coutlistTwo.begin()-listTwo.end():endl;for (j = listTwo.begin(); j != listTwo.end(); +j)cout char(*j) ;cout endl;/使用STL的max_element算法求listTwo中的最大元素并显示j=max_element(listTwo.begin(),listTwo.end();cout The maximum element in listTwo is: char(*j)endl;return 0;List使用实例2list: Linked list of variables, struct or objects. Insert/remove anywhere.Two examples are given:1. The first STL example is for data typeint2. The second for a list ofclassinstances.They are used to show a simple example and a more complex real world application.1. Lets start with a simple example of a program using STL for a linked list: / Simple example uses type int#include #include using namespace std;int main() list L; L.push_back(0); / Insert a new element at the end L.push_front(0); / Insert a new element at the beginning L.insert(+L.begin(),2); / Insert 2 before position of first argument / (Place before second argument) L.push_back(5); L.push_back(6); list:iterator i; for(i=L.begin(); i != L.end(); +i) cout *i ; cout endl; return 0;Compile:g+ example1.cppRun:./a.outOutput:0 2 0 5 62. The STL tutorials and texts seem to give simple examples which do not apply to the real world. The following example is for a doubly linked list. Since we are using a class and we are not using defined built-in C+ types we have included the following: To make this example more complete, a copy constructor has been included although the compiler will generate a member-wise one automatically if needed. This has the same functionality as the assignment operator (=). The assignment (=) operator must be specified so that sort routines can assign a new order to the members of the list. The less than () operator must be specified so that sort routines can determine if one class instance is less than another. The equals to (=) operator must be specified so that sort routines can determine if one class instance is equals to another./ Standard Template Library example using a class.#include #include using namespace std;/ The List STL template requires overloading operators =, = and ./vc2005调试没有错（红色字体部分可去掉）、可用vc6.0却报错了“operator is ambiguous”（vc6.0的加上红色字体部分）class AAA;ostream &operator(ostream &output, const AAA &aaa);class AAA friend ostream &operator(ostream &, const AAA &); public: int x; int y; float z; AAA(); AAA(const AAA &); AAA(); AAA &operator=(const AAA &rhs); int operator=(const AAA &rhs) const; int operator(const AAA &rhs) const;AAA:AAA() / Constructor x = 0; y = 0; z = 0;AAA:AAA(const AAA ©in) / Copy constructor to handle pass by value. x = copyin.x; y = copyin.y; z = copyin.z;ostream &operator(ostream &output, const AAA &aaa) output aaa.x aaa.y aaa.z x = rhs.x; this-y = rhs.y; this-z = rhs.z; return *this;int AAA:operator=(const AAA &rhs) const if( this-x != rhs.x) return 0; if( this-y != rhs.y) return 0; if( this-z != rhs.z) return 0; return 1;/ This function is required for built-in STL list functions like sortint AAA:operatorx = rhs.x & this-y = rhs.y & this-z x = rhs.x & this-y x rhs.x ) return 1; return 0;int main() list L; AAA Ablob ; Ablob.x=7; Ablob.y=2; Ablob.z=4.2355; L.push_back(Ablob); / Insert a new element at the end Ablob.x=5;