STL容器：vector

1. 概念 
vector是一种序列式容器，所谓序列式容器，即其中的元素可以排序，但是并未排序。可以把vector可作为加强版的array，它和array一样，存储空间是一段连续的内存，因此支持随机访问，但是，和array相比，vector支持动态增加数据。 
vector支持动态增加数据，同时又需要保持空间的连续性从而支持随机访问，因此，在对vector动态增加元素时，如果旧有空间装满，需要申请更大的内存，并且需要把旧有数据搬到新内存去，因此，数据的搬移效率使我们在开发过程中需要考虑的重要因素。

2. API 
vector提供了很多接口，以下列出vector的成员函数和操作： 

(constructor) Construct vector (public member function) 
(destructor) Vector destructor (public member function) 
operator= Copy vector content (public member function ) 

Iterators: 
begin Return iterator to beginning (public member type) 
end Return iterator to end (public member function) 
rbegin Return reverse iterator to reverse beginning (public member function) 
rend Return reverse iterator to reverse end (public member function) 

Capacity: 
size Return size (public member function) 
max_size Return maximum size (public member function) 
resize Change size (public member function) 
capacity Return size of allocated storage capacity (public member function) 
empty Test whether vector is empty (public member function) 
reserve Request a change in capacity (public member function) 

Element access: 
operator[] Access element (public member function) 
at Access element (public member function) 
front Access first element (public member function) 
back Access last element (public member function) 

Modifiers: 
assign Assign vector content (public member function) 
push_back Add element at the end (public member function) 
pop_back Delete last element (public member function) 
insert Insert elements (public member function) 
erase Erase elements (public member function) 
swap Swap content (public member function) 
clear Clear content (public member function) 

Allocator: 
get_allocator Get allocator (public member function )

3. Vecotr内存分配 
vector内存分配原则是保证一块连续的空间。 vector 并不是随每一个元素的插入而增长自己，而是当vector 需要增长自身时，它实际分配的空间比当前所需的空间要多一些，这主要是基于效率的考虑。 vector内存分配策略的实现是常常是双倍分配（不是所有），比如说当size为4，capacity大小为4，如果再push一个元素，则size为5，capacity为8。 

vector在进行增数据操作时有可能会重新分配内存以保证空间的连续性。增数据操作：push_back,insert 
vector在进行删数据操作时，内存不会重新分配。删数据操作：erase，pop_back 

有两个概念需要明确：size和capacity 
vector::size(): Returns the number of elements in the vector container. 
vector::capacity(): Returns the size of the allocated storage space for the elements of the container 
size是元素个数，capacity则是指为vector分配的内存大小，显然，capacity一定要大于等于size。 

4. reserve和resize的区别 

reserve会预留内存，但不会创建元素；resize则会创建元素，在空间不足的时候，会申请内存。具体的区别，上代码： 

//查看vector：size、capacity
void print(vector &vector)
{
    cout << endl;
    cout << "my vector size:" << vector.size() << endl;
    cout << "my vector capacity:" << vector.capacity() << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    vector myvector1;
    myvector1.reserve(100);

    print(myvector1);

    vector myvector2;
    myvector2.resize(100);

    print(myvector2);
    return 0；
}

输出： 
my vector size:0 
my vector capacity:100

my vector size:100 
my vector capacity:100 


5. Vector使用示例 

代码如下： 

//插入4个元素
void push4element(vector &vector)
{
    vector.push_back (100);
    vector.push_back (100);
    vector.push_back (100);
    vector.push_back (100);
}

//查看vector：size、capacity
void print(vector &vector)
{
    cout << endl;
    cout << "my vector size:" << vector.size() << endl;
    cout << "my vector capacity:" << vector.capacity() << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
    //初始化vector
    vector myvector;

    //插入数据、查看大小
    push4element(myvector);
    print(myvector);

    //插入数据、查看大小
    push4element(myvector);
    print(myvector);

    //插入数据、查看大小
    push4element(myvector);
    print(myvector);

    //插入数据、查看大小
    push4element(myvector);
    print(myvector);

    //清空vector
    while (!myvector.empty())
    {
        myvector.pop_back();
    }
    print(myvector);

    //重置vector大小
    myvector.resize(myvector.size()+2);
    print(myvector);

    system("pause");
    return 0;
}

x32，win7，VS2010运行输出结果： 
my vector size:4 
my vector capacity:4 

my vector size:8 
my vector capacity:9 

my vector size:12 
my vector capacity:13

my vector size:16 
my vector capacity:19

my vector size:0 
my vector capacity:19

my vector size:2 
my vector capacity:19 


lx64 inux 2.6.9 gcc 运行输出结果： 
my vector size:4 
my vector capacity:4

my vector size:8 
my vector capacity:8

my vector size:12 
my vector capacity:16

my vector size:16 
my vector capacity:16

my vector size:0 
my vector capacity:16

my vector size:2 
my vector capacity:16 

从capacity的增长情况来看，不同库内存分配策略实现不一样，但总体上都是增量分配。

