容器简介 and Vector
[TOC]
6.1 容器的共通能力和共通操作
1. 共通能力
1. 所有容器提供都是“value语意”而非“reference语意”。容器进行元素的安插操作时，内部实施的是copy操作，置于容器内。因此STL容器的每一个元素都必须能够被拷贝。 2. 所有元素形成一个次序。 3. 各项操作并非绝对安全。
2.共通操作
初始化，每个容器类别都提供一个default构造函数，一个copy构造函数和一个析构函数。
ContType c //产生一个未含任何元素的空容器 ContType c1(c2) //产生一个同型容器 ContType c(beg, end) //复制[beg,end]区间内的元素，作为容器初值 c.~ContType() //删除所有元素，释放内存 c.size() //返回容器中的元素数量 c.empty() //判断容器是否为空 c.max_size() //返回元素的最大可能数量 c1 == c2 c1 != c2 c1 < c2 c1 > c2 c1 <= c2 c1 >= c2 c1.swap(c2) //交换c1和c2的数据 swap(c1, c2) //同上，是个全局函数 c.begin() c.end() c.rbegin() c.rend() c.insert(pos, elem) c.erase(beg, end) c.clear() c.get_allocator() //返回容器的内存模型与大小相关的操作函数。
size()、empty()、max_size()。 比较，比较按照以下三条规则： ``` - 比较操作两端必须属于同一型别。
- 如果两个容器的所有元素依序相等，那么两个容器相等。采用==操作。
- 采用字典式顺序比较原则来判断某个容器是否小于另一个容器。 ```
赋值和swap
当你对着容器复制元素时，源容器的所有元素被拷贝到目标容器内，后者原来的所有元素全被移除。所以，容器的赋值操作代价比较高昂。 如果两个容器型别相同，而且拷贝后源容器不再被使用，那么我们可以使用一个简单优化的方法：swap。事实上它只交换某些内部指针。
6.2 Vector
使用vector之前，必须包含#include <vector>。其中，vector声明在std。
namespace std {
template <class T,
class Allocator = allocator<T>>
class vector;
} 1.vector的能力
大小和容量。vector优异性能的秘诀之一，就是配置比其所容纳的元素所需要更多的内存。 vector之中用于操作大小的函数有size、empty、max_size。另一个与大小有关的函数是capacity，它返回vector实际能够容纳的元素数量。如果超过这个数量，vector就有必要重新分配内部储存器。
vector的容量之所以很重要，有以下两个原因：
- 一旦内存重新配置，和vector元素相关的所有ref，pointer，iterator都会失效。
- 内存重新配置很耗时间。
你可以使用reserve()保留适当容量，避免一再重新配置内存。另一种避免重新配置内存的方法是，初始化期间就向构造函数传递附加参数，构造出足够的空间。为了获取这种能力，必须提供一个default构造函数。如果型别复杂，就算提供了default构造函数，初始化操作也很耗时，如果你只不过为了保留足够的内存，那倒不如使用reserve。
安插操作可能使ref、pointer、iterator失效。因为可能导致重新配置空间。
下面有个间接所见vector容量的小窍门。
std::vector<T>(v).swap(v)
swap后，ref等都会失效。
2. Vector的操作函数
构造、拷贝和析构
vector<Elem> c vector<Elem> c1(c2) vector<Elem> c(n) vector<Elem> c(n, elem) //产生一个大小为n的vector，每个元素都是elem vector<Elem> c(beg, end) c.~vector<Elem>()
非变动性操作
c.size() c.empty() c.max_size() capacity() reserve() c1 == c2 c1 != c2 c1 < c2 c1 > c2 c1 <= c2 c1 >= c2
赋值
c1 = c2 c.assign(n, elem) c.assign(beg, end) c1.swap(c2) swap(c1, c2)
元素存取，不作边界检查。
c.at(idx) c[idx] c.front() c.back()
迭代器相关函数
c.begin() c.end() c.rbegin() c.rend()
安插和移除元素
c.insert(pos, elem) c.insert(pos, n, elem) c.insert(pos, beg, end) c.push_back() c.erase(pos) c.erase(beg, end) c.resize(num) c.resize(num ,elem) c.clear()
vector并未提供任何函数可以直接移除“与某值相等”的所有元素，以下可以移除所有val：
col1.erase(remove(col1.begin(), col1.end(), val),
col1.end()); 3. 异常处理
如果vector调用的函数抛出异常，C++标准程序库做出如下保证：
- 如果push_back()安插元素时发生异常，该函数不起作用。
- 如果元素的拷贝(copy, assign)操作不抛出异常，insert要么成功，要么什么都不发生。
- pop_back()决不会抛出任何异常。
- 如果元素拷贝操作不抛出异常，erase和clear就不抛出异常。
- swap不抛出异常。
- 如果元素拷贝操作绝对不会抛出异常，那么所有操作不是成功，就是不起作用。这类元素可被称为POS(plain old data)。POD泛指那些无C++特性的异常，例如C structure。
所有这些保证都基于一个条件：析构函数不得抛出异常。
4. Class vector<bool>
目标是获取一个优化的vector，其耗用空间远远小于一般vector生成的bool vector。
如果你需要静态大小的bitfield，应当使用bitset。
vector<bool>的特殊操作
c.flip() m[idx].flip() m[idx] = val m[idx1] = m[idx2]
参考：
- C++标准程序库：自修教程与参考手册