_M_range_initialize 函数也是一个函数模板，其最后一个形参用来判断调用那个函数的定义，vector 中有两种 _M_range_initialize 的定义。

_M_range_initialize 的第一种定义中，第三个形参为 input_iterator_tag。函数中直接调用 push_back 将 __first 到 __last 之间的元素逐个插入到尾部。但这种初始化的方法效率是较低的，因为当前 vector 是没有内存分配的，push_back n 个元素可能大致需要进行 log(n) 次内存分配，每次当 push_back 函数中遇到空间不够时，在重新内存分配时会申请原来内存的 2 倍。

  template <class _InputIterator>
  void _M_range_initialize(_InputIterator __first,  
			   _InputIterator __last, input_iterator_tag)
  {
    for ( ; __first != __last; ++__first)
      push_back(*__first);
  }

_M_range_initialize 的第二种定义中，第三个形参为 _forward_iterator_tag (如果第三个形参是 forward_iterator_tag 的派生类也会调用当前定义，尽管 forward_iterator_tag 的派生类也是 input_iterator 的派生类，但会选择派生关系更近的 forward_iterator_tag)会调用下面的函数定义。

函数首先通过计算 __first 和 __last 的距离来判断一共有多少个元素需要被插入到 vector 中。并根据元素个数分配好内存空间 (调用基类的内存分配函数进行内存分配)，最后在分配好的内存上拷贝或者构建这些对象。

STL 中的拷贝函数比较常用的是 copy 和 unitialized_copy，假设拷贝的元素是 _Tp 类型，二者的区别在于 copy 函数会调用 _Tp 类型的 operator= 函数来进行复制，而 uninitialized_copy 会调用 _Tp 类型的拷贝构造函数进行复制。那么待拷贝的空间上的元素还没有进行初始化，则应该选择用拷贝构造函数进行初始化(而不是 operator= 函数); 如果待拷贝的空间上的元素已经被初始化了，则可以直接用 operator= 函数进行赋值。因此前者用 uninitialized_copy 进行拷贝，后者用 copy 函数进行拷贝。

对于那些拷贝构造函数和 operator= 函数定义一致的类型，copy 函数和 uninitialized_copy 函数的功能是一样的。对于这种情况 uninitialized_copy 中会直接调用 copy 函数进行复制。

  // This function is only called by the constructor. 
  template <class _ForwardIterator>
  void _M_range_initialize(_ForwardIterator __first,
			   _ForwardIterator __last, forward_iterator_tag)
  {
    size_type __n = 0;
    distance(__first, __last, __n);
    _M_start = _M_allocate(__n);
    _M_end_of_storage = _M_start + __n;
    _M_finish = uninitialized_copy(__first, __last, _M_start);
  }

vector 的析构函数用来销毁_M_start 到 _M_finish 的对象。这里只是销毁对象，对于已经分配的内存不由 vector 进行释放，内存释放工作由基类的析构函数调用 _M_deallocate 来实现。

  ~vector() { destroy(_M_start, _M_finish); }

operator= 函数，是用一个 vector 的内容来初始化另一个 vector ，但这两个 vector 必须要有相同的模板实参。

如果指定 vector __x 的大小（指size()) 比当前 vector 的 capacity() 还大 。则需要重新进行内存分配。这里调用成员函数 _M_allocate_and_copy 来一并实现分配和复制的工作。 _M_allocate_and_copy 来实现内存重新分配和对象构造。并对原来 vector 中的对象进行销毁，再对原来分配的内存进行回收。因为当前的 vector 并没有结束，所以程序不会调用析构函数去销毁对象，也不会调用基类的析构函数去释放内存，这些工作都需要显示的调用。对象销毁和内存回收完毕后，则可以重新调整 _M_start , _M_finish _M_end_of_storage 的值，使得当前 vector 使用新的内存空间。

如果当前的 vector 的内存空间足够容纳 __x 中的所有元素，则不额外的申请内存。再判断当前 vector 的 size() 是否比 x 的 size() 要大，如果是则拷贝 x 中的对应元素到当前 vector 中。并将当前 vector 中多余的元素删除，使得在当前 vector 中只保留 x 中的元素。

如果当前 vector 的 size() 比 x 的 size() 要小。则先拷贝 x 中的前 size() （ vector 的前 size() 个元素已初始化，直接用 copy 进行拷贝) 个元素，剩下的元素调用 uninitialized_copy 进行拷贝。同时对于不同的情况要注意 _M_start , _M_finish , _M_end_of_storage 的修改。

