各位客官好久不见！
C++ STL从⼴义来讲包括了三类：算法，容器和迭代器。
算法包括排序，复制等常⽤算法，以及不同容器特定的算法。
容器就是数据的存放形式，包括序列式容器和关联式容器，序列式容器就是list，vector等，关联式容器就是 set，map等。
迭代器就是在不暴露容器内部结构的情况下对容器的遍历。
所谓序列容器，即以线性排列（类似普通数组的存储方式）来存储某一指定类型（例如 int、double 等）的数据，需要特殊说明的是，该类容器并不会自动对存储的元素按照值的大小进行排序。
需要注意的是，序列容器只是一类容器的统称，并不指具体的某个容器，序列容器大致包含以下几类容器：
array<T,N>（数组容器）：表示可以存储 N 个 T 类型的元素，是 C++ 本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；
vector<T>（向量容器）：用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；
deque<T>（双端队列容器）：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；
list<T>（链表容器）：是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list<T> 必须从第一个元素或最后一个元素开始访问，需要沿着链表移动，直到到达想要的元素。
forward_list<T>（正向链表容器）：和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。
注意，其实除此之外，stack<T> 和 queue<T> 本质上也属于序列容器，只不过它们都是在 deque 容器的基础上改头换面而成，通常更习惯称它们为容器适配器，有关它们的介绍，会放到后续章节中。
图 1 说明了可供使用的序列容器以及它们之间的区别。
图 1 标准的序列容器
图 1 中每种类型容器的操作都可以高效执行，但进行除此之外的其他操作，效率会稍差一些。在本章的剩余部分，会详细介绍每一类序列容器的具体用法。
容器中常见的函数成员
序列容器包含一些相同的成员函数，它们的功能也相同，本教程会在某个容器的上下文中详细介绍下面的每个函数，但对于每种类型的容器不会重复介绍它们的细节。
表 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 容器彼此非常相似，forward_list 中包含了 list 的大部分成员函数，而未包含那些需要反向遍历的函数。表 3 展示了 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 中。 | - | 是 |
注意，大家没有必要死记这些表，它们仅供参考。在深入了解到容器是如何组织元素以后，你会本能地知道哪个容器能使用哪些成员函数。
特别的面试中经历的问题：
（1）vector的底层原理
vector底层是⼀个动态数组，包含三个迭代器，start和finish之间是已经被使⽤的空间范围，end_of_storage是整块连续空间包括备⽤空间的尾部。 当空间不够装下数据（vec.push_back(val)）时，会⾃动申请另⼀⽚更⼤的空间（1.5倍或者2倍），然后把原来的 数据拷⻉到新的内存空间，接着释放原来的那⽚空间【vector内存增⻓机制】。
当释放或者删除（vec.clear()）⾥⾯的数据时，其存储空间不释放，仅仅是清空了⾥⾯的数据。因此，对vector的任何操作⼀旦引起了空间的重新配置，指向原vector的所有迭代器会都失效了。
（2）vector中的reserve和resize的区别
reserve是直接扩充到已经确定的⼤⼩，可以减少多次开辟、释放空间的问题（优化push_back），就可以提⾼效 率，其次还可以减少多次要拷⻉数据的问题。reserve只是保证vector中的空间大小capacity）最少达到参数所指 定的大小n。reserve()只有⼀个参数。resize()可以改变有效空间的大小，也有改变默认值的功能。capacity的⼤⼩也会随着改变。resize()可以有多个参 数。
（3）vector中的size和capacity的区别
size表示当前vector中有多少个元素（finish - start），⽽capacity函数则表示它已经分配的内存中可以容纳多少元 素（end_of_storage - start）。（4）vector的元素类型可以是引⽤吗？
vector的底层实现要求连续的对象排列，引⽤并⾮对象，没有实际地址，因此vector的元素类型不能是引⽤。
（5）vector迭代器失效的情况
当插⼊⼀个元素到vector中，由于引起了内存᯿新分配，所以指向原内存的迭代器全部失效。当删除容器中⼀个元素后,该迭代器所指向的元素已经被删除，那么也造成迭代器失效。erase⽅法会返回下⼀个有 效的迭代器，所以当我们要删除某个元素时，需要it=vec.erase(it);。
（6）正确释放vector的内存(clear(), swap(), shrink_to_fit())
vec.clear()：清空内容，但是不释放内存。vector().swap(vec)：清空内容，且释放内存，想得到⼀个全新的vector。vec.shrink_to_fit()：请求容器降低其capacity和size匹配。vec.clear();vec.shrink_to_fit();：清空内容，且释放内存。
（7）vector 扩容为什么要以1.5倍或者2倍扩容?
考虑可能产⽣的堆空间浪费，成倍增⻓倍数不能太⼤，使⽤较为⼴泛的扩容⽅式有两种，以 2倍的⽅式扩容，或者以1.5倍的⽅式扩容。以2倍的⽅式扩容，导致下⼀次申请的内存必然⼤于之前分配内存的总和，导致之前分配的内存不能再被使⽤，所 以最好倍增⻓因⼦设置为(1,2)之间：
vector<int> vec(10,100); 创建10个元素,每个元素值为100vec.resize(r,vector<int>(c,0)); ⼆维数组初始化reverse(vec.begin(),vec.end()) 将元素翻转sort(vec.begin(),vec.end()); 排序，默认升序排列vec.push_back(val); 尾部插⼊数字vec.size(); 向量⼤⼩find(vec.begin(),vec.end(),1); 查找元素iterator = vec.erase(iterator) 删除元素
