list 容器讲解
- 使用双向链表管理元素
- list的元素可以是任意类型T，但必须具备赋值和拷贝能力
- 必须包含的头文件
#include <list> - list不支持随机存取，因此不提供下标操作符
- 在任何位置上执行元素的安插和移除都非常快。
- 安插和删除不会导致指向其他元素的指针、引用、iterator失效。
特性
- 底层数据结构是双向链表
- 不支持随机存取,所以不能使用下标操作
- 在任意位置上插入和删除都很快
- 插入和删除不会导致其它元素的指针,引用,iterator失效
plaintext
|------------------------------+----------------------------------------------------------|
| list | |
|------------------------------+----------------------------------------------------------|
| 支持的迭代器类型 | 双向 |
|------------------------------+----------------------------------------------------------|
| 创建list | |
|------------------------------+----------------------------------------------------------|
| list<T> c | 创建一个空的list |
| list<T> c1(c2) | 复制c2创建一个c1 list |
| list<T> c(n) | 创建n个元素,值是T类型的默认构造函数产生的 |
| list<T> c(n,e) | 创建n个元素,值是e |
| list<T> c(beg,end) | 创建n个元素,以区间[beg,end)为初值 |
| ~list<T>() | 销毁所有元素,释放内存 |
|------------------------------+----------------------------------------------------------|
| 基本操作 | |
|------------------------------+----------------------------------------------------------|
| c.size() | 返回元素的个数 |
| c.empty() | 是否为空 |
| c.max_size() | 返回元素的最大可能数量 |
| ==,!=,<,<=,>,>= | 逻辑运算 |
|------------------------------+----------------------------------------------------------|
| 赋值操作 | |
|------------------------------+----------------------------------------------------------|
| c1 = c2 | c2赋值给c1 |
| c.assign(n,e) | 将元素e的n个拷贝赋值给c |
| c.assign(beg,end) | 将[beg,end)内的值赋给c |
| c1.swap(c2) | 交换 |
| swap(c1,c2) | 交换 |
|------------------------------+----------------------------------------------------------|
| 存入读取 | |
|------------------------------+----------------------------------------------------------|
| front() | 第一个元素的引用,不检查元素是否存在[1] |
| back() | 最后一个元素的引用,不检查元素是否存在 |
|------------------------------+----------------------------------------------------------|
| 迭代器[2] | |
|------------------------------+----------------------------------------------------------|
| c.begin() | 指向第一个元素的迭代器 |
| c.end() | 指向最后一个元素后面一个位置的迭代器 |
| rbegin() | 逆向迭代器,反向的第一个元素(也就是最后一个)迭代器 |
| rend() | 逆向迭代器,反向在最后一个元素后面一个位置的迭代器 |
|------------------------------+----------------------------------------------------------|
| 插入操作 | |
|------------------------------+----------------------------------------------------------|
| c.insert(pos,e) | pos位置(迭代器)前插入e的拷贝,返回新元素的位置的位置 |
| c.insert(pos,n,e) | pos位置(迭代器)前插入e的n个拷贝 |
| c.push_back(e) | 在尾部压入元素e的拷贝 |
| c.push_front(e) | 在头部压入元素e的拷贝 |
|------------------------------+----------------------------------------------------------|
| 删除操作 | |
|------------------------------+----------------------------------------------------------|
| c.pop_back() | 删除最后一个元素,不会返回元素的引用 |
| c.pop_front() | 删除第一个元素,不会返回元素的引用 |
| c.erase(pos) | 删除pos(迭代器)位置的元素,返回下一个元素的位置 |
| c.erase(beg,end) | 删除[beg,end)位置内的元素,返回下一个元素的位置 |
| c.clear() | 删除所有元素,并清空容器所占的内存 |
| c.resize(num) | 将元素数量改为num,多佘的删除,多出的用default构造函数产生 |
| c.resize(num,e) | 将元素数量改为num,多佘的元素为e的拷贝 |
| c.remove(val) | 删除值为val的元素 |
| c.remove_if(op) | 删除op(val) == true 为的元素 |
|------------------------------+----------------------------------------------------------|
| 特殊 | |
|------------------------------+----------------------------------------------------------|
| c.unique() | 删除重复元素,只留一个 |
| c.unique(op) | 删除op(val) == true 重复的元素,只留一个 |
| c.splice(pos,c2) | 将c2的所有元素转移到c1 pos 之前 |
| c.splice(pos,c2.c2pos) | 将c2内的c2pos的元素移到pos之前 |
| c.splice(pos,c2,c2beg,c2end) | 将c2内的[c2beg,c2end)内的元素移到c1 pos 之前 |
| c.sort() | 以 `<` 来排序 |
| c.sort(op) | 以op 为准排序 |
| c.merge(c2) | 归并排序c,c2,要求c,c2已经排序好 |
| c.reverse() | 将所有元素反序 |
|------------------------------+----------------------------------------------------------|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
注: list的迭代器不是随机迭代器,不能进行这种操作iter+10,iter-10,也不能使用下标进行操作,只能使用这种iter++,iter--
创建list
c
#include <iostream>
#include <list>
using namespace std;
int a[] = {1,2,3,4,5};
void printList(list<int> l,string s){
cout << s;
list<int>::iterator iter = l.begin();
for(;iter!=l.end();iter++){
cout << *iter << " ";
}
cout << endl;
}
int main(){
//创建
list<int> c;
printList(c,"c:");
list<int> c1(10,1);
printList(c1,"c1:");
list<int> c2(c1);
printList(c2,"c2:");
list<int> c3(10);
printList(c3,"c3:");
list<int> c4(c3.begin(),c3.end());
printList(c4,"c4:");
list<int> c5(a,a+sizeof(a)/sizeof(a[0]));
printList(c5,"c5:");
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
操作list
c
#include <iostream>
#include <list>
using namespace std;
int a[] = {1,2,3,4,5};
void printList(list<int> l,string s){
cout << s;
list<int>::iterator iter = l.begin();
for(;iter!=l.end();iter++){
cout << *iter << " ";
}
cout << endl;
}
int main(){
list<int> c(a,a+sizeof(a)/sizeof(a[0]));
printList(c,"c:");
//基本操作
cout << "c.size()" << c.size() << endl;
cout << "c.empty()" << c.empty() << endl;
cout << "c.max_size()" << c.max_size() << endl;
//赋值
list<int> c1 = c;
printList(c1,"c1:");
c1.swap(c);
//操作元素
c.insert(c.begin(),111);
printList(c,"c:");
c.insert(c.begin(),2,123);
printList(c,"c:");
c.push_back(321);
c.push_front(321);
printList(c,"c:");
//删除
c.pop_back();
c.pop_front();
printList(c,"c:");
c.erase(c.begin()++);
printList(c,"c:");
c.erase(c.begin(),c.end()--);
printList(c,"c:");
c.clear();
printList(c,"c:");
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54