深入理解C++中的vector类的用法及特性
//<vector> template<classT,classAlloc=allocator<T>>classvector;
向量（Vector）是一个封装了动态大小数组的顺序容器（Sequencecontainer）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，向量是一个能够存放任意类型的动态数组。
vector类为内置数组提供了一种替代表示，与string类一样vector类是随标准C++引入的标准库的一部分，为了使用vector我们必须包含相关的头文件 ：
#include<vector>
容性特性：
1.顺序序列
顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。
2.动态数组
支持对序列中的任意元素进行快速直接访问，甚至可以通过指针算述进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作。
3.能够感知内存分配器的（Allocator-aware）
容器使用一个内存分配器对象来动态地处理它的存储需求。
使用：
使用vector有两种不同的形式，即所谓的数组习惯和STL习惯。
一、数组习惯用法
1.定义一个已知长度的vector：
vector<int>ivec(10);//类似数组定义intia[10];
可以通过ivec[索引号]来访问元素
使用if(ivec.empty())判断是否是空，ivec.size()判断元素个数。
2.vector的元素被初始化为与其类型相关的缺省值：算术和指针类型的缺省值是0，对于class类型，缺省值可通过调用这类的缺省构造函数获得，我们还可以为每个元素提供一个显式的初始值来完成初始化，例如
vector<int>ivec(10,-1);
定义了ivec它包含十个int型的元素每个元素都被初始化为-1
对于内置数组我们可以显式地把数组的元素初始化为一组常量值，例如：
intia[6]={-2,-1,0,1,2,1024};
我们不能用同样的方法显式地初始化vector，但是可以将vector初始化为一个已有数组的全部或一部分，只需指定希望被用来初始化vector的数组的开始地址以及数组最末元的下一位置来实现，例如：
//把ia的6个元素拷贝到ivec中 vector<int>ivec(ia,ia+6);
被传递给ivec的两个指针标记了用来初始化对象的值的范围，第二个指针总是指向要拷贝的末元素的下一位置，标记出来的元素范围也可以是数组的一个子集，例如:
//拷贝3个元素ia[2],ia[3],ia[4] vector<int>ivec(&ia[2],&ia[5]);
3.与内置数组不同vector可以被另一个vector初始化或被赋给另一个vector例如
vector<string>svec;
voidinit_and_assign()
{
//用另一个vector初始化一个vector
vector<string>user_names(svec);
//...
//把一个vector拷贝给另一个vector
svec=user_names;
}
二、STL习惯用法
在STL9中对vector的习惯用法完全不同。我们不是定义一个已知大小的vector，而是定义一个空vector
vector<string>text;
1.我们向vector中插入元素，而不再是索引元素，以及向元素赋值，例如push_back()操作，就是在vector的后面插入一个元素下面的while循环从标准输入读入一个字符串序列并每次将一个字符串插入到vector中
stringword;
while(cin>>word){
text.push_back(word);
//...
}
虽然我们仍可以用下标操作符来迭代访问元素
cout<<"wordsreadare:\n"; for(intix=0;ix<text.size();++ix) cout<<text[ix]<<''; cout<<endl;
但是更典型的做法是使用vector操作集中的begin()和end()所返回的迭代器iterator
对：
cout<<"wordsreadare:\n"; for(vector<string>::iteratorit=text.begin(); it!=text.end();++it) cout<<*it<<''; cout<<endl
iterator是标准库中的类，它具有指针的功能
*it;
对迭代器解引用，并访问其指向的实际对象
++it;
向前移动迭代器it使其指向下一个元素
2.注意不要混用这两种习惯用法，例如，下面的定义
vector<int>ivec;
定义了一个空vector再写这样的语句
ivec[0]=1024;
就是错误的，因为ivec还没有第一个元素，我们只能索引vector中已经存在的元素size()操作返回vector包含的元素的个数。
3.类似地当我们用一个给定的大小定义一个vector时，例如 ：
vector<int>ia(10);
任何一个插入操作都将增加vector的大小，而不是覆盖掉某个现有的元素，这看起来好像是很显然的，但是下面的错误在初学者中并不少见：
constintsize=7;
intia[size]={0,1,1,2,3,5,8};
vector<int>ivec(size);
for(intix=0;ix<size;++ix)
ivec.push_back(ia[ix]);
程序结束时ivec包含14个元素,ia的元素从第八个元素开始插入。
深入理解
在向量中，所有元素都是连续存储的。也就是说，不仅可以通过迭代器（Iterators）访问各个元素，也可以通过指向元素的指针加上偏移来访问。还意味着，当向任意函数传递向量的一个元素的指针时，这个指针可以直接被认为指向了一个数组中的某个元素。
向量内部的存储调整是自动处理的，按需扩展或压缩。通常，相比静态数组（Staticarrays），向量将会占用更多的存储空间，因为额外的内存将被未来增长的部分所使用。就因为这点，当插入元素时，向量不需要太频繁地重分配（Reallocate）内存。当前最大容量可以通过函数capacity()查询。额外的内存可以通过调用shrink_to_fit()函数返还给操作系统。
当增加向量对象中的序列的长度时，如果超出当前存储容量上限，就会发生内存重分配（Reallocation），即内部将会重新分配一个数组，然后按顺序逐个拷贝元素。其它的插入及删除操作将会修改序列中部分元素的内存地址。在上述所有情况下，指向序列中被修改部分的迭代器或引用将会失效。当未发生内存重分配，仅指向插入或删除点之前元素的迭代器或引用才会保持有效性。
标准库可以执行不同的增长策略来平衡内存的使用量与重分配所耗的性能。但不管哪种情况下，重分配内存的大小必须以指数方式增长，只有这样，才能将在向量末尾逐个插入元素所需的时间复杂度整体分摊（Amortized）为一个恒定值。
内存重分配就性能而言是一个高代价操作。如果在使用向量前知道元素的数量，可以通过reserve()消除内存重分配。
向量支持在序列末尾恒定耗时的插入及删除元素。而在向量的中间插入或删除元素则需要线性的时间。在只涉及向序列起始或未尾插入及删除元素操作时，std::deque容器的性能将会高出很多。当涉及向序列中的任意位置进行插入及删除操作时，std::list容器的性能将会高出很多。
常用操作的算法复杂度（性能相关）如下：
- 随机访问，时间复杂度为O(1)
- 在未尾插入或删除元素，整体分摊的时间复杂度为O(1)
- 其它位置插入或删除元素，与当前位置至向量末尾的距离有关，时间复杂度O(n)