6. Vecotr使用常见问题 

1）迭代器失效 
iterator失效主要有两种情况： 
a.iterator变量已经变成了“悬空指针”，对它进行*,++,--都会引起程序内存操作异常； 
b.iterator所指向的变量已经不是你所以为的那个变量了。 

vector迭代器的几种失效的情况： 
a.当插入（push_back）一个元素后，end操作返回的迭代器肯定失效。 
b.当插入(push_back)一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操作返回的迭代器都会失效。 
c.当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。 

比较常见的一种场景是遍历一个vector，删除符合条件的数据，正确的写法如下：

vector myvector;
for(vector::iterator iter=myvector.begin();iter!=myvector.end();)
{
    if(10 == (*iter))
        iter=myvector.erase(iter);
    else
        ++iter;
}

在erase之后，删除的迭代器之后的数据前移，因此，在删除之后，不需要对迭代器++

2）元素访问 
vector支持随机内存访问,我们可以使用at和[]来访问元素，这两者有什么区别呢？ 
在不越界的情况下，两者没有区别；在越界的情况下，at会抛出一个std::out_of_range异常。而C++98标准说[]可以、但不一定要进行下标越界检查。因此，标准库实现方可以自由选择是否为operator[]加上下标越界检查功能。上代码 
at： 

vector myvector;
myvector.reserve(10);
try
{
    cout << myvector.at(100);
}
catch(...)
{
    cout << "got you" << endl;
}

VS2010输出： 
got you 

[]： 

vector myvector;
myvector.reserve(10);

try
{
    cout << myvector[100];
}
catch(...)
{
    cout << "got you" << endl;
}

VS2010： 
程序崩溃

 

3）拷贝构造函数 
初学者使用vector使用常常会遇到的一个麻烦就是忘记定义拷贝构造函数。向上代码，看什么时候我们需要拷贝构造函数 

class A
{
public:
    A(){cout << "construct" << endl;}
    ~A(){cout << "deconstruct" << endl;}
    A(const A&){cout << "copy construct" << endl;}
};

void push_vec(vector& myvector)
{
    A a;
    myvector.push_back(a);
    cout << "my vector capacity:" << myvector.capacity() << endl;
}

void fun()
{
    vector myvector;

    cout << "---begin----"<
    push_vec(myvector);
    cout << "---end----"<

    cout << "---begin----"<
    push_vec(myvector);
    cout << "---end----"<

    cout << "---begin----"<
    push_vec(myvector);
    cout << "---end----"<

    cout << "---begin----"<
    push_vec(myvector);
    cout << "---end----"<

}

int _tmain(int argc, _TCHAR* argv[])
{
    fun();

    system("pause");
    return 0;
}

输出： 

---begin---- 
construct 
copy construct 
my vector capacity:1 
deconstruct 
---end---- 
---begin---- 
construct 
copy construct 
deconstruct 
copy construct 
my vector capacity:2 
deconstruct 
---end---- 
---begin---- 
construct 
copy construct 
copy construct 
deconstruct 
deconstruct 
copy construct 
my vector capacity:3 
deconstruct 
---end---- 
---begin---- 
construct 
copy construct 
copy construct 
copy construct 
deconstruct 
deconstruct 
deconstruct 
copy construct 
my vector capacity:4 
deconstruct 
---end---- 
deconstruct 
deconstruct 
deconstruct 
deconstruct

分析： 
第一个push_vec(myvector)，输出： 
construct // A a 
copy construct // myvector.push_back(a);调用拷贝构造函数 
my vector capacity:1 
deconstruct // a的生命周期到，析构

第2个push_vec(myvector)，输出： 
construct // A a 
copy construct // myvector.push_back(a); 此时capacity不够大，需要重新分配内存，先将第一次push的a调用拷贝构造函数拷贝到新的内存， 
deconstruct // 析构掉第一次push的a（原有内存） 
copy construct //将第2个a 调用拷贝构造函数push到vector新申请的内存中 
my vector capacity:2 
deconstruct // a的生命周期到，析构

我们可以看到，在vector push_back遇到capacity不够的过程中，会调用拷贝构造函数搬移数据。其实，在erase的过程中，也会有调用拷贝构造函数的需要，因此，在我们的对象中有使用指针申请内存的情况下，需要定义好拷贝构造函数。

4）释放内存 

vector在调用erase，pop_back删除元素的时候，并不会释放内存，因此，在vector生命期内，需要释放vector所占用内存的时候，可以使用如下代码： 

template < class T >
void ClearVector( vector< T >& vt )
{
vector< T > vtTemp;
veTemp.swap( vt );
}

如果需要部分释放，可以先将vector的数据拷贝到另一个vector，然后调用swap。 

7. 结语 
vector具有很多优秀的特点：随机访问、动态扩张、额外消耗少，非常适合多查询的应用场景。但是，由于其需要保持内存连续，在删除某个元素之后，后续元素需要拷贝前移，这会带来一些消耗，因此不适合随机删除的场景。