点击查看Evernote原文。
#@author: gr
#@date: 2014-08-11
#@email: forgerui@gmail.com
vector的相关问题。《stl学习》将按内容进行整理，不再把所有内容放到一个文件中。
###stl学习
|--迭代器
|--类属算法
|--容器
|--vector
|--deque
|--list
|--set
|--map
|--函数对象
|--适配器
|--分配器
一、Contents
1. 强大的迭代器
因为vector的迭代器是随机迭代器,即最强大的迭代器,所以一般的类属算法都可以支持. 如sort算法, list(链表)便不支持sort类属算法, 而对list增加了sort成员函数.
2. vector构造函数
int n = 10;
//初始n个"T value"
vector<T> v1(n, value);
//第二个参数是默认参数,默认为T(),向量的每个成员都是T()的拷贝构造函数得来,
//可以理解为先使用T a初始化一个对象a,之后每个向量的元素都是调用拷贝构造函数T(T& a)得来的对象
vector<T> v2(n);
//从其它容器中拷贝
char a[] = "hello";
vector<char> v3(a, a+5);
vector<int> v4(list1.begin(), list1.end());
3. 插入
vector提供了随机访问的功能,说明其访问时间是常数的，但其插入和删除时间则是线性的。所以，在末尾插入用vector, 在末尾和头部插入用双向队列(deque)，大量进行插入删除操作时使用链表(list)。
//push_back压入最后
vector<int> v;
v.push_back(2);
//insert插入任何位置
v.insert(position, value);
4. capacity与size
capacity: 向量已经申请到的内存空间大小
size： 向量已经分配元素的大小
一般，capacity() >= size()。
5. vector的内存分配问题
当初始化一个空vector时，默认内存大小为0;可以通过capacity查看。
第一次申请空间大小个数为1024,如果使用空间超过capacity，再次插入时就会扩大2倍。
具体做法是重新申请原来内存2倍的空间，并将原来的数据拷贝到新申请的内存中，释放掉原来的内存。这样做的原因是vector需要按顺序连续存储在一段空间中。虽然，重新分配内存和拷贝数据需要很大的开销，但这种情况很少出现一次，把它平均分摊到每个插入操作，复杂度仍可以维持在常数。
//初始化一个空向量
vector<int> a;
assert(a.capacity() == 0);
//增加内存,申请大小为1024
a.push_back(1);
assert(a.capacity() == 1024);
6.使用reserve提高效率
上面提到，vector动态申请内存的开销问题，如果可以事先确定需要的大小，可以使用reserve一次性申请这段空间。
//不提前申请空间，需要申请多次,1024,2048,4096,8192,16384，造成了多次开销
vector<int> v1;
for(int i=0; i<1000; i++){
v1.push_back(i);
}
//一次性申请10000空间，可以有效减少开销
vector<int> v2;
v2.reserve(10000);
for(int i=0; i<1000; i++){
v1.push_back(i);
}
7. 删除
在删除末尾以外地方的元素需要将后面的元素进行移动，时间复杂度是线性的。删除点之后的迭代器失效，所以erase(j++)是值得考量的;
//pop_back
vector<int> a;
a.pop_back();
//erase,删除position位置上的元素
a.erase(position);
//erase,删除[first, last)上的元素
a.erase(iterator first, iterator last);
//删除向量v1的第一个元素
a.erase(v1.begin());
8. 访问器
访问器是vector的成员函数，只获取向量的信息，不改变向量的状态。
size_type size(), capacity(),
iterator begin(), end()
reference front(), back(), [], at()
bool empty()
9. 向量的swap函数
部分特殊化定义(partial specialization)：将模板参数类型更加具体化
当存在两个模板函数时，特殊化程度高的函数会被调用。这样，各个容器的swap函数会比最普通的swap调用的优先级更高。实现了针对各个容器的快速算法，这些容器的swap函数都是常数的时间复杂度。
//最普适的swap
template <typename T>
void swap(T& a, T& b){
T temp = a;
a = b;
b = temp;
}
//特殊化的swap,将T变为vector<U>，当遇到vector时，会先调用这个swap
template <typename U>
void swap(vector<U>& a, vector<U>& b){
a.swap(b);
}
//调用swap,优先使用向量的swap，即有vector1.swap(vector2);
swap(vector1, vector2);
二、Miscellany
@author gr
@mail forgerui@gmail.com