C++ STL

c语言中文网的STL教程

stl 是一个将算法与底层抽象实现相分离的库，通过它我们可以很轻松地，高效地实现很多复杂的算法。但是学习stl不仅仅要学习其使用方式，更重要的是学习其底层实现，若是掌握了其底层实现逻辑，则不仅拥有了扎实的数据结构的基本功，更是在c++修仙之路上修炼了一本武林秘籍。

c++ stl 的头文件有： 

1
2
3
4
5
6
7
8
9
10
11
12
13
<iterator>      
<functional>    
<vector>    
<deque>     
<list>      
<queue>     
<stack>     
<set>       
<map>       
<algorithm>     
<numeric>       
<memory>        
<utility>

stl提供三种标准容器，分别为序列容器，排序容器，哈希容器。后两种也称为关联容器。

容器种类 功能
序列容器 主要包括vector，list，deque。元素在容器中的位置和元素的值没有关系，容器是非排序的。将元素插入时，指定在什么位置，元素就会在什么位置
排序容器 包含set,multiset,map,multimap.元素默认是从大到小排好的，插入元素时元素会自动插入到适当的位置。关联容器在查找时有着很好的性能。
哈希容器 unordered_set,unordered_map,unordered_multiset,unordered_multimap。和排序容器不同，哈希容器中元素的位置是未排序的，元素的位置有哈希函数确定。

迭代器

stl标准库为每一种容器定义了一种迭代器，不同的容器迭代器不同，其功能强弱也不同。

  1. 前向迭代器(forward iterator)
    假设p是一个前向迭代器，则p支持p++,++p,*p操作，可以用相互赋值，可以使用==与!=进行比较。
  2. 双向迭代器(bidirectional iterator)
    相比于前向迭代器，可以进行–p和p–操作。
  3. 随机访问迭代器(random acccess iterator)
    除了双向迭代器的所有操作还支持以下操作：
    1. p+=i
    2. p-=i
    3. p+i
    4. p-i
    5. p[i]

不同容器的迭代器

容器 迭代器
array 随机
vector 随机
deque 随机
list 双向
set/multiset 双向
map/multimap 双向
forward_list 前向
unordered_set/unordered_multiset 前向
unordered_map/unordered_multimap 前向
stack 不支持
queue 不支持

迭代器的定义方式

迭代器类型 具体格式
正向迭代器 容器类名::iterator 迭代器名
常量正向迭代器 容器类名::const_iterator 迭代器名;
反向迭代器 容器类名::reverse_iterator 迭代器名
常量反向迭代器 容器类名::const_reverse_iterator 迭代器名

序列式容器

