vector的底层（存储）机制

vector就是一个动态数组，底层有一个指针指向一片连续的内存空间，当空间不够装下数据时，会自动申请另一片更大的空间（一般是当前容量的2倍），然后把原来的数据拷贝过去，接着释放原来的那片空间；如果元素数量比较大(比如上百个)，重新分配内存的耗费会非常大，可能会出错。

当删除里面的数据时，其存储空间不释放，仅仅是清空了里面的数据。

vector中begin和end函数返回的是什么？

begin返回的是第一个元素的迭代器，end返回的是最后一个元素后面位置的迭代器。

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

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

vector怎么实现动态空间分布?

vector容器基于数组实现，其元素在内存中连续存放，vector容器除了容器尾部之外，在其他任意位置插入或删除元素时，都需要移动该元素后面的所有元素

capacity和size

capacity是容器不用重新分配内存就可容纳的元素个数，容器的大小一旦超过capacity的大小，vector会重新配置内部的存储器，导致和vector元素相关的所有reference、pointers、iterator都会失效。内存的重新配置会很耗时间，
size()是容器中现有的元素个数，max_size()返回Vector所能容纳元素数量的最大值(包括可重新分配内存)，一般是一个很大的数

reserve

vector频繁的销毁新建内存会导致效率很低，所以正确的做法是新建vector的时候初始化一个合适的大小，就像使用普通数组一样，这就用到了reserve。 如果reserve的值大于当前的capacity，那么会重新分配内存

reserve是容器预留空间，但并不真正创建元素对象，在创建对象之前，不能引用容器内的元素。否则会报错terminate called after throwing an instance of 'std::out_of_range'

保证vector的capacity最少达到它的参数所指定的大小n

resize

resize跟reserve不同了，它是改变容器的大小，并且可以创建对象，调用这个函数之后，就可以引用容器内的对象了.

void resize(size_type _Newsize)
void resize(size_type _Newsize, _Ty _Val)

对于第1个版本：

• 若_Newsize小于oldsize，则剩余元素值不变
• 若_Newsize大于oldsize，则新添加的元素值用元素的默认构造函数初始化（特别的，int型的将被初始化为0）

对于第2个版本：

• 若_Newsize小于oldsize，则剩余元素值不变,全部调用erase(begin() + _Newsize,end())擦除掉多余元素
• 若_Newsize大于oldsize，则新添加的元素值用提供的第2个参数初始化。

vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);

cout<< vec.size() <<"  "<<vec.capacity()<<"  "<<endl;   // 5   8
vec.resize(10);     // 改变大小
cout<< vec.size() <<"  "<<vec.capacity()<<"  "<<endl;   // 10   10

如果_Newsize小于之前的capacity，那么capacity不变。如果大于，那么capacity也要改变.也就是说 resize也涉及了内存重新分配，同时改变了capacity和size

data

返回指向vector中第一个数据的指针或空vector之后的位置

vector<int> v{1,2,3,4,5};
qDebug()<< *(v.data() ) ;  // 1

assign

// 先清除vector之前的内容,再将区间[first, last)的元素赋到当前vector
void assign(const_iterator first, const_iterator last);
// 先清除vector之前的内容,再将Count个Val插入到vector
void assign( size_type _Count, const Type& _Val );

使用assign赋值给容器:

vector<int> vec;
vec.assign(5,9);

cout<< vec.size() <<"  "<<vec.capacity()<<"  "<<endl;

容器的capacity和size都是5

push_back

但是如果使用push_back:

vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
vec.push_back(5);
cout<< vec.size() <<"  "<<vec.capacity()<<"  "<<endl;

此时容器的capacity为8

每次执行push_back操作,相当于底层的数组实现要重新分配大小,如果capacity不够插入新元素，需要开辟新的内存空间，把原来的元素复制到新内存，释放原来内存。

频繁的vector扩容会使效率很低，所以 不要使用for循环和push_back给vector赋值，这样会多次重新分配内存；如果先reserve分配需要的内存空间，再push_back会显著提高效率。

vector的几种清空容器办法

iterator erase(iterator it); // 删除指定元素，并返回删除元素后一个元素的位置（如果无元素，返回end()）
iterator erase(iterator first, iterator last); // 注意：删除元素后，删除点之后的元素对应的迭代器不再有效。

void clear() const; // 函数删除当前vector中的所有元素，相当于调用erase( begin(), end())

释放内存

vector的内存空间是只增加不减少的，erase和clear只删除元素，不能释放内存。如果是C++11环境，直接使用std::vector::shrink_to_fit()，它会将capacity缩减到size大小，所以如果要释放内存，可以先clear，再shrink_to_fit，这跟Qt里的qDeleteAll非常相似

元素是指针时，如何释放内存

如果vector中存放的是指针，而这些指针指向的对象没有销毁，那么当vector销毁时，内存不会被释放。

int v[6] = {1,2,3,4,5,6};
std::vector<int*> ps;
int* p1 = v;
int* p2 = v+1;
int* p3 = v+2;
int* p4 = v+3;

ps.push_back( p1 );
ps.push_back( p2 );
ps.push_back( p3 );
ps.push_back( p4 );

// delete ps.back(), ps.pop_back();

for (auto it = ps.begin(); it != ps.end(); it++)
{
  if (*it != NULL)
  {
    delete *it;
    *it = NULL;
  }
}

ps.clear();
ps.shrink_to_fit();

vector赋值速度

vector所有赋值方式的速度排名：

1. assign
2. resize以后用copy算法赋值
3. 赋值操作符，也就是 destinationVector = sourceVector;
4. 采用插入迭代器再用copy的方式
5. insert
6. push_back

记住最快的是assign，最慢的是push_back

vector遍历元素的速度

一般的速度排名： iterator > [] > at

但是根据编译器和平台的不同，iterator和[]速度有快有慢，但基本上at都是最慢的

尽量避免在vector前部插入元素

一般也没人这么干，任何在vetor前部的插入操作其复杂度都是O(n)的，所以十分低效，如果实在需要在前部插入元素，可以用list，它的效率远远超过vector

这样的代码是valid

using Type = std::vector<int>;
int f = 12;
Type vec={f};

参考：
vector/list的几种赋值方法的速度比较