vector<_Tp,_Alloc>::operator=(const vector<_Tp, _Alloc>& __x)
{
  if (&__x != this) {
    const size_type __xlen = __x.size();
    if (__xlen > capacity()) {
      iterator __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
      destroy(_M_start, _M_finish);
      _M_deallocate(_M_start, _M_end_of_storage - _M_start);
      _M_start = __tmp;
      _M_end_of_storage = _M_start + __xlen;
    }
    else if (size() >= __xlen) {
      iterator __i = copy(__x.begin(), __x.end(), begin());
      destroy(__i, _M_finish);
    }
    else {
      copy(__x.begin(), __x.begin() + size(), _M_start);
      uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
    }
    _M_finish = _M_start + __xlen;
  }
  return *this;
}

函数 _M_allocate_and_copy 实现很简单，先调用基类的 _M_allocate 分配 __n 个元素所需的内存，然后调用 uninitialized_copy 将原先的元素拷贝到新分配的内存上。

  template <class _ForwardIterator>
  iterator _M_allocate_and_copy(size_type __n, _ForwardIterator __first, 
					       _ForwardIterator __last)
{
    iterator __result = _M_allocate(__n);
    __STL_TRY {
      uninitialized_copy(__first, __last, __result);
      return __result;
    }
    __STL_UNWIND(_M_deallocate(__result, __n));
  }

reserve 函数实现的功能是保证 vector 中至少有容纳 __n 个元素的内存空间（可以大于），reserve 不会改变 vector 中的内容。如果 __n 比 size() 要小，也不会将多余的元素删除。当 __n 比当前 vector 的 capacity 还有大时，则需要重新分配内存空间。此时会将原来的元素拷贝到新分配的内存空间上。

  void reserve(size_type __n) {
    if (capacity() < __n) {
      const size_type __old_size = size();
      iterator __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
      destroy(_M_start, _M_finish);
      _M_deallocate(_M_start, _M_end_of_storage - _M_start);
      _M_start = __tmp;
      _M_finish = __tmp + __old_size;
      _M_end_of_storage = _M_start + __n;
    }
  }

assign 函数是一个函数模板，根据 _InputIterator 的类型，分别调用不同的 _M_assign_dispatch 函数。具体的调用机制和前面讨论的一样，也是通过判断 _InputIterator 到底是的类型是整型还是迭代器来决定调用哪个 _M_assign_dispatch 函数。

如果 _InputIterator 为整型变量，第一个形参用来表示拟待赋值的元素个数，第二个形参表示元素的值。但所有对函数模板的实例化都需要第一个形参和第二个形参的类型是一样的。如果当前元素是一个类的对象，希望为这个 vector 进行赋值，使得 vector 被赋值之后 一共有 __n 个元素，且每个元素都是一个相同的对象，这个功能是函数模板提供不了的，因为 __n 是一个整型，而元素是对象。两个的类型不一致，函数模板是不能被实例化的，assign 函数有另外的定义来实现这一功能。

如果模板实参的类型不为整型，那么则认为他是一个迭代器，并且认为函数的第一个形参 __first 和第二个形参 __last 限定了一片内存空间，并将这片内存空间的内容赋值给当前的 vector 。

  template <class _InputIterator>
  void assign(_InputIterator __first, _InputIterator __last) {
    typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
    _M_assign_dispatch(__first, __last, _Integral());
  }

_M_assign_dispatch 一共有两个函数定义，区别在于第三个函数形参不同，如果第三个形参为__true_type，则认为前面两个形参都是整型。并调用 _M_fill_assign 函数进行赋值，_M_fill_assign 当前 vector 赋上 __n 个 值为 __value 的元素。

如果第三个形参为 __false_type 则认为前面两个形参是迭代器。将迭代器限定的内存空间的元素通过 _M_assign_aux 复制到当前的 vector中。

  template <class _Integer>
  void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
    { _M_fill_assign((size_type) __n, (_Tp) __val); }

  template <class _InputIter>
  void _M_assign_dispatch(_InputIter __first, _InputIter __last, __false_type)
    { _M_assign_aux(__first, __last, __ITERATOR_CATEGORY(__first)); }

assgin 函数用来将 __n 个值为 __val 的元素赋值给当前 vector 。

  void assign(size_type __n, const _Tp& __val) { _M_fill_assign(__n, __val); }

_M_fill_assign 函数将 __n 个值为 __value 的元素赋值给当前 vector 。函数首先检测当前 vector 的 capacity 是否能够容纳 __n 个元素。如果不能，则声明一个临时变量 __tmp 并对 __tmp 进行初始化，使得初始化之后 __tmp 之中有 __n 个值为 __value 的元素。然后调用 swap 函数将 tmp 和当前 vector 进行交换，交换只是简单的交换 _M_start , _M_finish _M_end_of_storage 的值。因为整个 vector 只有这三个成员变量。

