| 顺序容器类型 | 特点 | ||
|---|---|---|---|
| vector | 可变大小数组 | 支持快速随机访问。因为元素保存在连续的内存空间里 | 中间位置添加删除元素很慢。在尾部插入删除速度快。因为要移动插入/删除位置之后的所有元素 |
| string | 专用于保存字符(与vector相似) | 支持随机访问 | 中间位置添加删除元素很慢。在尾部插入删除速度快 |
| deque | 双端队列 | 支持快速随机访问 | 在头尾位置插入/删除速度很快 |
| list | 双向链表 | 不支持随机访问。只支持双向顺序访问 | 在链表的任何位置插入和删除都很快 |
| forward_list | 单向链表 | 不支持随机访问。只支持单向顺序访问 | 在链表的任何位置插入和删除都很快 |
| array | 固定大小数组 | 支持快速随机访问 | 不能添加或删除元素 |
vector和数组比较？
vector 和 数组 非常相似，但是两者的差别在于空间运用的灵活性。数组是静态空间，定义好大小之后就不能改变；
但是vector是动态空间，随着元素的加入，它的内部机制可动态的增加或减少元素，内存管理自动完成，我们也可以用reserve()来自行管理内存。
vector类有两个成员函数：capacity 和 reserve
capacity：用来获取当前容器可以存储的元素总数
reserve：用来告诉容器应该预留多少个元素的空间。
vector的两个大小概念：
capacity：在容器必须重新分配存储空间之前，当前可以存储的元素总数。当元素个数超过capacity()的时候，就会触发内存重新分配，此时会重新分配一块更大的空间，然后复制元素到新分配的空间里去，然后再释放旧空间
size：当前容易拥有的元素个数。即已经存储的元素个数。
size是当前已有元素大小，capacity是当前可容纳元素大小。
vector迭代器失效的情况：
vector迭代器在内存重新分配的时候将会失效（因为它指向的元素在内存分配的前后不在相同）。
插入元素后，指向当前插入元素的后面的任何元素的迭代器都失效。当插入元素后，元素个数如果超过capacity()时，内存会重新分配，此时所有的迭代器都将失效。
删除元素时，指向被删除元素之后的任何元素的迭代器将会失效。vector是连续存储的，在删除一个元素的时候，后面的元素都要向前移动，所以迭代器的位置就会被前面的覆盖，这个时候++迭代器的时候，就会跳过删除元素的后一个元素。erase会返回删除之后的元素的iterator。
list 的内部结构是一个双向环状链表。
不能随机访问一个元素，可以双向遍历，可以动态的增加或减少元素，内存管理自动完成。
增加任何元素都不会使迭代器失效。删除元素时，除了指向当前被删除的迭代器外，其它迭代器都不会失效。
deque 则是一种双开口的连续线性空间。即可以再头尾两端分别做元素的插入和删除操作。
deque 没有容量(capacity)概念，因为它是动态地以分段连续空间组合成的，随时可以增加一段新的空间并链接起来。
随机访问每个元素，所需要的时间为常量。
在开头和末尾增加元素所需时间与元素数目无关，在中间增加或删除元素所需时间随元素数目呈线性变化。
可动态增加或减少元素，内存管理自动完成，不提供内存管理的成员函数
适配器，可以将任意类型的序列容器转换为一个堆栈。
适配器，可以将任意类型的序列容器转换为一个队列。
适配器，可以将任意类型的序列容器转换为一个优先级队列。
只能访问第一个元素，不能编译priority_queue，第一个元素始终是优先级最高的元素。
| 构造函数 | 作用 |
|---|---|
| C c | 默认构造函数，构造空容器 |
| C c1(c2) | 构造c2的拷贝c1 |
| C c(b,e) | 构造c，将迭代器b和e指定的范围内的元素拷贝到c（array不支持） |
| C c{a,b,c…} | 列表初始化c |
（1）以vector来举个例子：
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vec1; //默认初始化，vec1为空
for(int i = 1;i <= 10;i++){
vec1.push_back(i);
}
vector<int> vec2(vec1); //使用vec1初始化vec2
vector<int> vec3(vec1.begin(),vec1.end());
vector<int> vec4(10); //10个值为0的元素
vector<int> vec5(10,4); //10个值为4的元素
cout << (vec1 == vec2) ? true : false;
cout << "\n";
cout << (vec1 == vec3) ? true : false;
return 0;
}
控制台输出：
（2）以list来举个例子
#include <iostream>
#include <list>
using namespace std;
int main(){
list<int> list1; //创建一个空的list
list<int> list2(list1); //使用list1初始化list2
list<int> list3(3); //创建含有3个元素的list3
list<int> list4(10,5); //创建10个元素为5的list4
list<int> list5(list1.begin(),list1.end()); //使用list1初始化list5,同list2
cout << ((list1 == list2) ? true : false) << endl;
return 0;
}
控制台输出：1
（3）特殊的array，具有固定大小。在定义array时，不仅要指定元素类型，还需要指定容器大小。
#include <iostream>
#include <array>
using namespace std;
int main(){
array<int,10> a1; //10个默认初始化的int
array<int,10> a2 = {0,1,2,3,4,5,6,7,8,9}; //列表初始化
array<int,10> a3 = {42}; //a3[0]是42，剩余元素为0
//a4 = {0}; //错误：不能将一个花括号列表赋予数组
return 0;
}
| 赋值与swap | 作用 |
|---|---|
| c1 = c2 | 将c1中的元素替换为c2中的元素 |
| c1 = {a,b,c…} | 将c1中的元素替换为列表中的元素，不适用于array |
| a.swap(b) | 交换a和b的元素 |
| swap(a,b) | 与a.swap(b)等价 |
| 大小 | 作用 |
|---|---|
| c.size() | c中元素的数目，不支持forward_list |
| c.max_size() | c可保存在最大元素数目 |
| c.empty() | 判断c中是否含有元素，有元素返回false，否则返回true |
| 添加删除元素（不适用array） | 作用 |
|---|---|
| c.insert(args) | 将args中的元素拷贝进c |
| c.emplace(inits) | 适用inits构造c中的一个元素 |
| c.erase(args) | 删除args指定的元素 |
| c.clear(args) | 删除c中的所有元素，返回void |
（1）vector容器
#include <iostream>
#include <vector>
using namespace std;
int main(){
vector<int> vec1; //默认初始化，vec1为空
vec1.push_back(1); //从末尾插入一个元素 vector中元素：1
vec1.insert(vec1.end(),2,3); //从vec1.end()位置插入2个3 vector中元素：1 3 3
vec1.insert(vec1.begin(),2,4); //从vec1.begin()位置插入2个4 vector中元素：4 4 1 3 3
vec1.pop_back(); //删除末尾元素 vector中元素：4 4 1 3
vec1.erase(vec1.begin(),vec1.begin()+2); //删除vec1[0]-vec1[2]之间的元素，不包括vec1[2]
int size = vec1.size(); //得到vector的大小
bool isEmpty = vec1.empty(); //判断vector是否为空
//使用迭代器遍历
vector<int>::iterator iter = vec1.begin();
for(;iter != vec1.end();iter++){
cout << *iter << " ";
}
return 0;
}
（2）list容器
list中的erase的作用是，使作为参数的迭代器失效，并返回指向该迭代器的下一个参数的迭代器
#include <iostream>
#include <list>
using namespace std;
int main(){
list<int> list1; //创建一个空的list
list<int> list2(3); //创建含有3个元素的list
list1.assign(list2.begin(),list2.end()); //分配值，3个值为0的元素 0 0 0
list1.push_back(10); //末尾添加一个值 0 0 0 10
list1.insert(list1.begin(),3,2); //从指定位置插入3个值为2的元素 2 2 2 0 0 0 10
list1.erase(list1.begin()); //使指定位置的迭代器失效 2 2 0 0 0 10
list1.assign(list2.begin(),list2.end()); //分配值，会覆盖之前的所有值 0 0 0
list1.pop_back(); //删除末尾的值 0 0
list1.clear(); //清空list1的全部值
list1.erase(list1.begin(),list1.end()); //删除元素
list1.front(); //返回第一个元素的引用
list1.back(); //返回最后一个元素的引用
list1.size();
list1.sort();
list1.unique();
return 0;
}
| 反向容器的额外成员（不支持forward_list） | 作用 |
|---|---|
| reverse_iterator | 按逆序寻址元素的迭代器 |
| const_reverse_iterator | 不能修改元素的逆序迭代器 |
| c.rbegin(),c.rend() | 返回指向c的尾元素和首元素之前位置的迭代器 |
| c.crbegin(),c.crend() | 返回const_reverse-iterator |
（1）每个顺序容器都有一个front成员函数，返回首元素的引用。
（2）除了forward_list，其他的所有顺序容器都有一个back成员函数，返回尾元素的引用。
（3）forward_list不支持递减迭代器，即–操作
（4）at(n) 成员函数，返回下标为n的元素的引用。如果下标越界，则抛出out_of_range异常，只适用于string、vector、deque和array
| 获取迭代器 | 作用 |
|---|---|
| c.begin(),c.end() | 返回指向c的首元素和尾元素之后位置的迭代器 |
| c.cbegin(),c.cend() | 返回const_iterator |
| 关系运算符 | 作用 |
|---|---|
| ==,!= | 相等不等运算符 |
| <,<=,>,>= | 关系运算符（无序关联容器不支持） |
关联容器：关联容器中的元素是按照关键字来保存和访问的。也就是通过键去获得对应的值 。两个主要的关联容器类型是map和set。
map中的元素是关键字-值对，set中的元素只包含一个关键字。
有序容器
| 关联容器类型 | 作用 |
|---|---|
| map | 关键字-值对 |
| set | 关键字 |
| multimap | 关键字可重复出现的map |
| multiset | 关键字可重复出现的set |
| 关联容器额外的类型别名 | 作用 |
|---|---|
| key_type | 此容器类型的关键字类型 |
| mapped_type | 每个关键字关联的类型，只适用于map |
| value_type | 对于set，与key_type相同，对于map，为pair<const key_type,mapped_type> |
set<string>::value_type v1; //v1是一个 string 类型
set<string>::key_type v2; //v2是一个 string 类型
map<string,int>::value_type v3; //v3是一个 pair<const string,int> 类型
map<string,int>::key_type v4; //v4是一个 string 类型
map<string,int>::mapped_type v5; //v5是一个 int 类型
insert（或emplace）进行插入操作的时候，如果容器中已经存在这个关键字，就什么也不做，如果不存在，就进行插入操作，并返回一个pair，告诉我们插入操作是否成功。
#include <iostream>
#include <map>
#include <list>
using namespace std;
int main(){
map<string,int> map_count;
//向map中添加元素的四种方法
map_count.insert({"aaa",1});
map_count.insert(pair<string,int>("bbb",2));
map_count.insert(map<string,int>::value_type("ccc",3));
map_count.insert(make_pair("ddd",4));
return 0;
}
#include <iostream>
#include <map>
#include <list>
using namespace std;
int main(){
map<string,int> map_count;
//向map中添加元素的四种方法
map_count.insert({"aaa",1});
map_count.insert(pair<string,int>("bbb",2));
map_count.insert(map<string,int>::value_type("ccc",3));
map_count.insert(make_pair("ddd",4));
//删除元素
map_count.erase("aaa");
//通过键去访问
cout << map_count["bbb"] << endl;;
//查找元素
map_count.find("ccc"); //返回一个迭代器，指向第一个关键字为ccc的元素，若ccc不再容器中，则返回尾后迭代器
map_count.count("ccc"); //返回关键字等于ccc的元素的数量。
map_count.lower_bound("ccc"); //返回一个迭代器，指向第一个关键字不小于k的元素
map_count.upper_bound("ccc"); //返回一个迭代器，指向第一个关键字大于k的元素
//遍历map
map<string,int>::iterator iter = map_count.begin();
while(iter != map_count.end()){
cout << iter->first << " = " << iter->second << endl;
++iter;
}
return 0;
}
关联容器支持高效的关键字查找和访问。
| 关联容器类型 | 介绍 |
|---|---|
| 按关键字有序保存元素 | |
| map | 关联数组：保存关键字--值对 |
| set | 关键字即值，即只保存关键字的容器 |
multimap | 关键字可重复出现的map |
| multiset | 关键字可重复出现的set |
| 无序集合 | |
unordered_map | 用哈希函数组织的map |
| unordered_set | 用哈希函数组织的set |
| unordered_multimap | 用哈希函数组织的map，关键字可重复出现 |
| unordered_multiset | 用哈希函数组织的set，关键字可重复出现 |
关联容器额外的类型别名：
| key_type |
|---|
| 电脑 |
| 手机 |
| 导管 |
pair作为函数返回值：
pair<string , int> process(std::vector<string> & v)
{
if(v.empty())
{
return pair<string, int>(); // 构造隐式返回值
}
else
{
// make_pair<string , int>(v.back() , (int)v.back().size());
// pair<string , int>(v.back() , (int)v.back().size());
return {v.back() , (int)v.back().size()}; //列表初始化
}
}
map的元素是pair。
map不允许两个元素拥有相同的键值。
所有元素会根据元素的键值被自动排序。
对元素新增或删除时，操作之前的所有迭代器，在操作完之后都仍然有效。被删除的元素的迭代器会失效
multimap的特性和用法和map完全相同。唯一区别就是multimap允许键值重复
所有元素都会根据元素的键值被自动排序。set不允许两个元素有相同的键值
对元素新增或删除时，操作之前的所有迭代器，在操作完之后都仍然有效。除了被删除的元素的迭代器
multiset的特性和用法和set完全相同。唯一区别就是multiset允许键值重复
顺序容器：vector、deque、stack、queue、priority_queue
关联容器：map、set、multimap、multiset
顺序容器：此处的顺序不是体现在元素的值的顺序，而是指的是元素加入容器时的位置顺序相对应的。
关联容器：关联容器中的元素是按照关键字来保存和访问的。也就是通过键去获得对应的值
顺序容器和关联容器的差别？
顺序容器：为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖元素的值，而是与元素加入容器时的位置相对应。
关联容器通过键存储和读取元素，顺序容器通过元素在容器中的位置顺序存储和访问元素
string和vector相似的地方？
string 和 vector 都是将元素存储在连续的内存空间中。由于元素是连续存储的，由元素的下标来计算地址是非常快的。
但是，在这两种容器的中间位置添加或者删除元素就会非常耗时。在一次插入或删除操作后，需要移动插入/删除位置之后的所有元素，来保持连续存储。如果添加一个元素，导致需要重新分配存储空间进行存储的时候，需要把所有元素都移动到新的存储空间中。
list 和 forward_list
list 和 forward_list 设计目的是令容器任何位置的添加和删除操作都很快速。
但是，这两个元素不支持随机访问，为了访问一个元素，只能遍历整个容器。
并且
迭代器范围：一个迭代器范围由一对迭代器表示，两个迭代器分别指向同一个容器中的首元素或者尾元素之后的位置。这两个迭代器分别叫做begin和end，它们标记了容器中元素的一个范围[begin,end)。
| 顺序容器类型别名 | 作用 |
|---|---|
| iterator | 此容器类型的迭代器类型 |
| const_iterator | 可以读取元素，但不能修改元素的迭代器类型 |
| size_type | 无符号整数类型，足够保存此容器类型最大可能容器的大小 |
| defference_type | 带符号整数类型，足够保存两个迭代器之间的距离 |
| value_type | 元素类型 |
| reference | 元素的左值类型，与value_type&含义相同 |
| const_reference | 元素的const左值类型，即const value_type& |