目录
STL 容器
STL迭代器
array vector deque功能
list 和 forward_list 功能
vector emplace_back()和push_back()的区别
vector插入函数insert和emplace用法
vector删除元素函数
deque容器
deque反向迭代器
list容器
来源：C语言中文网：C语言程序设计门户网站(入门教程、编程软件)
STL 容器
序列容器是默认不排序的，比如数组向量vector，哈希容器用于快速查找效率是O(1)，排序容器用于查找最小最大效率也是O(1)
| 序列容器 |
主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。之所以被称为序列容器，是因为元素在容器中的位置同元素的值无关，即容器不是排序的。将元素插入容器时，指定在什么位置，元素就会位于什么位置。 |
| 排序容器 |
包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素默认是由小到大排序好的，即便是插入元素，元素也会插入到适当位置。所以关联容器在查找时具有非常好的性能。 |
| 哈希容器 |
C++ 11 新加入 4 种关联式容器，分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。和排序容器不同，哈希容器中的元素是未排序的，元素的位置由哈希函数确定。 |
STL迭代器
迭代器用于对元素进行顺序访问（或倒序）
- 对正向迭代器进行 ++ 操作时，迭代器会指向容器中的后一个元素；
- 而对反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素。
- *迭代器 指向 特定元素
- array vector deque支持随机访问迭代器 支持++ -- < == != +=
- stack queue不支持迭代器
//遍历 vector 容器。
#include <iostream>
//需要引入 vector 头文件
#include <vector>
using namespace std;
int main()
{
vector<int> v{1,2,3,4,5,6,7,8,9,10}; //v被初始化成有10个元素
cout << "第一种遍历方法：" << endl;
//size返回元素个数
for (int i = 0; i < v.size(); ++i)
cout << v[i] <<" "; //像普通数组一样使用vector容器
//创建一个正向迭代器，当然，vector也支持其他 3 种定义迭代器的方式
cout << endl << "第二种遍历方法：" << endl;
vector<int>::iterator i;
//用 != 比较两个迭代器
for (i = v.begin(); i != v.end(); ++i)
cout << *i << " ";
cout << endl << "第三种遍历方法：" << endl;
for (i = v.begin(); i < v.end(); ++i) //用 < 比较两个迭代器
cout << *i << " ";
cout << endl << "第四种遍历方法：" << endl;
i = v.begin();
while (i < v.end()) { //间隔一个输出
cout << *i << " ";
i += 2; // 随机访问迭代器支持 "+= 整数" 的操作
}
}
array vector deque功能
| 函数成员 |
函数功能 |
array<T,N> |
vector<T> |
deque<T> |
| begin() |
返回指向容器中第一个元素的迭代器。 |
是 |
是 |
是 |
| end() |
返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。 |
是 |
是 |
是 |
| rbegin() |
返回指向最后一个元素的迭代器。 |
是 |
是 |
是 |
| rend() |
返回指向第一个元素所在位置前一个位置的迭代器。 |
是 |
是 |
是 |
| cbegin() |
和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
是 |
是 |
是 |
| cend() |
和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
是 |
是 |
是 |
| crbegin() |
和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
是 |
是 |
是 |
| crend() |
和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
是 |
是 |
是 |
| assign() |
用新元素替换原有内容。 |
- |
是 |
是 |
| operator=() |
复制同类型容器的元素，或者用初始化列表替换现有内容。 |
是 |
是 |
是 |
| size() |
返回实际元素个数。 |
是 |
是 |
是 |
| max_size() |
返回元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。 |
是 |
是 |
是 |
| capacity() |
返回当前容量。 |
- |
是 |
- |
| empty() |
判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。 |
是 |
是 |
是 |
| resize() |
改变实际元素的个数。 |
- |
是 |
是 |
| shrink _to_fit() |
将内存减少到等于当前元素实际所使用的大小。 |
- |
是 |
是 |
| front() |
返回第一个元素的引用。 |
是 |
是 |
是 |
| back() |
返回最后一个元素的引用。 |
是 |
是 |
是 |
| operator[]() |
使用索引访问元素。 |
是 |
是 |
是 |
| at() |
使用经过边界检査的索引访问元素。 |
是 |
是 |
是 |
| push_back() |
在序列的尾部添加一个元素。 |
- |
是 |
是 |
| insert() |
在指定的位置插入一个或多个元素。 |
- |
是 |
是 |
| emplace() |
在指定的位置直接生成一个元素。 |
- |
是 |
是 |
| emplace_back() |
在序列尾部生成一个元素。 |
- |
是 |
是 |
| pop_back() |
移出序列尾部的元素。 |
- |
是 |
是 |
| erase() |
移出一个元素或一段元素。 |
- |
是 |
是 |
| clear() |
移出所有的元素，容器大小变为 0。 |
- |
是 |
是 |
| swap() |
交换两个容器的所有元素。 |
是 |
是 |
是 |
| data() |
返回指向容器中第一个元素的指针。 |
是 |
是 |
- |
list 和 forward_list 功能
| 函数成员 |
函数功能 |
list<T> |
forward_list<T> |
| begin() |
返回指向容器中第一个元素的迭代器。 |
是 |
是 |
| end() |
返回指向容器最后一个元素所在位置后一个位置的迭代器。 |
是 |
是 |
| rbegin() |
返回指向最后一个元素的迭代器。 |
是 |
- |
| rend() |
返回指向第一个元素所在位置前一个位置的迭代器。 |
是 |
- |
| cbegin() |
和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
是 |
是 |
| before_begin() |
返回指向第一个元素前一个位置的迭代器。 |
- |
是 |
| cbefore_begin() |
和 before_begin() 功能相同，只不过在其基础上，增加了 const 属性，即不能用该指针修改元素的值。 |
- |
是 |
| cend() |
和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
是 |
是 |
| crbegin() |
和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
是 |
- |
| crend() |
和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
是 |
- |
| assign() |
用新元素替换原有内容。 |
是 |
是 |
| operator=() |
复制同类型容器的元素，或者用初始化列表替换现有内容。 |
是 |
是 |
| size() |
返回实际元素个数。 |
是 |
- |
| max_size() |
返回元素个数的最大值，这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。 |
是 |
是 |
| resize() |
改变实际元素的个数。 |
是 |
是 |
| empty() |
判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。 |
是 |
是 |
| front() |
返回容器中第一个元素的引用。 |
是 |
是 |
| back() |
返回容器中最后一个元素的引用。 |
是 |
- |
| push_back() |
在序列的尾部添加一个元素。 |
是 |
- |
| push_front() |
在序列的起始位置添加一个元素。 |
是 |
是 |
| emplace() |
在指定位置直接生成一个元素。 |
是 |
- |
| emplace_after() |
在指定位置的后面直接生成一个元素。 |
- |
是 |
| emplace_back() |
在序列尾部生成一个元素。 |
是 |
- |
| cmplacc_front() |
在序列的起始位生成一个元索。 |
是 |
是 |
| insert() |
在指定的位置插入一个或多个元素。 |
是 |
- |
| insert_after() |
在指定位置的后面插入一个或多个元素。 |
- |
是 |
| pop_back() |
移除序列尾部的元素。 |
是 |
- |
| pop_front() |
移除序列头部的元素。 |
是 |
是 |
| reverse() |
反转容器中某一段的元素。 |
是 |
是 |
| erase() |
移除指定位置的一个元素或一段元素。 |
是 |
- |
| erase_after() |
移除指定位置后面的一个元素或一段元素。 |
- |
是 |
| remove() |
移除所有和参数匹配的元素。 |
是 |
是 |
| remove_if() |
移除满足一元函数条件的所有元素。 |
是 |
是 |
| unique() |
移除所有连续重复的元素。 |
是 |
是 |
| clear() |
移除所有的元素，容器大小变为 0。 |
是 |
是 |
| swap() |
交换两个容器的所有元素。 |
是 |
是 |
| sort() |
对元素进行排序。 |
是 |
是 |
| merge() |
合并两个有序容器。 |
是 |
是 |
| splice() |
移动指定位置前面的所有元素到另一个同类型的 list 中。 |
是 |
- |
| splice_after() |
移动指定位置后面的所有元素到另一个同类型的 list 中。 |
- |
是 |
容器名[n]这种获取元素的方式，需要确保下标 n 的值不会超过容器的容量（可以通过 capacity() 成员函数获取），否则会发生越界访问的错误。幸运的是，和 array 容器一样，vector 容器也提供了 at() 成员函数，当传给 at() 的索引会造成越界时，会抛出std::out_of_range异常。
vector容器
emplace_back()和push_back()的区别
emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。
vector插入函数insert和emplace用法
| 语法格式 |
用法说明 |
| iterator insert(pos,elem) |
在迭代器 pos 指定的位置之前插入一个新元素elem，并返回表示新插入元素位置的迭代器。 |
| iterator insert(pos,n,elem) |
在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器。 |
| iterator insert(pos,first,last) |
在迭代器 pos 指定的位置之前，插入其他容器（不仅限于vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器。 |
| iterator insert(pos,initlist) |
在迭代器 pos 指定的位置之前，插入初始化列表（用大括号{}括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器。 |
#include <iostream>
#include <vector>
#include <array>
using namespace std;
int main()
{
std::vector<int> demo{1,2};
//第一种格式用法
demo.insert(demo.begin() + 1, 3);//{1,3,2}
//第二种格式用法
demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}
//第三种格式用法
std::array<int,3>test{ 7,8,9 };
demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}
//第四种格式用法
demo.insert(demo.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}
for (int i = 0; i < demo.size(); i++) {
cout << demo[i] << " ";
}
return 0;
}
emplace() 是 C++ 11 标准新增加的成员函数，用于在 vector 容器指定位置之前插入一个新的元素。
vector删除元素函数
| 函数 |
功能 |
| pop_back() |
删除 vector 容器中最后一个元素，该容器的大小（size）会减 1，但容量（capacity）不会发生改变。 |
| erase(pos) |
删除 vector 容器中 pos 迭代器指定位置处的元素，并返回指向被删除元素下一个位置元素的迭代器。该容器的大小（size）会减 1，但容量（capacity）不会发生改变。 |
| swap(beg)、pop_back() |
先调用 swap() 函数交换要删除的目标元素和容器最后一个元素的位置，然后使用 pop_back() 删除该目标元素。 |
| erase(beg,end) |
删除 vector 容器中位于迭代器 [beg,end)指定区域内的所有元素，并返回指向被删除区域下一个位置元素的迭代器。该容器的大小（size）会减小，但容量（capacity）不会发生改变。 |
| remove() |
删除容器中所有和指定元素值相等的元素，并返回指向最后一个元素下一个位置的迭代器。值得一提的是，调用该函数不会改变容器的大小和容量。 |
| clear() |
删除 vector 容器中所有的元素，使其变成空的 vector 容器。该函数会改变 vector 的大小（变为 0），但不是改变其容量。 |
#include <vector>
#include <iostream>
using namespace std;
int main()
{
std::vector<int> demo{ 1,2,3,4,5 };
//删除 2、3
auto iter = demo.erase(demo.begin()+1, demo.end() - 2);
cout << "size is :" << demo.size() << endl;
cout << "capacity is :" << demo.capacity() << endl;
for (int i = 0; i < demo.size(); i++) {
cout << demo[i] << " ";
}
return 0;
}
remove删除相同元素
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
vector<int>demo{ 1,3,3,4,3,5 };
//交换要删除元素和最后一个元素的位置
auto iter = std::remove(demo.begin(), demo.end(), 3);
cout << "size is :" << demo.size() << endl;
cout << "capacity is :" << demo.capacity() << endl;
//输出剩余的元素
for (auto first = demo.begin(); first < iter;++first) {
cout << *first << " ";
}
return 0;
}
remove() 的实现原理是，在遍历容器中的元素时，一旦遇到目标元素，就做上标记，然后继续遍历，直到找到一个非目标元素，即用此元素将最先做标记的位置覆盖掉，同时将此非目标元素所在的位置也做上标记，等待找到新的非目标元素将其覆盖。因此，如果将上面程序中 demo 容器的元素全部输出，得到的结果为 1 4 5 4 3 5。
size is :6
capacity is :6
1 4 5
remove()用于删除容器中指定元素时，常和 erase() 成员函数搭配使用。
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
vector<int>demo{ 1,3,3,4,3,5 };
//交换要删除元素和最后一个元素的位置
auto iter = std::remove(demo.begin(), demo.end(), 3);
demo.erase(iter, demo.end());
cout << "size is :" << demo.size() << endl;
cout << "capacity is :" << demo.capacity() << endl;
//输出剩余的元素
for (int i = 0; i < demo.size();i++) {
cout << demo[i] << " ";
}
return 0;
}
size is :3
capacity is :6
1 4 5
如果想删除容器中所有的元素，则可以使用 clear() 成员函数
deque容器
支持push_back() push_front() pop_back() pop_front()
| 函数成员 |
函数功能 |
| begin() |
返回指向容器中第一个元素的迭代器。 |
| end() |
返回指向容器最后一个元素所在位置后一个位置的迭代器，通常和 begin() 结合使用。 |
| rbegin() |
返回指向最后一个元素的迭代器。 |
| rend() |
返回指向第一个元素所在位置前一个位置的迭代器。 |
| cbegin() |
和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| cend() |
和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crbegin() |
和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crend() |
和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| size() |
返回实际元素个数。 |
| max_size() |
返回容器所能容纳元素个数的最大值。这通常是一个很大的值，一般是 232-1，我们很少会用到这个函数。 |
| resize() |
改变实际元素的个数。 |
| empty() |
判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。 |
| shrink _to_fit() |
将内存减少到等于当前元素实际所使用的大小。 |
| at() |
使用经过边界检查的索引访问元素。 |
| front() |
返回第一个元素的引用。 |
| back() |
返回最后一个元素的引用。 |
| assign() |
用新元素替换原有内容。 |
| push_back() |
在序列的尾部添加一个元素。 |
| push_front() |
在序列的头部添加一个元素。 |
| pop_back() |
移除容器尾部的元素。 |
| pop_front() |
移除容器头部的元素。 |
| insert() |
在指定的位置插入一个或多个元素。 |
| erase() |
移除一个元素或一段元素。 |
| clear() |
移出所有的元素，容器大小变为 0。 |
| swap() |
交换两个容器的所有元素。 |
| emplace() |
在指定的位置直接生成一个元素。 |
| emplace_front() |
在容器头部生成一个元素。和 push_front() 的区别是，该函数直接在容器头部构造元素，省去了复制移动元素的过程。 |
| emplace_back() |
在容器尾部生成一个元素。和 push_back() 的区别是，该函数直接在容器尾部构造元素，省去了复制移动元素的过程。 |
#include <iostream>
#include <deque>
using namespace std;
int main()
{
//初始化一个空deque容量
deque<int>d;
//向d容器中的尾部依次添加 1，2,3
d.push_back(1); //{1}
d.push_back(2); //{1,2}
d.push_back(3); //{1,2,3}
//向d容器的头部添加 0
d.push_front(0); //{0,1,2,3}
//调用 size() 成员函数输出该容器存储的字符个数。
printf("元素个数为：%d\n", d.size());
//使用迭代器遍历容器
for (auto i = d.begin(); i < d.end(); i++) {
cout << *i << " ";
}
cout << endl;
return 0;
}
deque反向迭代器
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int>d{1,2,3,4,5};
for (auto i = d.rbegin(); i < d.rend(); i++) {
cout << *i << " ";
}
return 0;
}
5 4 3 2 1
对于空的 deque 容器来说，可以通过 push_back()、push_front() 或者 resize() 成员函数实现向（空）deque 容器中添加元素。
除此之外，当向 deque 容器添加元素时，deque 容器会申请更多的内存空间，同时其包含的所有元素可能会被复制或移动到新的内存地址（原来占用的内存会释放），这会导致之前创建的迭代器失效。
#include <iostream>
#include <deque>
using namespace std;
int main()
{
deque<int>d;
d.push_back(1);
auto first = d.begin();
cout << *first << endl;
//添加元素，会导致 first 失效
d.push_back(1);
cout << *first << endl;
return 0;
}
程序崩溃!
list容器
可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）
| 成员函数 |
功能 |
| begin() |
返回指向容器中第一个元素的双向迭代器。 |
| end() |
返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。 |
| rbegin() |
返回指向最后一个元素的反向双向迭代器。 |
| rend() |
返回指向第一个元素所在位置前一个位置的反向双向迭代器。 |
| cbegin() |
和 begin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| cend() |
和 end() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crbegin() |
和 rbegin() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| crend() |
和 rend() 功能相同，只不过在其基础上，增加了 const 属性，不能用于修改元素。 |
| empty() |
判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。 |
| size() |
返回当前容器实际包含的元素个数。 |
| max_size() |
返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 232-1，所以我们很少会用到这个函数。 |
| front() |
返回第一个元素的引用。 |
| back() |
返回最后一个元素的引用。 |
| assign() |
用新元素替换容器中原有内容。 |
| emplace_front() |
在容器头部生成一个元素。该函数和 push_front() 的功能相同，但效率更高。 |
| push_front() |
在容器头部插入一个元素。 |
| pop_front() |
删除容器头部的一个元素。 |
| emplace_back() |
在容器尾部直接生成一个元素。该函数和 push_back() 的功能相同，但效率更高。 |
| push_back() |
在容器尾部插入一个元素。 |
| pop_back() |
删除容器尾部的一个元素。 |
| emplace() |
在容器中的指定位置插入元素。该函数和 insert() 功能相同，但效率更高。 |
| insert() |
在容器中的指定位置插入元素。 |
| erase() |
删除容器中一个或某区域内的元素。 |
| swap() |
交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。 |
| resize() |
调整容器的大小。 |
| clear() |
删除容器存储的所有元素。 |
| splice() |
将一个 list 容器中的元素插入到另一个容器的指定位置。 |
| remove(val) |
删除容器中所有等于 val 的元素。 |
| remove_if() |
删除容器中满足条件的元素。 |
| unique() |
删除容器中相邻的重复元素，只保留一个。 |
| merge() |
合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。 |
| sort() |
通过更改容器中元素的位置，将它们进行排序。 |
| reverse() |
反转容器中元素的顺序。 |
list 容器迭代器函数
| 迭代器函数 |
功能 |
| begin() |
返回指向容器中第一个元素的双向迭代器（正向迭代器）。 |
| end() |
返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。（正向迭代器）。 |
| rbegin() |
返回指向最后一个元素的反向双向迭代器。 |
| rend() |
返回指向第一个元素所在位置前一个位置的反向双向迭代器。 |
| cbegin() |
和 begin() 功能相同，只不过在其基础上，正向迭代器增加了 const 属性，即不能用于修改元素。 |
| cend() |
和 end() 功能相同，只不过在其基础上，正向迭代器增加了 const 属性，即不能用于修改元素。 |
| crbegin() |
和 rbegin() 功能相同，只不过在其基础上，反向迭代器增加了 const 属性，即不能用于修改元素。 |
| crend() |
和 rend() 功能相同，只不过在其基础上，反向迭代器增加了 const 属性，即不能用于修改元素。 |
这意味着，假设 p1 和 p2 都是双向迭代器，则它们支持使用 ++p1、 p1++、 p1--、 p1++、 *p1、 p1==p2 以及 p1!=p2 运算符，但不支持以下操作（其中 i 为整数）：
- p1[i]：不能通过下标访问 list 容器中指定位置处的元素。
- p1-=i、 p1+=i、 p1+i 、p1-i：双向迭代器 p1 不支持使用 -=、+=、+、- 运算符。
- p1<p2、 p1>p2、 p1<=p2、 p1>=p2：双向迭代器 p1、p2 不支持使用 <、 >、 <=、 >= 比较运算符。
#include <iostream>
#include <list>
using namespace std;
int main()
{
//创建 list 容器
std::list<char> values{'h','t','t','p',':','/','/','c','.','b','i','a','n','c','h','e','n','g','.','n','e','t'};
//使用begin()/end()迭代器函数对输出list容器中的元素
for (std::list<char>::iterator it = values.begin(); it != values.end(); ++it) {
std::cout << *it;
}
cout << endl;
//使用 rbegin()/rend()迭代器函数输出 lsit 容器中的元素
for (std::list<char>::reverse_iterator it = values.rbegin(); it != values.rend();++it) {
std::cout << *it;
}
return 0;
}
- push_front()：向 list 容器首个元素前添加新元素；
- push_back()：向 list 容器最后一个元素后添加新元素；
- emplace_front()：在容器首个元素前直接生成新的元素；
- emplace_back()：在容器最后一个元素后直接生成新的元素；
- emplace()：在容器的指定位置直接生成新的元素；
- insert()：在指定位置插入新元素；
- splice()：将其他 list 容器存储的多个元素添加到当前 list 容器的指定位置处。
