[TOC]

1. vector

vector底层是一个动态数组。

1.1. 底层原理

当空间不够装下数据（vec.push_back(val)）时，会自动申请另一片更大的空间（1.5倍或者2倍），然后把原来的数据拷贝到新的内存空间，接着释放原来的那片空间【vector内存增长机制】。

当释放或者删除（vec.clear()）里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。

1.2. 初始化

方法一

vector<int> vi;

方法二

vector<int> vi(10,10);//size 10,each value 10

方法三

vector<int> vi(arr,arr+10);//begin,end

1.3. 插入

方法一 push_back

vector<T> a;
T val;
a.push_back( val);//在末尾插入一个元素

方法二 insert

v2.insert(v2.begin()+4, L"3");   //在指定位置，例如在第五个元素前插入一个元素

v2.insert(v2.end(), L"3");   //在末尾插入一个元素

v2.insert(v2.begin(), L"3");   //在开头插入一个元素

1.4. 查找

方法一迭代器

    #include <algorithm>

    ...
    vector<int> vec;
    ...
    vector<int>::iterator it = find(vec.begin(), vec.end(), value);

    if (it != vec.end()){
        //找到了
    }

方法二数组查找

std::vector <T> a;
for (size_t i = 0; i < a.size(); i++)
{
    if(value ==  a[i];{
    //找到了
    }
}

1.5. 遍历

方法一迭代器

std::vector <T> a;

std::vector <T>::iterator iVector = a.begin();  

while(iVector != a.end())
{
 std::cout<<" dump "<< (*iVector)<<std::endl;
 ++iVector;  
}

方法二数组

std::vector <T> v1;
for (size_t i = 0; i < v1.size(); i++)
{
    T tempNum = v1[i];
}

1.6. 删除

1.6.1. erase和clear区别

vector::clear()函数的作用是清空容器中的内容，但如果是指针对象的话，并不能清空其内容.

clear 清空并释放内存,并回收内存.

vector<int*> xx;
for(int it=0;it!=xx.size();++it)
{
    delete xx[it];
}
xx.clear();
xx.swap(vector<int>());

vector::erase()用于清空容器中的内容以及释放内存,并返回指向删除元素的下一个元素的迭代器。

1.6.2. 删除最后一个元素

   v1.pop_back();   //删除最后一个元素

1.6.3. 删除开头的元素

   v1.erase(v2.begin()); //删除开头的元素

1.6.4. 删除[begin,end]区间的元素

   v1.erase(v1.begin(),v1.end);

1.6.5. 删除全部元素

方法一

v1.clear()

方法二

std::vector<T>::iterator iVector = v1.begin();

while(iVector != v1.end())
{
    delete (*iVector)->p;
    iVector = v1.erase(iVector);
}

方法三

while(pVector->size() != 0)
{
    //pop_back方法无返回值
    pVector->pop_back();
    //删除操作避免大量移动的方法，如果元素有申请堆栈的内存，不可用此方法
}

2. vector常见问题

2.1. 1.push_back 与 emplace_back(c++11)区别

2.1.1. 相同点

都是在 vector 容器的尾部添加一个元素。

2.1.2. 不同点

push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；

而emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

总之,emplace会减少拷贝或者移动元素的过程,减少拷贝耗时.

2.2. 2.频繁对vector调用push_back()对性能的影响和原因

vector需要不断调整容量，容量调整过程是需要从旧容器拷贝到新的是原来容量1.5倍的大小的新容器中。

拷贝过程中耗时。

2.3. 3.vector中的reserve和resize的区别

reserve： 是直接扩充到已经确定的大小，可以减少多次开辟、释放空间的问题（优化push_back），就可以提高效率，其次还可以减少多次要拷贝数据的问题。reserve只是保证vector中的空间大小（capacity）最少达到参数所指定的大小n。reserve()只有一个参数。

resize：可以改变有效空间的大小，也有改变默认值的功能。capacity的大小也会随着改变。resize()可以有多个参数。

2.4. 4.为什么vector的插入操作可能会导致迭代器失效

vector动态增加大小时，并不是在原空间后增加新的空间，而是以原大小的两倍在另外配置一片较大的新空间，然后将内容拷贝过来，并释放原来的空间。由于操作改变了空间，所以迭代器失效。

2.2.1-vector