STL容器Vector

1.底层实现原理

vector的底层数据结构比较简单，时一段连续的存储空间，即数组。
```
//_Alloc 表示内存分配器，此参数几乎不需要我们关心
template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
    ...
protected:
    pointer _Myfirst;
    pointer _Mylast;
    pointer _Myend;
};
```
从它的源码中可以看出，它是通过三个指针来实现的。
- _Myfirst 指向的是 vector 容器对象的起始字节位置；
- _Mylast 指向当前最后一个元素的末尾字节；
- _Myend 指向整个 vector 容器所占用内存空间的末尾字节。
通过这三个指针来完成各种功能，下面举几个例子说明，详细说明在API函数中会进行讲解。
- iterator begin() {return _Myfirst;}
- iterator end() {return _Mylast;}
- size_type size() const {return size_type(end() - begin());}
- size_type capacity() const {return size_type(_Myend - begin());}
- bool empty() const {return begin() == end();}
- reference operator[] (size_type n) {return *(begin() + n);}
- reference front() { return *begin();}
- reference back() {return *(end()-1);}
注意:当vector为空时，三个指针都为null!
vector的扩容

vector是自动扩容的，当插入的数据大于当前vector的容量时，不同编译器的扩容是不一样的，VS本身就会自动扩大容量50%。
扩容过程如下所示：
- 找到一块新的地址空间，申请连续空间。
- 将旧空间中的数据按顺序移动到新地址空间中。
- 释放掉旧空间中的内存。

2.常用的API函数

函数名	功能
empty();	判断vector是否为空
capacity();	容器的容量
size();	容器数据的数量（大小）
push_back(elem);	在尾部插入一个元素
pop_back(elem);	删除尾部的一个元素
assign(beg, end);	区间中的数据拷贝赋值给本身
assign(n,elem);	将n个elem拷贝赋值给本身
insert(const_iterator pos, (count),elem);	在pos位置插入(count)个elem元素
erase(const_iterator pos);	删除指定位置的元素
clear();	清空所有位置的元素
reserve(int len);	设置vector的容量
at(int idx);	根据索引取值
operator[];	返回索引idx所指的数据
front();	返回容器中第一个数据元素
back();	返回容器中最后一个数据元素

另外c++11对push_back()进行了改进，提供了emplace_back()函数。
它们的区别主要在于是否进行了深度拷贝或者移动构造函数。

push_back(Person)
- 首先创建Person对象。
- 把Person复制到vector的尾部元素（拷贝/移动构造）。若是深拷贝，那么会影响性能，占用更多的堆空间。
- 若是拷贝需要销毁掉之前创建好的对象。
emplace_back(Person)
直接在vector的尾部新建对象。
代码实现如下所示。
```
void* ptr = malloc(sizeof(Person)); 
new (ptr)Person();
```
第1行: 主要是分配一个Person对象所需的内存空间, 但在vector里, 这步不需要考虑, 内部会在实现;
第2行: 这才是重点, 通过这样的语法, 就可以对已在的内存空间, 调用相应的Person类构造函数进行初始化;

同理emplace与insert也是一样的道理

3.迭代器失效解决办法

reserve()函数对vector进行扩容时，会造成迭代器失效。
erase()函数删除元素时，返回值就是下一个迭代器，在循环时容易造成迭代器丢失。

4.参考文献

vector底层实现机制
 vector的函数使用
 push_back()和emplace_back()详解
 移动构造函数详解