List(雙向鏈表)介紹:
List是一個線性鏈表結構，它的數據由若干個節點構成，每一個節點都包括一個信息塊（即實際存儲的數據）、一個前驅指針和一個后驅指針。它無需分配指定的內存大小且可以任意伸縮，這是因為它存儲在非連續的內存空間中，并且由指針將有序的元素鏈接起來。
由于其結構的原因，list 隨機檢索的性能非常的不好，因為它不像vector 那樣直接找到元素的地址，而是要從頭一個一個的順序查找，這樣目標元素越靠后，它的檢索時間就越長。檢索時間與目標元素的位置成正比。
雖然隨機檢索的速度不夠快，但是它可以迅速地在任何節點進行插入和刪除操作。因為list 的每個節點保存著它在鏈表中的位置，插入或刪除一個元素僅對最多三個元素有所影響，不像vector 會對操作點之后的所有元素的存儲地址都有所影響，這一點是vector 不可比擬的。
List 的特點：
(1) 不使用連續的內存空間這樣可以隨意地進行動態操作；
(2) 可以在內部任何位置快速地插入或刪除，當然也可以在兩端進行push和pop 。
(3) 不能進行內部的隨機訪問，即不支持[ ] 操作符和vector.at() ；
Lists將元素按順序儲存在鏈表中，與向量(vectors)相比，它允許快速的插入和刪除，但是隨機訪問卻比較慢.
1.assign() 給list賦值
語法:
void assign( input_iterator start, input_iterator end );
//以迭代器start和end指示的范圍為list賦值
void assign( size_type num, const TYPE &val );
//賦值num個以val為值的元素。
2.back() 返回最后一個元素的引用
3.begin() 返回指向第一個元素的迭代器
4.clear() 刪除所有元素
5.empty() 如果list是空的則返回true
6.end() 返回末尾的迭代器
7.erase() 刪除一個元素
語法：
iterator erase( iterator loc );//刪除loc處的元素
iterator erase( iterator start, iterator end ); //刪除start和end之間的元素
8.front() 返回第一個元素的引用
9.get_allocator() 返回list的配置器
10.insert() 插入一個元素到list中
語法：
iterator insert( iterator loc, const TYPE &val );
//在指定位置loc前插入值為val的元素,返回指向這個元素的迭代器,
void insert( iterator loc, size_type num, const TYPE &val );
//定位置loc前插入num個值為val的元素
void insert( iterator loc, input_iterator start, input_iterator end );
//在指定位置loc前插入區間[start, end)的所有元素
11.max_size() 返回list能容納的最大元素數量
12.merge() 合并兩個list
語法:
void merge( list &lst );//把自己和lst鏈表連接在一起
void merge( list &lst, Comp compfunction );
//指定compfunction，則將指定函數作為比較的依據。
13.pop_back() 刪除最后一個元素
14.pop_front() 刪除第一個元素
15.push_back() 在list的末尾添加一個元素
16.push_front() 在list的頭部添加一個元素
17.rbegin() 返回指向第一個元素的逆向迭代器
18.remove() 從list刪除元素
語法:
void remove( const TYPE &val );
//刪除鏈表中所有值為val的元素
19.remove_if() 按指定條件刪除元素
20.rend() 指向list末尾的逆向迭代器
21.resize() 改變list的大小
語法:
void resize( size_type num, TYPE val );
//把list的大小改變到num。被加入的多余的元素都被賦值為val22.
22.reverse() 把list的元素倒轉
23.size() 返回list中的元素個數
24.sort() 給list排序
語法:
void sort();//為鏈表排序，默認是升序
void sort( Comp compfunction );//采用指定函數compfunction來判定兩個元素的大小。
25.splice() 合并兩個list
語法:
void splice( iterator pos, list &lst );//把lst連接到pos的位置
void splice( iterator pos, list &lst, iterator del );//插入lst中del所指元素到現鏈表的pos上
void splice( iterator pos, list &lst, iterator start, iterator end );//用start和end指定范圍。
26.swap() 交換兩個list
語法：
void swap( list &lst );// 交換lst和現鏈表中的元素
27.unique() 刪除list中重復的元素
語法:
void unique();//刪除鏈表中所有重復的元素
void unique( BinPred pr );// 指定pr，則使用pr來判定是否刪除。
以下轉自：http://www.cnblogs.com/fangyukuan/archive/2010/09/21/1832364.html
例子：
1 // -------------------------------------------------------------------------
2 // 文件名 : list1.cpp
3 // 創建者 : 方煜寬
4 // 郵箱 ： fangyukuan@gmail.com
5 // 創建時間 : 2010-9-19 15:58
6 // 功能描述 : STL中的list就是一雙向鏈表，可高效地進行插入刪除元素。
7 //
8 // -------------------------------------------------------------------------
9 #include "stdafx.h"
10 #include <iostream>
11 #include <list>
12 using namespace std;
13
14 list<int> g_list1;
15 list<int> g_list2;
16
17 //////////////////////////////////////////////////////////////////////////
18
19 // 初始化全局鏈表
20 void InitList()
21 {
22 // push_back()增加一元素到鏈表尾
23 g_list1.push_back(1);
24 g_list1.push_back(2);
25 g_list1.push_back(3);
26
27 // push_front()增加一元素到鏈表頭
28 g_list2.push_front(6);
29 g_list2.push_front(5);
30 g_list2.push_front(4);
31 }
32
33 // 輸出一個鏈表
34 void ShowList(list<int>& listTemp)
35 {
36 // size()返回鏈表中元素個數
37 cout << listTemp.size() << endl;
38
39 for (list<int>::iterator it = listTemp.begin(); it != listTemp.end(); ++it)
40 {
41 cout << *it << ' ';
42 }
43 cout << endl;
44 }
45
46 //////////////////////////////////////////////////////////////////////////
47
48 // 構造函數，空鏈表
49 void constructor_test0()
50 {
51 list<int> listTemp;
52 cout << listTemp.size() << endl;
53 }
54
55 // 構造函數，建一個含三個默認值是0的元素的鏈表
56 void constructor_test1()
57 {
58 list<int> listTemp(3);
59 ShowList(listTemp);
60 }
61
62 // 構造函數，建一個含五個元素的鏈表，值都是1
63 void constructor_test2()
64 {
65 list<int> listTemp(5, 1);
66 ShowList(listTemp);
67 }
68
69 // 構造函數，建一個g_list1的copy鏈表
70 void constructor_test3()
71 {
72 list<int> listTemp(g_list1);
73 ShowList(listTemp);
74 }
75
76 // 構造函數，listTemp含g_list1一個區域的元素[_First, _Last)
77 void constructor_test4()
78 {
79 list<int> listTemp(g_list1.begin(), g_list1.end());
80 ShowList(listTemp);
81 }
82
83 // assign()分配值，有兩個重載
84 // template <class InputIterator>
85 // void assign ( InputIterator first, InputIterator last );
86 // void assign ( size_type n, const T& u );
87 void assign_test()
88 {
89 list<int> listTemp(5, 1);
90 ShowList(listTemp);
91
92 listTemp.assign(4, 3);
93 ShowList(listTemp);
94
95 listTemp.assign(++g_list1.begin(), g_list1.end());
96 ShowList(listTemp);
97 }
98
99 // operator=
100 void operator_equality_test()
101 {
102 g_list1 = g_list2;
103 ShowList(g_list1);
104 ShowList(g_list2);
105 }
106
107 // front()返回第一個元素的引用
108 void front_test7()
109 {
110 cout << g_list1.front() << endl;
111 }
112
113 // back()返回最后一元素的引用
114 void back_test()
115 {
116 cout << g_list1.back() << endl;
117 }
118
119 // begin()返回第一個元素的指針(iterator)
120 void begin_test()
121 {
122 list<int>::iterator it1 = g_list1.begin();
123 cout << *++it1 << endl;
124
125 list<int>::const_iterator it2 = g_list1.begin();
126 it2++;
127 // (*it2)++; // *it2 為const 不用修改
128 cout << *it2 << endl;
129
130 }
131
132 // end()返回 [最后一個元素的下一位置的指針] (list為空時end()= begin())
133 void end_test()
134 {
135 list<int>::iterator it = g_list1.end(); // 注意是：最后一個元素的下一位置的指針
136 --it;
137 cout << *it << endl;
138 }
139
140 // rbegin()返回鏈表最后一元素的后向指針
141 void rbegin_test()
142 {
143 list<int>::reverse_iterator it = g_list1.rbegin();
144 for (; it != g_list1.rend(); ++it)
145 {
146 cout << *it << ' ';
147 }
148 cout << endl;
149 }
150
151 // rend()返回鏈表第一元素的下一位置的后向指針
152 void rend_test()
153 {
154 list<int>::reverse_iterator it = g_list1.rend();
155 --it;
156 cout << *it << endl;
157 }
158
159 // push_back()增加一元素到鏈表尾
160 void push_back_test()
161 {
162 ShowList(g_list1);
163 g_list1.push_back(4);
164 ShowList(g_list1);
165 }
166
167 // push_front()增加一元素到鏈表頭
168 void push_front_test()
169 {
170 ShowList(g_list1);
171 g_list1.push_front(4);
172 ShowList(g_list1);
173 }
174
175 // pop_back()刪除鏈表尾的一個元素
176 void pop_back_test()
177 {
178 ShowList(g_list1);
179 cout << endl;
180
181 g_list1.pop_back();
182 ShowList(g_list1);
183
184 }
185
186 // pop_front()刪除鏈表頭的一元素
187 void pop_front_test()
188 {
189 ShowList(g_list1);
190 cout << endl;
191
192 g_list1.pop_front();
193 ShowList(g_list1);
194 }
195
196 // clear()刪除所有元素
197 void clear_test()
198 {
199 ShowList(g_list1);
200 g_list1.clear();
201 ShowList(g_list1);
202 }
203
204 // erase()刪除一個元素或一個區域的元素(兩個重載函數)
205 void erase_test()
206 {
207 ShowList(g_list1);
208 g_list1.erase(g_list1.begin());
209 ShowList(g_list1);
210
211 cout << endl;
212
213 ShowList(g_list2);
214 g_list2.erase(++g_list2.begin(), g_list2.end());
215 ShowList(g_list2);
216 }
217
218 // remove()刪除鏈表中匹配值的元素(匹配元素全部刪除)
219 void remove_test()
220 {
221 ShowList(g_list1);
222 g_list1.push_back(1);
223 ShowList(g_list1);
224
225 g_list1.remove(1);
226 ShowList(g_list1);
227 }
228
229 bool myFun(const int& value) { return (value < 2); }
230 // remove_if()刪除條件滿足的元素(會遍歷一次鏈表)
231 void remove_if_test()
232 {
233 ShowList(g_list1);
234 g_list1.remove_if(myFun);
235 ShowList(g_list1);
236 }
237
238
239 // empty()判斷是否鏈表為空
240 void empty_test()
241 {
242 list<int> listTemp;
243 if (listTemp.empty())
244 cout << "listTemp為空" << endl;
245 else
246 cout << "listTemp不為空" << endl;
247 }
248
249
250 // max_size()返回鏈表最大可能長度:1073741823
251 void max_size_test()
252 {
253 list<int>::size_type nMax = g_list1.max_size();
254 cout << nMax << endl;
255 }
256
257
258 // resize()重新定義鏈表長度(兩重載函數)：
259 void resize_test()
260 {
261 ShowList(g_list1);
262 g_list1.resize(9); // 用默認值填補
263 ShowList(g_list1);
264 cout << endl;
265
266 ShowList(g_list2);
267 g_list2.resize(9, 51); // 用指定值填補
268 ShowList(g_list2);
269 }
270
271 // reverse()反轉鏈表
272 void reverse_test()
273 {
274 ShowList(g_list1);
275 g_list1.reverse();
276 ShowList(g_list1);
277 }
278
279
280 // sort()對鏈表排序，默認升序(兩個重載函數)
281 void sort_test()
282 {
283 list<int> listTemp;
284 listTemp.push_back(9);
285 listTemp.push_back(3);
286 listTemp.push_back(5);
287 listTemp.push_back(1);
288 listTemp.push_back(4);
289 listTemp.push_back(3);
290
291 ShowList(listTemp);
292 listTemp.sort();
293 ShowList(listTemp);
294
295 listTemp.sort(greater<int>());
296 ShowList(listTemp);
297 }
298
299 // merge()合并兩個升序序鏈表并使之成為另一個升序.
300 void merge_test1()
301 {
302 list<int> listTemp2;
303 listTemp2.push_back(3);
304 listTemp2.push_back(4);
305
306 list<int> listTemp3;
307 listTemp3.push_back(9);
308 listTemp3.push_back(10);
309
310 ShowList(listTemp2);
311 cout << endl;
312 ShowList(listTemp3);
313 cout << endl;
314
315 listTemp2.merge(listTemp3);
316 ShowList(listTemp2);
317 }
318
319
320 bool myCmp (int first, int second)
321 { return ( int(first)>int(second) ); }
322
323 // merge()合并兩個降序鏈表并使之成為另一個降序.
324 void merge_test2()
325 {
326 list<int> listTemp2;
327 listTemp2.push_back(4);
328 listTemp2.push_back(3);
329
330 list<int> listTemp3;
331 listTemp3.push_back(10);
332 listTemp3.push_back(9);
333
334 ShowList(listTemp2);
335 cout << endl;
336 ShowList(listTemp3);
337 cout << endl;
338
339 // listTemp2.merge(listTemp3, greater<int>()); // 第二個參數可以是自己定義的函數如下
340 listTemp2.merge(listTemp3, myCmp);
341 ShowList(listTemp2);
342 }
343
344 // splice()對兩個鏈表進行結合(三個重載函數),結合后第二個鏈表清空
345 // void splice ( iterator position, list<T,Allocator>& x );
346 // void splice ( iterator position, list<T,Allocator>& x, iterator i );
347 // void splice ( iterator position, list<T,Allocator>& x, iterator first, iterator last );
348 void splice_test()
349 {
350 list<int> listTemp1(g_list1);
351 list<int> listTemp2(g_list2);
352
353 ShowList(listTemp1);
354 ShowList(listTemp2);
355 cout << endl;
356
357 //
358 listTemp1.splice(++listTemp1.begin(), listTemp2);
359 ShowList(listTemp1);
360 ShowList(listTemp2);
361
362 //
363 listTemp1.assign(g_list1.begin(), g_list1.end());
364 listTemp2.assign(g_list2.begin(), g_list2.end());
365 listTemp1.splice(++listTemp1.begin(), listTemp2, ++listTemp2.begin());
366 ShowList(listTemp1);
367 ShowList(listTemp2);
368
369 //
370 listTemp1.assign(g_list1.begin(), g_list1.end());
371 listTemp2.assign(g_list2.begin(), g_list2.end());
372 listTemp1.splice(++listTemp1.begin(), listTemp2, ++listTemp2.begin(), listTemp2.end());
373 ShowList(listTemp1);
374 ShowList(listTemp2);
375
376 }
377
378 // insert()在指定位置插入一個或多個元素(三個重載函數)
379 // iterator insert ( iterator position, const T& x );
380 // void insert ( iterator position, size_type n, const T& x );
381 // template <class InputIterator>
382 // void insert ( iterator position, InputIterator first, InputIterator last );
383 void insert_test()
384 {
385 list<int> listTemp1(g_list1);
386 ShowList(listTemp1);
387 listTemp1.insert(listTemp1.begin(), 51);
388 ShowList(listTemp1);
389 cout << endl;
390
391 list<int> listTemp2(g_list1);
392 ShowList(listTemp2);
393 listTemp2.insert(listTemp2.begin(), 9, 51);
394 ShowList(listTemp2);
395 cout << endl;
396
397 list<int> listTemp3(g_list1);
398 ShowList(listTemp3);
399 listTemp3.insert(listTemp3.begin(), g_list2.begin(), g_list2.end());
400 ShowList(listTemp3);
401
402 }
403
404 // swap()交換兩個鏈表(兩個重載)
405 void swap_test()
406 {
407 ShowList(g_list1);
408 ShowList(g_list2);
409 cout << endl;
410
411 g_list1.swap(g_list2);
412 ShowList(g_list1);
413 ShowList(g_list2);
414 }
415
416 bool same_integral_part (double first, double second)
417 { return ( int(first)==int(second) ); }
418
419 // unique()刪除相鄰重復元素
420 void unique_test()
421 {
422 list<int> listTemp;
423 listTemp.push_back(1);
424 listTemp.push_back(1);
425 listTemp.push_back(4);
426 listTemp.push_back(3);
427 listTemp.push_back(5);
428 listTemp.push_back(1);
429 list<int> listTemp2(listTemp);
430
431 ShowList(listTemp);
432 listTemp.unique(); // 不會刪除不相鄰的相同元素
433 ShowList(listTemp);
434 cout << endl;
435
436 listTemp.sort();
437 ShowList(listTemp);
438 listTemp.unique();
439 ShowList(listTemp);
440 cout << endl;
441
442 listTemp2.sort();
443 ShowList(listTemp2);
444 listTemp2.unique(same_integral_part);
445 ShowList(listTemp2);
446
447 }
448
449 // 主函數，下面要測試哪個就把那個注釋去掉即可
450 int _tmain(int argc, _TCHAR* argv[])
451 {
452 InitList();
453 // ShowList(g_list1);
454 // ShowList(g_list2);
455
456 // constructor_test0();
457 // constructor_test1();
458 // constructor_test2();
459 // constructor_test3();
460 // constructor_test4();
461 // assign_test();
462 // operator_equality_test();
463 // front_test7();
464 // back_test();
465 // begin_test();
466 // end_test();
467 // rbegin_test();
468 // rend_test();
469 // push_back_test();
470 // push_front_test();
471 // pop_back_test();
472 // pop_front_test();
473 // clear_test();
474 // erase_test();
475 // remove_test();
476 // remove_if_test();
477 // empty_test();
478 // max_size_test();
479 // resize_test();
480 // reverse_test();
481 // sort_test();
482 // merge_test1();
483 // merge_test2();
484 // splice_test();
485 // insert_test();
486 // swap_test();
487 // unique_test();
488 return 0;
489 }
posted on 2012-06-04 15:50
王海光 閱讀(4115)
評論(0) 編輯 收藏 引用 所屬分類:
STL