vector的push_back操作是将一个元素插入vector的末尾。
源码如下：
template <class T, class Alloc = alloc> void YVector::push_back(const T& x) { if (finish != end_of_storage) { construct(finish, x); ++finish; } else { insert_aux(finish, x); } }
函数insert_aux
template <class T, class Alloc = alloc> void YVector::insert_aux(iterator position, const T& x) { if (finish != end_of_storage) { construct(finish, *(finish - 1)); ++finish; T copy_x = x; copy_backward(position, finish - 2, finish - 1); *position = copy_x; } else { const size_type old_size = size(); const size_type new_size = old_size == 0 ? 1 : 2 * old_size; iterator new_start = data_allocator::allocate(new_size); iterator new_finish = new_start; try { new_finish = uninitialized_copy(start, position, new_start); construct(new_finish, x); ++new_finish; new_finish = uninitialized_copy(position, finish, new_finish); } catch (...) { destroy(new_start, new_finish); data_allocator::deallocate(new_start, new_size); throw; } destroy(begin(), end()); deallocate(); start = new_start; finish = new_finish; end_of_storage = new_start + new_size; } }
需要理解以上源码并不容易。看我一一道来。
1.start，finish，end_of_storage
首先必须了解vector的数据结构。如图：
vector是一段连续的内存空间。start，finish，end_of_storage三个指针描述了空间状态，这三个是普通的指针。start到finish是已经使用的内存，里面有元素。finish到end_of_storage是未使用的内存，里面没有元素。
由此三个指针可以得出一些简单的操作。
iterator begin() { return start; } //起始位置
iterator end() { return finish; } //结束位置
size_type size() const { return size_type(end() - begin()); } //已可用大小
size_type capacity() const { return size_type(end_of_storage - begin()); } //申请的内存大小
bool empty() { return begin() == end(); } //是否为空
reference operator[](size_type n) { return *(begin() + n); } //[]操作
reference front() { return *begin(); } //首元素
reference back() { return *(end() - 1); } //尾元素
其中一些定义
typedef T value_type; typedef value_type* pointer; typedef value_type* iterator; typedef value_type& reference; typedef size_t size_type;
2.construct，destroy
这个两个是全局的构造和析构函数。其中construct是调用placement new。
有关于placement new，参考 http://www.cnblogs.com/luxiaoxun/archive/2012/08/10/2631812.html
template<class T1, class T2> inline void construct(T1* p, const T2& value) { new (p)T1(value); }
placement new可以简单理解成在已经分配好的空间上构造。
在puch_back这里的情境中，如果内存的备用区还有空间，则用x在finish指向的空间上构造，同时移动finish指针。这里原本finish指向的空间是已经申请了的，所以使用placement new。
if (finish != end_of_storage) { construct(finish, x); ++finish; }
destroy有两个版本。destroy实现较复杂，参看《STL源码剖析》第二章。只需知道destroy会在指定范围进行析构。
template <class T> inline void destroy(T* pointer) { pointer->~T(); } template <class ForwardIterator> inline void destroy(ForwardIterator first, ForwardIterator last) { //实现略 }
3.allocate，deallocate
注意到定义类时出现了Alloc，这其实是配置器。vector默认使用alloc配置器。
template <class T, class Alloc = alloc>
在基本的alloc上封装一层simple_alloc。如下：
template <class T, class Alloc = alloc> class simple_alloc { static T* allocate(size_t n)
{ return n == 0 ? 0 : (T*)Alloc::allocate(n * sizeof(T)); } static T* allocate()
{ return (T*)Alloc::allocate(sizeof(T)); } static void deallocate(T *p, size_t n)
{ if (n == 0) Alloc::deallocate(p, n * sizeof(T)); } static void deallocate(T *p)
{ Alloc::deallocate(p, sizeof(T)); } };
实际上内部实现就是调用malloc和free，但是会有复杂的分级配置处理。在此不再讨论。参看《STL源码剖析》第二章。
可以就简单的把allocate，deallocate理解成malloc，free来辅助记忆，但务必记得没那么简单。
4.uninitialized_copy，copy_backward
uninitialized_copy处理如下图：
看起来好复杂……来看一下原型：
template <class InputIterator, class ForwardIterator> inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result) { return __uninitialized_copy(first, last, result, value_type(result)); }
如果[result，result + (last - first))范围内的迭代器都指向未初始化区域，则uninitialized_copy()会使用copy construct给输入来源[first，last)范围内的每一个对象产生一个拷贝放进输出范围。
更深的实现也贴出来：
template <class InputIterator, class ForwardIterator> inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result, T*) { typedef typename __type_traist<T>::is_POD_type is_POD_type is_POD; return __uninitialized_copy_aux(first, last, result, is_POD()); } template <class InputIterator, class ForwardIterator> inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result, __true_type) { return copy(first, last, result); } template <class InputIterator, class ForwardIterator> inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result, __false_type) { ForwardIterator cur = result; for (; last != first; first++, cur++) { construct(&*cur, *first); } return cur; }
这里面的逻辑是，首先把result的value_type得出，判断是否是POD类型……
如果是POD类型，则调用copy函数，如果不是POD类型，则一个一个调用construct()
所谓POD类型，指的是拥有无意义的构造、析构、拷贝、赋值函数的类型…能不能理解成比较简单的类。
像是如果类成员里有一个其他类的指针，这种复杂的类，需要有特殊的构造函数，就没有默认的那个构造函数。因此是non-POD类型。
接下来回到push_back。insert_aux里面判断还有备用空间的地方，有一个copy_backword函数。来看一下实现：
template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result ) { while (last!=first) *(--result) = *(--last); return result; }
作用是将一个范围中的元素按逆序拷贝到新的位置处。insert_aux截取如下：
if (finish != end_of_storage) { construct(finish, *(finish - 1)); ++finish; T copy_x = x; copy_backward(position, finish - 2, finish - 1); *position = copy_x; }
这里面有两个问题。第一为什么要有一份拷贝T copy_x = x；问题的答案参考知乎 https://www.zhihu.com/question/56911557/answer/150928396
第二个 copy_backward(position，finish - 2，finish - 1) 在插入位置是末尾的时候不会死循环吗？黑人问号？
position其实是finish - 1，也就是说传入参数后first比last还后面，那岂不是死循环？
引用：
1.《STL源码剖析》
2.http://www.cnblogs.com/luxiaoxun/archive/2012/08/10/2631812.html