STL学习笔记 list
STL学习笔记-- list
list 双向链表容器(双向循环链表的数据结构)
list 是双向链表的一个泛化容器的容器，实现了 Reversible Container 、 Front Insertion Sequence 和 Back Insertion Sequence 等概念的接口规范。作为一种序列容器，它的数据元素可通过链表指针串接成逻辑上的线性表。
不同于采用线性表顺序存储结构的 vector 和 deque 容器，list 双向链表中任一位置的元素查找、插入和删除，都具有高效的常数阶算法时间复杂度 O(1).
list 双向链表容器的 C++ 标准头文件为 list ，必须通过宏语句 "#include <list>" 包含进来，才能对 list 双向链表容器进行开发。
创建 list 对象
为了管理双向链表的元素数据，必须先用 list 容器的构造函数，创建一个 list 对象。
1. list()
创建一个没有任何元素的 list 对象。此构造函数是 list(const A& a = A()) 的一个默认调用方式，其中 A 为内存分配器。
如下一行代码创建了一个空的 list 对象 lInt
list<int> lInt;
2. list(size_type n)
创建一个链接有 n 个元素的 list 对象，每个元素采用它的类型下的默认值。
例如，下面一行代码创建了具有 10 个元素的 list 对象 lInt ，每个元素初始值为 0 。
list<int> lInt;
3. list(size_type, const T& value)
创建一个有 n 个元素的 list 对象，这些元素的初始值均为 value ，
例如，下面一行代码创建了一个具有 10 个元素的 list 对象 lDou ，每个元素的初始值为 1.111 ；
list<double> lDou(10, 1.111);
4. list(const list&)
list拷贝构造函数，通过拷贝一个 list 对象的元素，创建一个新的 list 对象。此时，新旧 list 容器的元素对应相等。
例如，下面使用 list 对象 lChr1 , 创建另一个 list 对象 lChr2 ，lChr1 对象的 5 个元素也具有字符值 "K"
list<char> lChr1(5, 'K');
list<char> lChr2(lChr1);
5. list(InputIterator first, InputIterator last)
将另一个 list 对象的迭代器区间 [first, last) 所指的元素，拷贝到新创建的 list 对象中。它是更完整的 list(const InputIterator first, const InputIterator last, const A& a=A())构造函数的一个省略写法。
例如，下面代码将数组 iArray 的 3 个整数插入链表中，创建 list 对象 l
int iArray[] = {19, 13, 38};
初始化赋值
利用 list 提供的 push_back() 函数，可将元素依次链入链表中。 push_back() 函数常用于 list 容器的初始化。
元素的遍历
由于链表中的数据需要一个个元素进行遍历，因此， list 元素的遍历中有使用迭代器的方式进行。
用迭代器遍历 list 元素
1 -------------------------------------------------------- 用迭代器遍历 list 元素
2 #include <list>
3 #include <iostream>
4 using namespace std;
5
6 struct student
7 {
8 char * name; // 姓名
9 int age; // 年龄
10 char * city; // 城市
11 char * tel; // 电话
12 };
13
14 int main()
15 {
16 student s[]= {
17 { " 何亮 " , 18 , " 北京市 " , " 158 2652 7**4 " },
18 { " 何小亮 " , 17 , " 上海市 " , " 158 2652 7**5 " },
19 { " 何大亮 " , 20 , " 深圳市 " , " 158 2652 7**6 " },
20 { " 何生亮 " , 8 , " 荆州市 " , " 158 2652 7**7 " }
21 };
22 // 装入链表数据
23 list<student> lStu;
24 lStu.push_back(s[ 0 ]);
25 lStu.push_back(s[ 1 ]);
26 lStu.push_back(s[ 2 ]);
27 lStu.push_back(s[ 3 ]);
28 // 遍历打印链表元素
29 list<student> ::iterator i, iend;
30 iend = lStu.end();
31 cout << " 姓名 年龄 城市 电话 " << endl;
32 cout << " --------------------------- " << endl;
33
34 // 此处，用++i的效率比i++的效率更高。可以参考STL方面的书籍
35 // STL方面的书籍说，后缀++，会产生临时对象，一般不使用；
36 for (i=lStu.begin(); i!=iend; ++ i)
37 {
38 cout << (*i).name << " " ;
39 cout << (*i).age << " " ;
40 cout << (*i).city << " " ;
41 cout << (*i).tel << " " ;
42 cout << endl;
43 }
44 cout << " ------------------------------------ " << endl << endl;
45
46 return 0 ;
47 }
插入 list 链表元素
1 /* 解释：
2 push_back 函数在 list 尾部添加元素；
3 push_front 函数在 list 链首插入元素；
4 iterator insert(iterator pos, const T& x) 在任意位置插入元素
5 */
6
7 -------------------------------------------------------- 插入 list 链表元素
8 #include <list>
9 #include <iostream>
10 using namespace std;
11 int main()
12 {
13 list< int > lInt;
14 lInt.push_back( 1 );
15 lInt.push_back( 3 );
16 lInt.push_back( 4 );
17 lInt.push_back( 5 );
18 // 插入链表元素
19 list< int > ::iterator i, iend;
20 i = lInt.begin();
21 ++i; // 因为是 链表结构，所以，只能通过指针的移位找到要插入的位置
22 lInt.insert(i, 20 ); // 在第2个位置，插入元素 20
23 lInt.push_front( 0 );
24 // 打印链表元素
25 iend = lInt.end();
26 for (i=lInt.begin(); i!=iend; ++ i)
27 cout << *i << ' ' ;
28 cout << endl;
29
30 return 0 ;
31 }
list 链表元素的删除
1 /* 解释：
2 list 同样具有高效的链表元素删除处理，包括删除首元素的 pop_front 函数、删除末尾元素的 pop_back 函数和删除任一【指定迭代器位置】处元素的函数。
3 1. void pop_front() 删除 list 的第一个链表元素
4 2. void pop_back() 删除 list 的最后一个链表元素
5 3. iterator erase(iterator pos) 删除 pos 所指向的链表元素
6 4. iterator erase(iterator first, iterator last) 删除迭代器区间 [first, last) 所指向的所有链表元素
7 5. void clear() 删除所有 list 链表元素
8 6. void remove(const T& value) 删除 list 链表中所有元素值为 value 的元素
9 */
10
11 -------------------------------------------------------- list 链表元素的删除
12 #include <list>
13 #include <iostream>
14 using namespace std;
15 int main()
16 {
17 list< int > lInt;
18 lInt.push_back( 5 );
19 lInt.push_back( 6 );
20 lInt.push_back( 7 );
21 lInt.push_back( 8 );
22 lInt.push_back( 9 );
23 lInt.push_back( 9 );
24 lInt.push_back( 9 );
25 lInt.push_back( 10 );
26
27 list< int > ::iterator i, iend;
28 i = lInt.begin();
29 ++ i;
30 lInt.erase(i); // 删除 第 2 个元素 6
31 lInt.pop_back(); // 删除末元素 10
32 lInt.pop_front(); // 删除首元素 5
33 lInt.remove( 9 ); // 删除元素值为 9 的全部元素
34 // 打印 , 剩下 7 和 8
35 iend = lInt.end();
36 for (i=lInt.begin(); i!=iend; ++ i)
37 cout << *i << ' ' ;
38 cout << endl;
39
40 return 0 ;
41 }
元素的反向遍历：
reverse_iterator rbegin()
reverse_iterator rend()
下面代码段，反向遍历 list 链表元素，然后输出
// list<int> lInt;
list<int>::reverse_iterator ri, riend;
riend = lInt.rend();
// 仔细思考
for (ri=lInt.rbegin(); ri!=riend; ++ri)
cout << *ri;
list 的交换:
list容器的 swap 函数，通过简单地交换两个 list 的头指针，来实现 list 元素的交换。交换后的 list 将具有另一个 list 的链表元素。
void swap(list&)
例如：下面的 list 对象 lIntA 和 lIntB 进行了交换
// list<int> lIntA, lIntB;
lIntA.swap(lIntB);
list 链表的归并
1 /* 解释：
2 list 的归并
3 list 链表元素的排序，是将 list 链表分割成若干部分进行子排序，然后通过归并处理，实现 list 的所有元素的排序。为此，list 容器提供了 splice 和 merge 归并函数。
4 void splice(iterator position, list& x) 将 x 的链表归并到当前 list 链表的 position 位置之前， list 对象 x 将被清空
5 void splice(iterator position, list& x, iterator i) 将一个 list 的迭代器 i 值所指的元素，归并到当前 list 列表中，并将被归并的元素从原链表中删除。
6 void merge(list& x) 将 list 对象 x 的链表归并到当前 list 链表中，并清空 x 的链表。从 merge 函数的源码可看出，中有当前 list 链表 和被归并的 x 链表的元素，均预先按照元素值的 "<" 关系排好，merge 函数才具有意义，归并后的链表元素也是按 "<" 关系排序的。
7
8 如下说明 splice 和 merge 函数用法的示例程序，首先依序装入 1~10 的整数到 list 对象 l,然后，调用 list 对象 carry 的 splice 函数获取第 1 个元素，并打印 carry 和 1 的链表元素。创建一个 list 对象 x , 装入排序好的数据，调用 merge 函数将 x 归并到 l ， 此时 x 为空，l 变为一个更大的已排好序的 list 对象。
9 */
10
11 -------------------------------------------------------- list 链表的归并
12 #include <list>
13 #include <iostream>
14 using namespace std;
15 void print(list< int >& l);
16 int main()
17 {
18 list< int > l;
19 for ( int j= 1 ; j<= 10 ; j++ )
20 {
21 l.push_back(j);
22 }
23 // splice() 函数
24 list< int > carry;
25 carry.splice(carry.begin(), l, l.begin());
26 // 打印 carry
27 cout << " carry 的链表元素为: " ;
28 print(carry);
29 // 打印 l
30 cout << " l 的链表的元素为： " ;
31 print(l);
32 // merge() 函数用法
33 list< int > x;
34 x.push_back( 30 );
35 x.push_back( 31 );
36 x.push_back( 32 );
37 l.merge(x);
38 // 打印 x
39 cout << " x 的链表元素为空 " ;
40 print(x);
41 // 打印l
42 cout << " l 的链表元素为： " ;
43 print(l);
44
45 return 0 ;
46 }
47
48 // list 链表打印
49 void print(list< int >& l)
50 {
51 list< int > ::iterator i, iend;
52 iend = l.end();
53 for (i=l.begin(); i!=iend; ++ i)
54 cout << *i << ' ' ;
55 cout << endl << endl;
56 }
list 链表元素的排序
1 /* 解释：
2 list 提供的 void sort 函数，按 "<" 关系进行 list 链表元素排序，较小的元素排在前面。
3 下面的示例程序将 0~18 的降序排列的整数，依次装入 list 对象 l 的链表中，然后调用 sort 函数，按 0~18 的顺序排序元素。
4 */
5
6 -------------------------------------------------------- list 链表元素的排序
7 #include <list>
8 #include <iostream>
9 using namespace std;
10 void print(list< int >& l);
11 int main()
12 {
13 list< int > l;
14 for ( int j= 18 ; j>= 0 ; j-- )
15 l.push_back(j);
16 cout << " 排序前： " ;
17 print(l);
18 // 调用 list<int>::sort() 函数排序
19 l.sort();
20 cout << " 排序后 " ;
21 print(l);
22
23 return 0 ;
24 }
25
26 // 打印 list 链表元素
27 void print(list< int >& l)
28 {
29 list< int > ::iterator i, iend;
30 iend = l.end();
31 for (i=l.begin(); i!=iend; ++ i)
32 cout << *i << ' ' ;
33 cout << endl;
34 }
list 连续重复元素的删除
1 /* 解释：
2 利用 list 提供的 void unique 函数，可将连续重复的元素删除。仅保留一个。
3 例如，下面的示例程序，用 list 对象 l 装入 6 、8 、6 、6 、6 、9 、13 和 6 等整数，然后调用 unique 函数，把中级的 3 个连续元素 “6” 删除，最后打印 “ 6 8 6 9 13 6 ”。
4 */
5
6 -------------------------------------------------------- list 连续重复元素的删除
7 #include <list>
8 #include <iostream>
9 using namespace std;
10 int main()
11 {
12 list< int > l;
13 l.push_back( 6 );
14 l.push_back( 8 );
15 l.push_back( 6 );
16 l.push_back( 6 );
17 l.push_back( 6 );
18 l.push_back( 9 );
19 l.push_back( 13 );
20 l.push_back( 6 );
21
22 // 去处连续的元素
23 l.unique();
24 list< int > ::iterator i, iend;
25 iend = l.end();
26 for (i=l.begin(); i!=iend; ++ i)
27 cout << *i << ' ' ;
28 cout << endl;
29
30 return 0 ;
31 }
-------------------------- list 小结
list 双向链表容器采用双向链表的数据结构来存储元素数据，可高效查找、插入和删除容器元素。
list 提供的 splice 和 merge 归并函数，可用于链表的元素排序。sort 函数充分利用 list 的数据结构特点，对元素进行了归并排序。
list 缺点：查找某个元素的时候，经常需要遍历整个链表才能找到。如果，对 查找 的需求很频繁，list 不合适。
list 优点：元素插入、删除 操作非常频繁的时候，用 list 容器比较合适。
【好好学习，天天向上】 ||||||| 【 亮仔 到此一游 】
分类: STL学习笔记
标签: STL , C++ , 容器 , list
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息