容器简介 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()       //返回容器的内存模型

1. 比较操作两端必须属于同一型别。
2. 如果两个容器的所有元素依序相等，那么两个容器相等。采用==操作。
3. 采用字典式顺序比较原则来判断某个容器是否小于另一个容器。 ```

赋值和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的容量之所以很重要，有以下两个原因：

1. 一旦内存重新配置，和vector元素相关的所有ref，pointer，iterator都会失效。
2. 内存重新配置很耗时间。

你可以使用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++标准程序库做出如下保证：

1. 如果push_back()安插元素时发生异常，该函数不起作用。
2. 如果元素的拷贝(copy, assign)操作不抛出异常，insert要么成功，要么什么都不发生。
3. pop_back()决不会抛出任何异常。
4. 如果元素拷贝操作不抛出异常，erase和clear就不抛出异常。
5. swap不抛出异常。
6. 如果元素拷贝操作绝对不会抛出异常，那么所有操作不是成功，就是不起作用。这类元素可被称为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]

参考：

1. C++标准程序库：自修教程与参考手册