《双向循环链表list汇总》由会员分享，可在线阅读，更多相关《双向循环链表list汇总（12页珍藏版）》请在金锄头文库上搜索。
1、list是双向循环链表，每一个元素都知道前面一个元素和后面一个元素。在STL中，list和vector 一样，是两个常被使用的容器。和vector不一样的是，list不支持对元素的任意存取。list中提供的成员函数与vector类似，不过list提供对表首元素 的操作 push_front、pop_front，这是 vector不具备的。禾口 vector另一点不同的是， list的迭代器不会存在失效的情况，他不像 vector会保留备份空间，在超过容量额 度时重新全部分配内存，导致迭代器失效；list没有备份空间的概念，出入一个元素 就申请一个元素的空间，所以它的迭代器不会失效。还是举C+之
2、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所示：35A7r-9H412V4 I插入节点6之前的listI -3bw51-9Uo2M4 6 插入节点睜6之后的1曲图1 list的存储结构list每次增加一个元素，不存在重新申请内存的情况，它的成本是恒定的。而 vector每当增加关键元素的时候，都需要重新
3、申请新的更大的内存空间，会调用元 素的自身的复制构造函数，存在构造成本。在销毁旧内存的时候，会调用析构函数, 存在析构成本。所以在存储复杂类型和大量元素的情况下，list比vector更有优势！List是一个双向链表,双链表既可以向前又向后链接他的元素。List将元素按顺序储存在链表中.与向量(vector)相比,它允许快速的插 入和删除，但是随机访问却比较慢。assign()给 list 赋值back()返回最后一个元素begin()返回指向第一个元素的迭代器clear()删除所有元素empty() 如果list是空的则返回trueen d()返回末尾的迭代器erase()删除一个元素fro
4、n t()返回第一个元素get_allocator() 返回 list 的配置器insert()插入一个元素到list中max_size() 返回list能容纳的最大元素数量merge()合并两个listpop_back()删除最后一个元素pop_fro nt()删除第一个元素push_back()在list的末尾添加一个元素push_front()在list的头部添加一个元素rbegi n()返回指向第一个元素的逆向迭代器remove() 从list删除元素remove_if() 按指定条件删除元素rend()指向list末尾的逆向迭代器 resize。 改变list的大小reverse。把
5、list的元素倒转size()返回list中的元素个数 sort()给 list 排序 splice()合并两个listswap()交换两个listunique() 删除list中重复的元素List使用实例1#in elude #in clude #in clude #i nclude using n amespace std;创建一个list容器的实例LISTINT typedef list LISTINT;创建一个list容器的实例LISTCHAR typedef list LISTCHAR;int main (i nt argc, char *argv)/用list容器处理整型数据/用L
6、ISTINT创建一个名为listOne的list对象LISTINT list One;/声明i为迭代器LISTINT:iterator i;从前面向listOne容器中添加数据listO ne.push_fro nt (2);listO ne.push_fro nt (1);从后面向listOne容器中添加数据list On e.push_back (3);listO ne.push_back (4);从前向后显示listOne中的数据coutlist On e.beg in()- list On e.e nd():e ndl;for (i = list On e.begi n(); i 匸
7、list On e.e nd(); +i) cout *i ;cout en dl;从后向后显示listOne中的数据LISTINT:reverse_iterator ir;coutlistOne.rbegin()-list On e.re nd():ve ndl; for (ir =list On e.rbeg in (); ir!=list On e.re nd();ir+) cout *ir ;cout en dl;使用STL的accumulate(累加)算法int result = accumulate(list On e.beg in(), list On e.e nd(),0);
8、coutSum二vvresultvve ndl;coute ndl;/用list容器处理字符型数据/用LISTCHAR创建一个名为list One的list对象LISTCHAR listTwo;/声明i为迭代器LISTCHAR:iterator j;/从前面向listTwo容器中添加数据listTwo.push_fro nt (A);listTwo.push_fro nt (B);/从后面向listTwo容器中添加数据 listTwo.push_back (x);listTwo.push_back (y);从前向后显示listTwo中的数据coutlistTwo.begin()-listTwo
9、.e nd():ve ndl;for (j = listTwo.begin(); j != listTwo.end(); +j)cout char(*j) ;cout en dl;使用STL的max_element算法求listTwo中的最大元素并显示 j=max_eleme nt(listTwo.begi n( ),listTwo.e nd();cout The maximum eleme nt in listTwo is: vchar(*j)ve ndl;return 0;List使用实例2list: Lin ked list of variables, struct or objects
10、. In sert/remove any where.Two examples are give n:1. The first STL example is for data type int2. The sec ond for a list of class in sta nces.They are used to show a simple example and a more complex real world applicati on.1. Lets start with a simple example of a program using STL for a linked lis
11、t:/ Simple example uses type int#in clude #in clude using n amespace std;int mai n()list L;L.push_back(O);L.push_fro nt(0);L.i nsert(+L.beg in( ),2);/In sert a new eleme nt at the end/Insert a new eleme nt at the beg inning/ Insert 2 before position of first argument/ (Place before sec ond argume nt
12、)L.push_back(5);L.push_back(6);list :iterator i;for(i=L.begin(); i != L.end(); +i) cout *i ;cout en dl;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 notapply to the real world. The following example is for a doubly
13、linked list.Since we are using a class and we are not using defined built-in C+types we have in cluded the followi ng:* To make this example more complete, a copy con structor has bee nin cluded although the compiler will gen erate a member-wise one automatically if needed. This has the same functio
14、nality as the assignment operator (=). The assig nment (=) operator must be specified so that sort routi nes can assig n a new order to the members of the list. The less than () operator must be specified so that sort routines candetermine if one class instance is less than another. The equals to (=) operator must be specified so that sort routines candetermine if one class instance is equals to another./ Stan dard Template Library example using a class.#in clud