array

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
73
#include <iostream>
#include <array>
using namespace std;
int main()
{
    array<int, 4> myarray{};
    //初始化 myarray 容器为 {0,1,2,3}
    for (int i = 0; i < myarray.size(); i++)
    {
        myarray.at(i) = i;
    }
    //使用 get() 重载函数输出指定位置元素
    cout << get<3>(myarray) << endl;
    cout << myarray[3] << endl;

    //正向迭代器
    array<int, 4>::iterator it;
    if (!myarray.empty())
        for (it = myarray.begin(); it <= myarray.end() - 1; it++)
            cout << *it << " ";
    cout << endl;
    //反向迭代器
    array<int, 4>::reverse_iterator it_r;
    if (!myarray.empty())
        for (it_r = myarray.rend() - 1; it_r >= myarray.rbegin(); it_r--)
            cout << *it_r << " ";
    cout << endl;

    //随机访问
    int index = 1;
    cout << myarray[index] << " " << myarray[index + 1] << endl;
    //返回容器中第一个元素的直接引用，该函数不适用于空的 array 容器。
    cout << myarray.front() << endl;
    //返回容器中最后一个元素的直接应用，该函数同样不适用于空的 array 容器。
    cout << myarray.back() << endl;

    //返回一个指向容器首个元素的指针。利用该指针，可实现复制容器中所有元素等类似功能。
    int *p = myarray.data();
    cout << *p << endl;

    //将值赋值给容器中的每个元素。
    myarray.fill(9);
    if (!myarray.empty())
        for (it = myarray.begin(); it <= myarray.end() - 1; it++)
            cout << *it << " ";
    cout << endl;

    //交换 array1 和 array2 容器中的所有元素，但前提是它们具有相同的长度和类型。
    array<int, 10> array1;
    array1.fill(1);
    array<int, 10> array2;
    array2.fill(2);
    array<int, 10>::iterator it_10;
    if (!array1.empty())
        for (it_10 = array1.begin(); it_10 <= array1.end() - 1; it_10++)
            cout << *it_10 << " ";
    cout << endl;
    if (!array2.empty())
        for (it_10 = array2.begin(); it_10 <= array2.end() - 1; it_10++)
            cout << *it_10 << " ";
    cout << endl;
    //交换
    array1.swap(array2);
    if (!array1.empty())
        for (it_10 = array1.begin(); it_10 <= array1.end() - 1; it_10++)
            cout << *it_10 << " ";
    cout << endl;
    if (!array2.empty())
        for (it_10 = array2.begin(); it_10 <= array2.end() - 1; it_10++)
            cout << *it_10 << " ";
    cout << endl;
}

vector

vector 容器是 STL 中最常用的容器之一，它和 array 容器非常类似，都可以看做是对 C++ 普通数组的“升级版”。不同之处在于，array 实现的是静态数组（容量固定的数组），而 vector 实现的是一个动态数组，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间，整个过程无需人工干预。vector 常被称为向量容器，因为该容器擅长在尾部插入或删除元素，在常量时间内就可以完成，时间复杂度为O(1)；而对于在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶O(n)。