因为 __tmp 是临时变量，当函数结束之后，它会销毁 __tmp 中的每个对象，同时会调用基类的析构函数回收其占有的内存空间 (因为 vector 的析构函数中对对象的销毁和基类的析构函数对内存的回收，都是在 _M_start 和 _M_end_of_storage 上进行，交换之后 tmp 占有的内存空间和当前 vector 的内存空间进行了互换。所以最后销毁和回收的内存空间其实是当前 vector 在与 __tmp 进行交换之前的那片内存空间)。

如果当前 vector 的 capacity 能够满足要求，那么判断 size() 和 __n 的大小，如果 __n 比当前的 size() 大，则将 vector 的前 size() 个元素都用 __value 进行填充。再将余下的 __n - size() 个元素填充到后面。

如果 size() 比 __n 大，则先将前 __n 个元素都用 __value 进行填充，fill_n 的返回值是指向第 __n 个元素之后的那个地址。然后调用 erase 函数会删除最后的 size() - __n 个元素。

template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::_M_fill_assign(size_t __n, const value_type& __val) 
{
  if (__n > capacity()) {
  //exit the function the tmp will be destroy and release.
    vector<_Tp, _Alloc> __tmp(__n, __val, get_allocator());
    __tmp.swap(*this);
  }
  else if (__n > size()) {
    fill(begin(), end(), __val);
    _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
  }
  else
    erase(fill_n(begin(), __n, __val), end());
}

_M_assign_aux 函数是将 __first 和 __last 包围的内存空间中类型为 _Tp 的元素复制到 vector。 函数有两个定义，根据第三个实参来区分不同的定义，这样的调用策略，在之前已经碰到过了，当迭代器的标记为 input_iterator_tag 是会调用第一个函数定义，其他的都会调用第二个函数定义。

_M_assign_aux 函数的第一种定义首先将 min (size(), __n) 个元素填充到 vector 的前 min (size(), __n) 个元素中，然后根据 size() 和 __n 的大小决定是删除多余的元素还是填充剩下的元素。

template <class _Tp, class _Alloc> template <class _InputIter>
void vector<_Tp, _Alloc>::_M_assign_aux(_InputIter __first, _InputIter __last,
					input_iterator_tag) {
  iterator __cur = begin();
  for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
    *__cur = *__first;
  if (__first == __last)
    erase(__cur, end());
  else
    insert(end(), __first, __last);
}

_M_assign_aux 的第二种定义会在第三个形参为 forward_iterator_tag 或者 forward_iterator_tag 的派生类对象时被调用。函数首先通过计算 __first 和 __last 的差值来判断 __first 和 __last 包围的内存空间中一共有多少个 _Tp 类型的对象。如果 __first 和 __last 包围的内存空间的元素个数比当前的 capacity 还要大，那么说明需要重新进行内存空间的分配，调用 _M_allocate_and_copy 分配合适的内存空间，并将对应的元素拷贝到新分配的内存空间，并用 __tmp 变量得到分配的地址空间的首地址。然后在销毁当前 vector 中的对象，并释放相应的内存空间。最后更改 _M_start, _M_finish, _M_end_of_storage 。

如果 __first 和 __last 包围的内存空间的元素个数 __len 没有超过 capacity 则不需要分配内存空间。再判断 __len 是否比 size() 要大，如果是，则先复制__first 到 __last 中的前 size() 个元素到 vector ，然后再将余下的 __n - size() 个元素复制到后面，因为后面的 __n - size() 个位置原先是没有初始化的，因此需要调用 uninitialized_copy 函数。而前 size() 个位置是在赋值之前就已经进行了初始化，可以直接调用 copy 函数进行复制。

如果 __len 比 size() 小，则直接将 __len 个元素复制到 vector 的前 __len个元素中。然后删除后面的 size() - __len 即可 。

vector<_Tp, _Alloc>::_M_assign_aux(_ForwardIter __first, _ForwardIter __last,
				   forward_iterator_tag) {
  size_type __len = 0;
  distance(__first, __last, __len);

  if (__len > capacity()) {
    iterator __tmp = _M_allocate_and_copy(__len, __first, __last);
    destroy(_M_start, _M_finish);
    _M_deallocate(_M_start, _M_end_of_storage - _M_start);
    _M_start = __tmp;
    _M_end_of_storage = _M_finish = _M_start + __len;
  }
  else if (size() >= __len) {
    iterator __new_finish = copy(__first, __last, _M_start);
    destroy(__new_finish, _M_finish);
    _M_finish = __new_finish;
  }
  else {
    _ForwardIter __mid = __first;
    advance(__mid, size());
    copy(__first, __mid, _M_start);
    _M_finish = uninitialized_copy(__mid, __last, _M_finish);
  }
}

STL 的 vector 分析（一）</br> STL 的 vector 分析（二）</br> STL 的 vector 分析（三）</br>