（本文为有错漏和胡言乱语的个人笔记）
这篇笔记是我第一次看GCC源码时候记录的，比较繁琐而没有重点。此外，还忽略了C++11后添加的代码，比如emplace_back，移动构造（C++11部分的笔记补充在这里：万能引用，引用折叠，移动构造函数，emplace_back及其实现，完美转发及其实现）
总结一下这篇笔记:
如果你看了《STL源码剖析》中的vector实现方式，觉得很清晰明了，那其实我也是这么觉得的。
但当你想理论与实际相结合，想去看看GCC的源码，你会发现情况并不是很理想。
vector定义在stl_vector.h 中，它的继承关系如下所示:
vector--> _Vector_base [_Vector_impl --> _Tp_alloc_type]
vecotr继承自_Vector_base，而_Vector_base内含了一个_Vector_impl类，而_Vector_impl继承自_Tp_alloc_type。
_Tp_alloc_type的类型为:
74 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
...
221 typedef _Vector_base<_Tp, _Alloc> _Base;
222 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
(rebind的解释见注1)
即_Tp_alloc_type是vector的空间配置器的类型，_Vector_impl以继承的方式包含了一个空间配置器，并用其配置空间。
总的来说
STL的容器似乎都是以这种方式书写的，即deque和其他的容器也是如此。比如：deque--> _Deque_base [ _Deque_impl --> _Tp_Alloc_type]
至于为什么要这么复杂，在stl_deque.h中的注释中有稍微提到：
>447 /**
448 * Deque base class. This class provides the unified face for %deque's
449 * allocation. This class's constructor and destructor allocate and
450 * deallocate (but do not initialize) storage. This makes %exception
451 * safety easier.
452 *
453 * Nothing in this class ever constructs or destroys an actual Tp element.
454 * (Deque handles that itself.) Only/All memory management is performed
455 * here.
456 */
457 template<typename _Tp, typename _Alloc>
458 class _Deque_base
> ...
545 //This struct encapsulates the implementation of the std::deque
546 //standard container and at the same time makes use of the EBO
547 //for empty allocators.
548 struct _Deque_impl
549 : public _Tp_alloc_type
550 {
_Vector_impl有如下几个成员变量：
79 struct _Vector_impl
80 : public _Tp_alloc_type
81 {
82 pointer _M_start; //连续空间起点
83 pointer _M_finish; //所用空间的尾后位置
84 pointer _M_end_of_storage; //连续空间终点
85
《源码剖析》中定义typedef value_type* iterator为vector的迭代器，即指针。在GCC 5.4.0中确实如此，但又稍有不同。 GCC 5.4.0中的迭代器定义如下：
typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;
__normal_iterator是一个对原生指针的非常简单的包装。可以把它看作一个跟原生指针功能一样的随机访问迭代器。
在vector中有如下定义：
289 vector(size_type __n, const value_type& __value,
290 const allocator_type& __a = allocator_type())
291 : _Base(__n, __a)
292 { _M_fill_initialize(__n, __value); }
整个初始化分为了三部分：
第一部分 ： 构造函数链
初始化基类_Base。这里有一个构造函数链，我会详细说明：
134 _Vector_base(size_t __n, const allocator_type& __a)
135 : _M_impl(__a)
136 { _M_create_storage(__n); }
163 public:
164 _Vector_impl _M_impl;
这里_M_impl是_Vector_base的一个成员变量。 - _M_impl的构造函数为
90 _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT
91 : _Tp_alloc_type(__a), _M_start(), _M_finish(), _M_end_of_storage()
92 { }
115 allocator(const allocator& __a) throw()
116 : __allocator_base<_Tp>(__a) { }
81 new_allocator(const new_allocator&) _GLIBCXX_USE_NOEXCEPT { }
也就是说_Vector_impl只是初始化了start, finish, end_of_storage三个成员变量，__a则是完全无用的。
第二部分 分配空间
基类_Base的构造函数体调用了_M_create_storage分配了n个_Tp的空间。
181 private:
182 void
183 _M_create_storage(size_t __n)
184 {
185 this->_M_impl._M_start = this->_M_allocate(__n); //调用allocator分配并得到返回值（分配空间首地址）
186 this->_M_impl._M_finish = this->_M_impl._M_start; //刚开始容量为0 start = finish
187 this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; //end_of_storage = start + n;
188 }
而_M_allocate的实现如下：
76 typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer
77 pointer; //pointer即Tp*
166 pointer
167 _M_allocate(size_t __n)
168 {
169 typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr;
170 return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer();
171 }
而allocate是alloc_traits的一个静态成员函数，用于调用参数a的allocate方法分配n个空间。（由于_M_Impl继承了_Tp_alloc_type，所以可以作为alloc_traits<_Tp_alloc_type>::allocate的参数传入）
180 static pointer
181 allocate(_Alloc& __a, size_type __n)
182 { return __a.allocate(__n); }
183
184 static void deallocate(_Alloc& __a, pointer __p, size_type __n)
185 { __a.deallocate(__p, __n); }
到此，空间分配完成。
第三部分 为已分配的空间填充值
这一步用了vector的一个成员函数_M_fill_initialize(__n, __value)。它的定义如下：
1297 void
1298 _M_fill_initialize(size_type __n, const value_type& __value)
1299 {
1300 this->_M_impl._M_finish =
1301 std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value,
1302 _M_get_Tp_allocator());
1303 }
std::unitializied_fill_n_a是一个全局函数，用于填充已初始化的空间，可见另一篇博客。简单来说就是逐个视情况调用构造函数。
至此，构造函数完成。
非常常用的两个迭代器，其实就是_M_start, _M_finish。
555 const_iterator
556 begin() const _GLIBCXX_NOEXCEPT
557 { return const_iterator(this->_M_impl._M_start);
...
573 const_iterator
574 end() const _GLIBCXX_NOEXCEPT
575 { return const_iterator(this->_M_impl._M_finish); }
653 size_type
654 size() const _GLIBCXX_NOEXCEPT
655 { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
没什么好解释的。
733 size_type
734 capacity() const _GLIBCXX_NOEXCEPT
735 { return size_type(this->_M_impl._M_end_of_storage
736 - this->_M_impl._M_start); }
742 bool
743 empty() const _GLIBCXX_NOEXCEPT
744 { return begin() == end(); }
//见 gcc 5.4.0 std::vector，位于stl_vector.h
657 /** Returns the size() of the largest possible %vector. */
658 size_type
659 max_size() const _GLIBCXX_NOEXCEPT
660 { return _Alloc_traits::max_size(_M_get_Tp_allocator()); }
实际上实现的方式是：
//见 gcc 5.4.0 __gnu__cxx::new_allocator，位于new_allocator.h
112 size_type
113 max_size() const _GLIBCXX_USE_NOEXCEPT
114 { return size_t(-1) / sizeof(_Tp); }
仔细一想，好像也合理，32位电脑的内存只有32位地址，那不就是最大整型
vector::insert并没有被定义在stl_vector.h中，而是在vector.tcc中。（为什么？） 为了简洁，以下代码省略了为了C++11标准书写的代码。
105 template<typename _Tp, typename _Alloc>
106 typename vector<_Tp, _Alloc>::iterator
107 vector<_Tp, _Alloc>::
111 insert(iterator __position, const value_type& __x)
113 {
114 const size_type __n = __position - begin();
//如果是在末尾插入，且有空位
115 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
116 && __position == end())
117 {
118 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
119 ++this->_M_impl._M_finish;
120 }
121 else
122 {
133 _M_insert_aux(__position, __x);
135 }
136 return iterator(this->_M_impl._M_start + __n);
137 }
我们继续看_M_insert_aux的代码，也同样在vector.tcc中
// gcc 5.4.0 vector.tcc
324 template<typename _Tp, typename _Alloc>
325 void
326 vector<_Tp, _Alloc>::
327 _M_insert_aux(iterator __position, const _Tp& __x)
329 {
330 if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
331 {
//_Alloc_traits::construct(__a, __p, value)是一个静态函数，它会调用
// __a.construct(__p, value)
//注意， _M_impl因为继承了_Tp_alloc_type，所以是一个allocator
//以空间最后一个对象为蓝本构造新对象元素
332 _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
333 _GLIBCXX_MOVE(*(this->_M_impl._M_finish
334 - 1)));
335 ++this->_M_impl._M_finish;
337 _Tp __x_copy = __x;
// __position.base()即__position自己，见我另一篇介绍normal_iterator的文章
//_GLIBCXX_MOVE_BACKWARD3 是一个宏定义：#define _GLIBCXX_MOVE_BACKWARD3( _Tp, _Up, _Vp ) std::copy_backward(_Tp, _Up, _Vp)
// std::copy_backward的作用是：
// BidirIt2 copy_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );
// Copies the elements from the range, defined by [first, last), to another range ending at d_last. The elements are copied in reverse order (the last element is copied first), but their relative order is preserved.
339 _GLIBCXX_MOVE_BACKWARD3(__position.base(),
340 this->_M_impl._M_finish - 2,
341 this->_M_impl._M_finish - 1);
343 *__position = __x_copy;
347 }
348 else
349 {
350 const size_type __len =
351 _M_check_len(size_type(1), "vector::_M_insert_aux"); //一个检查size()返回的长度是否合理的方法，如果合理，返回size()的结果（这也能不合理?想不到例子)
352 const size_type __elems_before = __position - begin();
353 pointer __new_start(this->_M_allocate(__len)); //转调用this->_M_impl.allocate分配__len空间，并返回空间起始地址
354 pointer __new_finish(__new_start); //新的空间还没有元素__new_finish = __new_start
355 __try
356 {
357 // The order of the three operations is dictated by the C++0x
358 // case, where the moves could alter a new element belonging
359 // to the existing vector. This is an issue only for callers
360 // taking the element by const lvalue ref (see 23.1/13).
361 _Alloc_traits::construct(this->_M_impl,
362 __new_start + __elems_before,
366 __x); // Step 1, 先构造待插入元素
368 __new_finish = pointer();
369
//Step 2, 构造并复制[_M_start, , ___position)中的元素
//其实就是不断调用construct( &*(__new_start + i), *(_M_start + i))
//（注：在allocate后，如果你的类是trival的，那其实你的对象已经构造好了，只是值都是未定义的
//construct的作用只是对对象的值进行初始化。
370 __new_finish
371 = std::__uninitialized_move_if_noexcept_a
372 (this->_M_impl._M_start, __position.base(),
373 __new_start, _M_get_Tp_allocator());
374
375 ++__new_finish;
376
377 __new_finish
378 = std::__uninitialized_move_if_noexcept_a
379 (__position.base(), this->_M_impl._M_finish,
380 __new_finish, _M_get_Tp_allocator());//Step 3, 构造并复制[__position, _M_finish)中的元素
381 }
382 __catch(...)
383 {
384 if (!__new_finish) //__new_finish为0，说明step 1异常
385 _Alloc_traits::destroy(this->_M_impl,
386 __new_start + __elems_before);
387 else // step 2 step 3异常执行这里，destroy每一个construct的元素，不多不少，刚好
388 std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
389 _M_deallocate(__new_start, __len); //deallocate
390 __throw_exception_again;
391 }
//接下来销毁原来的空间。
392 std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
393 _M_get_Tp_allocator());
394 _M_deallocate(this->_M_impl._M_start,
395 this->_M_impl._M_end_of_storage
396 - this->_M_impl._M_start); //释放之前申请的所有空间
397 this->_M_impl._M_start = __new_start;
398 this->_M_impl._M_finish = __new_finish;
399 this->_M_impl._M_end_of_storage = __new_start + __len;
400 }
401 }
这段代码包含一些有趣的细节：
情况1 vector没有被塞满 :
此时vector中[_M_start, _M_finish)是已使用空间，[_M_finish, _M_end_of_storage)备用空间，我们想要在position处插入一个元素。
1. 332行调用_Alloc_traits::construct，在备用空间起始处以已使用空间最后一个元素为蓝本，构造了一个新的元素。相当于把最后一个元素即_M_finish - 1处的元素拷贝到了_M_finish处。
2. ++_M_finish
3. 339行调用std::copy_backward函数将[position, _M_finish - 2) 拷贝到 [position + 1, M_finish - 1)，这里没有拷贝最后一个元素，因为在第一步已经通过拷贝构造函数拷贝过了。
这里有两个细节:
*(it + 1) = *it从前至后拷贝的，所以这里如果使用copy就会使__position处的元素覆盖后面的所有元素 ，而 std::copy_backward是由后至前拷贝的。 *(_M_finish) = *(_M_finish + 1)，只能通过constrcut。4. 最后一步，将待插入元素赋值给__position
情况2 vector恰好满了：
这部分代码我在注释里已经说的很清楚了。3步操作定义的恰到好处，使得异常处理非常的舒服。
其实push_back就是insert的特殊情况insert(end(), value))，实现也是借助于_M_insert_aux，代码略了。
有空补
at(i)会做下标检查，出错会抛出out_of_range异常，而[]不检查下标。
源码如下:
778 reference
779 operator[](size_type __n) _GLIBCXX_NOEXCEPT
780 { return *(this->_M_impl._M_start + __n); }
798 /// Safety check used only from at().
799 void
800 _M_range_check(size_type __n) const
801 {
802 if (__n >= this->size())
803 __throw_out_of_range_fmt(__N("vector::_M_range_check: __n "
804 "(which is %zu) >= this->size() "
805 "(which is %zu)"),
806 __n, this->size());
807 }
821 reference
822 at(size_type __n)
823 {
824 _M_range_check(__n);
825 return (*this)[__n];
826 }
看vector的源码，pop_back或者erase后并不会释放空间，即vector的空间只会增长不会减小。 释放需要通过swap，看这里cnblogs
可以看到，虽然继承以及模板将vector打得非常碎片化，但本质上vector的组成部分和《源码剖析》差不多：
注1：rebind详解
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
类__gnu_cxx::__alloc_traits<_Alloc> 定义了rebind:
//ext/alloc_traits.h
206 template<typename _Tp>
207 struct rebind
208 { typedef typename _Alloc::template rebind<_Tp>::other other; };
假设_Alloc为__gnu_cxx::new_allocator，而__gnu_cxx::new_allocator定义了rebind：
69 template<typename _Tp1>
70 struct rebind
71 { typedef new_allocator<_Tp1> other; };
假设我们要定义一个list（STL中的双向链表，后面的博客会介绍）,则它的第二个模板参数_Alloc为默认的std::allocator。
但其实list不需要std::allocator，因为链表申请空间的基本单位为Node，那它需要的就是std::allocator。
那如何从std::allocator得到std::allocator呢？就可以利用__gnu_cxx::__alloc_traits<std::allocator<int>>::rebind<Node>::other得到std::allocator<Node>。
rebind也是C++标准定义的allocator标准接口之一。
总结一下，就是容器内部可以用rebind来获得用户要求的空间分配器，以分配容器内部需要的空间。