还需注意的是，如果调用 reserve() 来增加容器容量，之前创建好的任何迭代器（例如开始迭代器和结束迭代器）都可能会失效，这是因为，为了增加容器的容量，vector 容器的元素可能已经被复制或移到了新的内存地址。所以后续再使用这些迭代器时，最好重新生成一下。

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <iostream>
#include <array>
#include <vector>
using namespace std;
int main()
{
    vector<double> v0{1.0, 2.0, 3.0};
    //获取当前容量
    cout << v0.capacity() << endl;
    //申请100个元素空间，增加容器的容量。
    //如果vector的容量在执行此语句之前，已经大于或等于100个元素，那么这条语句什么也不做；
    v0.reserve(100);
    cout << v0.capacity() << endl;
    //减少内存到当前元素实际使用的的大小
    v0.shrink_to_fit();
    cout << v0.capacity() << endl;
    //实际使用元素个数
    cout << v0.size() << endl;

    //迭代器
    vector<double>::iterator it1;
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    //反向迭代器在array中示范过，不再赘述。

    //指定元素个数，其默认值都为0
    vector<double> v1(100);
    if (!v0.empty())
        for (it1 = v1.begin(); it1 <= v1.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    //指定默认值为10
    vector<double> v2(100, 10);
    if (!v0.empty())
        for (it1 = v2.begin(); it1 <= v2.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    //使用已经存在的vector创建新的vector
    vector<double> v3(v2);
    if (!v0.empty())
        for (it1 = v3.begin(); it1 <= v3.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    //也可以只取一部分
    vector<double> v4(v2.data(), v2.data() + 1);
    if (!v0.empty())
        for (it1 = v4.begin(); it1 <= v4.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;

    //使用下标访问
    cout << v0[0] << endl;
    cout << v0.at(0) << endl;

    //返回第一个元素的引用
    cout << v0.front() << endl;
    //返回最后一个元素的引用
    cout << v0.back() << endl;

    //替换原有的元素
    v0.assign(v1.data(), v1.data() + 5);
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;

    //在尾部插入元素
    v0.push_back(1);
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    //从尾部移除元素
    v0.pop_back();
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;

    //在指定位置插入一个或者多个元素
    it1 = v0.begin();
    //在指定位置插入元素，返回指向该元素的迭代器
    cout << *it1 << endl;
    it1 = v0.insert(it1, 1);
    cout << *it1 << endl;
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    //在指定位置前插入多个元素 插入两个4
    it1 = v0.begin();
    v0.insert(it1, 2, 4);
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    //在指定为之前插入指定元素，同assign
    //事实证明，是先将源内存区域的数据复制下来再插入进入。
    it1 = v0.begin();
    v0.insert(it1, v0.data(), v0.data() + 7);
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;

    //删除指定的元素
    it1 = v0.begin();
    v0.erase(it1);
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    //依次删除所有元素 注意这里，删除迭代器指向的元素之后，后面的元素会自动前移，所以不需要更新迭代器。
    it1 = v0.begin();
    while (it1 != v0.end())
        v0.erase(it1);
    if (v0.empty())
        cout << "空了" << endl;
    //删除指定区间的元素 前闭后开
    for (int i = 0; i <= 10; i++)
        v0.push_back(i);
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    it1 = v0.begin();
    v0.erase(it1, it1 + 2);
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;

    //清理元素 元素没有了，但是容量还在 事实证明擦除的内存被写入了-4.8367e-26
    int re_size = v0.size();
    it1 = v0.begin();
    for (int i = 0; i <= re_size; i++)
        cout << *(it1 + i) << endl;
    cout << v0.capacity() << endl;
    cout << v0.size() << endl;
    v0.clear();
    cout << v0.capacity() << endl;
    cout << v0.size() << endl;
    if (v0.empty())
        cout << "空了" << endl;
    v0.reserve(100);
    it1 = v0.begin();
    for (int i = 0; i <= re_size; i++)
        cout << *(it1 + i) << endl;

    //交换元素
    v0.clear();
    v1.clear();
    v0.push_back(0);
    v1.push_back(1);
    it1 = v0.begin();
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    it1 = v1.begin();
    if (!v1.empty())
        for (it1 = v1.begin(); it1 <= v1.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    v0.swap(v1);
    it1 = v0.begin();
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    it1 = v1.begin();
    if (!v1.empty())
        for (it1 = v1.begin(); it1 <= v1.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;

    //再指定位置直接生成一个元素 emplace 一次只可以插入一个元素，效率比insert高
    it1 = v0.begin();
    v0.emplace(it1, 2);
    it1 = v0.begin();
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
    //相当于 push_back
    v0.emplace_back(3);
    it1 = v0.begin();
    if (!v0.empty())
        for (it1 = v0.begin(); it1 <= v0.end() - 1; it1++)
            cout << *it1 << " ";
    cout << endl;
}

deque 双队列容器

和 vector 相比，额外增加了实现在容器头部添加和删除元素的成员函数，同时删除了 capacity()、reserve() 和 data() 成员函数。

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
#include <iostream>
#include <array>
#include <vector>
#include <deque>
using namespace std;
int main()
{
    deque<int> dq{0, 1, 2, 3, 4, 5};
    deque<int>::iterator it;
    it = dq.begin();
    if (!dq.empty())
        for (it = dq.begin(); it <= dq.end() - 1; it++)
            cout << *it;
    cout << endl;
    //相vector额外怎增加了从头删除与加入元素的额方法。
    dq.push_front(1);
    it = dq.begin();
    if (!dq.empty())
        for (it = dq.begin(); it <= dq.end() - 1; it++)
            cout << *it;
    cout << endl;
    dq.pop_front();
    it = dq.begin();
    if (!dq.empty())
        for (it = dq.begin(); it <= dq.end() - 1; it++)
            cout << *it;
    cout << endl;
}

list 双链表容器

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#include <array>
#include <vector>
#include <deque>
#include <list>
using namespace std;

bool demo(int a, int b)
{
    return (a <= b);
}
int main()
{
    list<int> l(10, 0);
    list<int>::iterator it;
    it = l.begin();
    if (!l.empty())
        for (it = l.begin(); it != l.end(); it++)
            cout << *it;
    cout << endl;

    //好多和vector重复的函数就不再赘述。
    //由于是双向链表，故前后都可以插入删除，和deque一样。

    //删除所有指定大小的元素
    l.remove(0);
    if (l.empty())
        cout << "你把0都删除了，我空了" << endl;
    list<int> l2(5, 2);

    //将一个 list 容器中的元素插入到另一个容器的指定位置。
    //当begin==end 时，为空，所以下面也可以换成 l.end()
    l.splice(l.begin(), l2);
    it = l.begin();
    if (!l.empty())
        for (it = l.begin(); it != l.end(); it++)
            cout << *it;
    cout << endl;

    l = {1, 1, 2, 2, 3, 4, 5, 6, 6, 7, 7, 9, 10, 10, 1};
    it = l.begin();
    if (!l.empty())
        for (it = l.begin(); it != l.end(); it++)
            cout << *it;
    cout << endl;
    //删除容器中相邻的重复元素，只保留一个。 可见只比较相邻的，若要实现真正的unique需要结合sort()进行排序
    l.unique();
    it = l.begin();
    if (!l.empty())
        for (it = l.begin(); it != l.end(); it++)
            cout << *it;
    cout << endl;
    //使用一个二元谓语函数作为参数删除 此函数的作用是自定义前后两个元素的关系。
    //此例时若前一个元素值比后一个小则删除掉前一个
    l.unique(demo);
    it = l.begin();
    if (!l.empty())
        for (it = l.begin(); it != l.end(); it++)
            cout << *it;
    cout << endl;
    //排序
    l.sort();
    l.unique();
    it = l.begin();
    if (!l.empty())
        for (it = l.begin(); it != l.end(); it++)
            cout << *it;
    cout << endl;
    //合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。 事实证明合并前的list必须都排好序。
    l2 = {1, 4, 2, 31, 54, 234, 2, 523, 42, 42, 10};
    l.merge(l2);
    it = l.begin();
    if (!l.empty())
        for (it = l.begin(); it != l.end(); it++)
            cout << *it << " ";
    cout << endl;
    l.sort();
    l2.sort();
    l.merge(l2);
    l.unique();
    it = l.begin();
    if (!l.empty())
        for (it = l.begin(); it != l.end(); it++)
            cout << *it << " ";
    cout << endl;

    //反转容器内元素的顺序
    l.reverse();
    it = l.begin();
    if (!l.empty())
        for (it = l.begin(); it != l.end(); it++)
            cout << *it << " ";
    cout << endl;

    //条件删除 remove_if
    //现在我对泛型不太了解，明日有精力了再写。
}

forward_list

其实就是单链表，相比于双向链表list,forward_list 更加有效率，但是不能进行逆向遍历的操作。当一个操作list与forward_list都可以做的时候，应该优先选用forward_list.

关联式容器

关联式容器再存储元素的时候还会给每一个元素配备一个键，整体以键值相配对的方式进行存储，可以通过键值直接索引到元素无需遍历整个容器，再存储元素的时候会默认按照各个元素的大小做升序排列。关联式容器在更删改查的效率更高。关联式容器在底层使用红黑树进行实现。

关联式容器包括： 

1
2
3
4
map
multimap
set
multiset
容器 特点
map 元素的键是唯一的，根据各元素键的大小进行升序排序
set 元素的键是唯一的,根据各元素键的大小进行升序排序
multimap 和map的区别在于键可以重复
multiset 和set的区别在于键可以重复

map

map容器存储的都是pair对象。

pair<const K, T>

键是不可以修改的。值是可以修改的。

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
#include <map>
#include <iostream>
using namespace std;
int main()
{
    //声明
    map<int, string> mymap{{3, "三"}, {4, "四"}};
    //插入元素 可以像数组一样进行 [] 运算
    mymap[1] = "一";
    mymap[2] = "二";

    //迭代器
    map<int, string>::iterator it;
    //遍历
    it = mymap.begin();
    if (!mymap.empty())
        for (it = mymap.begin(); it != mymap.end(); it++)
            cout << it->first << " " << it->second << endl;
    //试着插入一个重复的键值 事实证明重复插入就取代了之前的
    mymap[1] = "新一";
    it = mymap.begin();
    if (!mymap.empty())
        for (it = mymap.begin(); it != mymap.end(); it++)
            cout << it->first << " " << it->second << endl;

    //下面介绍相比与vector特有的成员函数。
    //根据键查找元素，返回一个指向结果元素的迭代器。
    it = mymap.find(1);
    cout << it->first << " " << it->second << endl;
    //返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器.
    it = mymap.lower_bound(2);
    cout << it->first << " " << it->second << endl;
    //返回一个指向当前 map 容器中第一个大于 key 的键值对的迭代器
    it = mymap.upper_bound(2);
    cout << it->first << " " << it->second << endl;
    //返回一个范围 两个it组成的一个pair,该范围中包含的键为 key 的键值对.
    //因为map中元素的唯一性，所以该范围最多包含一个键值对。前闭后开。
    pair<map<int, string>::iterator, map<int, string>::iterator> pair;
    pair = mymap.equal_range(2);
    cout << "范围low: " << pair.first->first << " " << pair.first->second << endl;
    cout << "范围high: " << pair.second->first << " " << pair.second->second << endl;

    //可以像数组一样进行 [] 运算 若不存在的话就插入一个key,其value为空。
    cout << mymap[8] << endl;
    cout << mymap[1] << endl;
    //at找到 map 容器中 key 键对应的值，如果找不到，该函数会引发 out_of_range 异常。
    cout << mymap.at(2) << endl;
    if (!mymap.at(8).empty())
        cout << mymap.at(8) << endl;
    //else cout<<"该key没有对应"<<endl;

    //插入 若插入的元素已经存在的话则会插入失败，所以需要删除在插入或者修改。
    mymap.insert({5, "五"});
    mymap.insert({5, "肆虐五"});
    it = mymap.begin();
    if (!mymap.empty())
        for (it = mymap.begin(); it != mymap.end(); it++)
            cout << it->first << " " << it->second << endl;
    //删除
    mymap.erase(8);
    it = mymap.begin();
    if (!mymap.empty())
        for (it = mymap.begin(); it != mymap.end(); it++)
            cout << it->first << " " << it->second << endl;

    //交换两个容器的内容 swap() 不在赘述

    //统计key出现的次数
    cout << mymap.count(1) << endl;
}

multimap

multimap 比 map 除了可以拥有重复的额值之外，没有什么不同的。略过。

set

和 map、multimap 容器不同，使用 set 容器存储的各个键值对，要求键 key 和值 value 必须相等。

其余和map没啥不同，set就是集合，所以也不可以重复。

multiset

multiset 比 set 除了可以拥有重复的额值之外，没有什么不同的。略过。

无序关联式容器

无序关联式容器，又称哈希容器。和关联式容器一样，此类容器存储的也是键值对元素；不同之处在于，关联式容器默认情况下会对存储的元素做升序排序，而无序关联式容器不会。和其它类容器相比，无序关联式容器擅长通过指定键查找对应的值，而遍历容器中存储元素的效率不如关联式容器。

关联式容器的底层实现采用的树存储结构，更确切的说是红黑树结构；
无序容器的底层实现采用的是哈希表的存储结构。

无序容器内部存储的键值对是无序的，各键值对的存储位置取决于该键值对中的键，
和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器。

包含有 4 个具体容器，分别为 unordered_map、unordered_multimap、unordered_set 以及 unordered_multiset。

c++ 的常用算法