文章首发于：My Blog 欢迎大佬们前来逛逛

1. vector的迭代器

vector维护的是一个连续线性空间。所以无论元素的类型是什么，普通指针都可以满足条件而作为vector的迭代器。

template <typename T, typename Alloc=alloc>
class vector
{
public:
	using value_type = T;
	using iterator = value_type*;
};

基于此，vector就可以写出这样的操作：

1 2	vector<int>::iterator //int* vector<char>::iterator //char*

其实就是一个 int的指针，或者 char的指针。

2. vector的数据类型

vector是一个简单的线性连续空间。

它以两个迭代器 start 和 finish 分别表示vector的起始元素的地址和终止元素的地址。

并且还具有一个 end_of_storage 表示vector开辟的空间的终止位置。

所以：

start - finish 表示的就是我们在连续空间中已经使用的范围。
start - end_of_storage 表示我们的总的空间大小。
finish - end_of_storage 表示我们还未使用过的空间总大小。

一个vector的容量一定大于等于其已分配元素的空间大小。

我们便可以得到关于空间大小的一系列函数：

template <typename T, typename Alloc=alloc>
class vector
{
public:
	using value_type = T;
	using iterator = value_type*;
	using pointer = value_type*;
	using reference = value_type&;
	using size_type = size_t;
	using difference_trpe = ptrdiff_t;
public:
	inline iterator begin() { return start; }
	inline iterator end() { return finish; }
	inline size_type size()const { return static_cast<size_type>(end() - begin()); }
	inline size_type capacity()const { return static_cast<size_type>(end_of_storage - begin()); }
	inline bool empty()const { return begin() == end(); }
	inline  reference operator[](size_type n) { return *(begin() + n); }//int a[1]={5}; a[1]=5;
	inline reference front() { return *begin(); }//返回的是值
	inline reference back() { return *(end() - 1); }
private:
	iterator start;
	iterator finish;
	iterator end_of_storage;
};

注意front和back取得的是值，并且值以引用的方式返回的效率相对较优。

重载的[] 运算符取得是第 [i] 个位置的值，并且也是以引用的形式返回。

关于vector的内存配置的原理：

3. vetor的空间配置器

SGI STL容器中默认使用的空间配置器说第二级空间配置器：

//malloc_alloc 为第一级空间配置器
typedef __malloc_alloc_template<0> malloc_alloc;
//alloc默认为多线程第二级空间配置器
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;

可以看到在vector的头部我们具有：

template <class T, class Alloc = alloc>//Alloc：第二级空间配置器
class vector {
protected:
    // simple_alloc 空间配置器 ->data_allocator
  	typedef simple_alloc<value_type, Alloc>  data_allocator;  
    ...
}

所以Alloc默认为第二级空间配置器，然后在simple_alloc中输入其元素类型和配置器属性，并且用 data_allocator作为vector的空间配置器别名。

simple_alloc 我们已经在第一章讲过了，他是一个封装了一二级配置器调用接口的抽象类

4. vector的构造函数

vector通过空间配置器来构造元素。

其中一个构造函数的方法：配置n个元素大小的空间，并且初始化为val值

//vector的其中一个构造函数
vector(size_type n, const value_type& val) { fill_initialize(n, val); }//n个元素为val值
//填充并且初始化
void fill_initialize(size_type n, const value_type& val)
{
    start = allocate_and_fill(n, val);//起始地址
    finish = begin() + n;//元素结束地址
    end_of_storage = finish;//总容量结束地址
}
iterator allocate_and_fill(size_type n, const value_type& val)
{
    iterator res = data_allocator::allocate(n);//开辟n个元素的空间
    uninitialized_fill_n(res, n, val);//res开始填充n个val
    return res;//返回此空间的起始地址
}

在vector中 fill_initialize用来调整空间的范围；

allocate_and_fill 用来开辟n个元素的空间然后填充进去val值

其中 allocate_and_fill 还要调用：

vector空间配置器的allocate 来开辟n个元素的空间。
uninitialized_fill_n 用来往指定空间填充val值

allocate_and_fill的函数内部首先使用vector的空间配置器data_allocator(typename)来调用了addlocate，然后再根据，vector使用第二级空间配置器，因此转为 第二级空间配置器的 allocatoe的实现去。

data_allocator::allocate是在自由链表中取出一块合适的地址空间，因此其返回值表示分配的这块空间的起始地址，用res表示。

uninitialized_fill_n接受第一个迭代器表示开始的地址，n个val值，在此函数中会使用 __type_traits 的类型推导机制，来推导出此迭代器所指元素的类型，并且选择适当的填充方法：

_false_type：非POD类型，进行constructor构造
_true_type：POD类型，直接进行内存的操作 fill_n，memcpy，memmove等

以res为起点，填充n个地址单元的值为val

分配与填充元素成功后，再把此分配空间的起始地址返回，给到start，然后再调整 finish 和end_of_storage。

5. vector的销毁与析构

~vector() { 
    destroy(start, finish);
    deallocate();
  }
...
void deallocate() {
    if (start) data_allocator::deallocate(start, end_of_storage - start);
  }

析构分成两步：

首先销毁所有元素，调用全局的destroy销毁函数，销毁start到finish的所有已经存在的元素。
然后调用deallocate函数析构所有对象。

deallocate的函数实现：

直接对vector的空间配置器调用deallocate 即可，它接受一个start，表示析构的空间的开始地址，和一个需要析构的空间总大小。

deallocate的具体实现我们已经在第一章空间配置器里讲过了。

4. vector对元素的操作

4.1 pop_back

弹出最后一个元素，代码实现如下：

//弹出最后一个元素
inline void pop_back() { finish--; destroy(finish); }

...
    //全局销毁函数
template <class T>
inline void destroy(T* pointer) {
    pointer->~T();      // 单个对象的析构
}

把指向元素末尾的 finish 直接减一即可，然后调用全局的destroy销毁销毁最后一个元素的空间

4.2 erase

删除 [first,last) 左闭右开的范围的元素，代码实现如下：

//消除[first,last)中的元素
iterator erase(iterator first, iterator last)
{
    //将[last,finish)中的元素全部拷贝到first处的位置
    iterator end_pos = std::copy(last, finish, first);
    destroy(end_pos, finish);//清除[end_pos,finish)元素空间
    finish = finish - (last-first);
    return first;
}

调用copy函数，copy的作用是是将 [last,finish) 左闭右开范围的元素拷贝至 first 处。

这样就做到了将 last之外finish之前往前移，覆盖掉 [last,finish)范围内的元素。

同时std::copy函数（往后会讲解）完成后返回end_pos，代表从此处开始，往后的元素都是无用的

直接调用全局的destroy函数删除此end_pos - finish 的元素即可。

最后调整finish为操作之后的finish，返回first。

erase 一个位置的元素：

首先要判断删除的元素是不是最后一个元素（它的下一个位置是 finish的位置）

//消除position位置的元素
iterator erase(iterator position)
{
    if (position + 1 != end())
    {
        std::copy(position + 1, finish, position);
    }
    destroy(finish);//随便销毁一个元素
    finish -= 1;//随便减少1个元素大小
    return position;
}

当position位置的元素是最后一个元素时：position+1 == end；此时直接销毁他即可，相当于直接销毁最后一个元素
当position位置的元素不是最后一个元素时：需要把后面的元素覆盖过来，使用std::copy函数，把后面的位置元素往前覆盖，然后再销毁最后一个位置元素。

4.3. clear

直接清除[begin,end) 的全部元素即可：

1 2	//清除所有元素 inline void clear() { erase(begin(), end()); }

4.4 insert*

vector具有一个比较复杂的insert的版本，接受三个参数：

起始位置
插入元素个数
insert元素值

在起始位置 position处，插入 n个元素，每个元素初始化为 x值

分为三种情况：

如果备用空间大于插入的元素个数：无需扩容
如何小于插入元素个数，则需要扩容

把这个复杂的搞定了，其他的就很简单了。

无需扩容的情况：并且到finish为止，现有的元素的数量（elem_after）大于等于插入的元素数量 n

首先把绿色区域往后拷贝，使用 uninitialized_copy
然后把蓝色区域往后拷贝，使用 copy_backward 反向拷贝到 old_finish
最后在position位置拷贝进新的x元素，使用 fill填充即可

无需扩容的情况：但是到finish为止，现有的元素的数量（elem_after）小于插入的元素数量 n

直接把n 大于elem_after之后的部分拷贝到 finish之后，使用 uninitialized_fll_n
把position到finish之间原有的元素全部拷贝到finish之后，为图中蓝色区域，使用 uninitialized_copy
最后把剩余的n的一部分填充至 position到finish之间，使用 fill填充

需要扩容的情况：

剩余备用的元素无法存放进全部的 n 个元素，因此需要重新分配空间，并且销毁原空间。
首先获得容纳这些全部元素至少需要多少空间
调用第二级空间配置器的allocate重新分配空间。
1. 首先把start到position的全部元素拷贝到新的空间，使用 uninitialized_copy
2. 然后把这n个元素拷贝到finish之后的空间，使用 uninitialized_fill_n（注意这是个插入的过程）
3. 最后再把原来 position到 finish之间的元素全部拷贝到 finish之后，使用 uninitialized_copy
再把原来的空间全部销毁，调用全局的destory，然后再调用第二级空间配置器的deallocate（销毁的顺序是先destroy然后再析构）
最后调整新的 start finish end_storage

注意：insert的过程中如果出现了内存不足的情况，就执行 commit or rallback的规则：

如果失败则try抛出异常，执行 destroy与 deallocate 销毁全部已成功的元素的空间及对象

template <class T, class Alloc>
void vector<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  if (n != 0) {
    if (size_type(end_of_storage - finish) >= n) {//剩余的空间足够容纳n个
      T x_copy = x;//需要赋予的值
      const size_type elems_after = finish - position;
      iterator old_finish = finish;
      if (elems_after > n) {//插入点之后的现有元素个数大于要插入的个数n
        uninitialized_copy(finish - n, finish, finish);//[finish-n,finish]往后移动
        finish += n;//新的finish位置
        copy_backward(position, old_finish - n, old_finish);//从后往前copy[position,old_finish-n]的元素
        fill(position, position + n, x_copy);//[position,position+n]插入新的元素
      }
      else {//插入点之后的现有元素个数小于等于要插入的个数n
        uninitialized_fill_n(finish, n - elems_after, x_copy);//先把插入位置大于finish的部分元素全部插入
        finish += n - elems_after;//调整finish为插入部分新元素后的位置
        uninitialized_copy(position, old_finish, finish);//把原来的[position,old_finish]的全部元素移动到新的finish的后面
        finish += elems_after;//再次调整finish位置
        fill(position, old_finish, x_copy);//把[position,old_finish]赋值为新的元素
      }
    }
    else {//如果说备用空间小于要插入的元素所占用的空间
      const size_type old_size = size();        
      const size_type len = old_size + max(old_size, n);//获取总的需要的长度空间单元
      //分配空间
      iterator new_start = data_allocator::allocate(len);//新的start
      iterator new_finish = new_start;//新的finish
      __STL_TRY {
        new_finish = uninitialized_copy(start, position, new_start);
        new_finish = uninitialized_fill_n(new_finish, n, x);
        new_finish = uninitialized_copy(position, finish, new_finish);
      }
#         ifdef  __STL_USE_EXCEPTIONS 
      catch(...) {
        destroy(new_start, new_finish);
        data_allocator::deallocate(new_start, len);
        throw;
      }
#         endif /* __STL_USE_EXCEPTIONS */
      //销毁原始空间
      destroy(start, finish);
      vector_deallocate();
      //确定新的 start finish  end_of_storeage
      start = new_start;
      finish = new_finish;
      end_of_storage = new_start + len;
    }
  }
}

4.5 push_bcak*

在容器的末尾插入一个元素，分为两种情况：

如果还有备用空间，则直接构造对象。
否则，调用insert_aux进行扩充空间的insert

void push_back(const T& x) {
    if (finish != end_of_storage) {
        construct(finish, x);//使用 placement new 操作，直接在finish位置构造对象
        ++finish;
    }
    else
        insert_aux(end(), x);//此时finish==end_of_storage
}

接下来看push_back在处理插入一个元素空间不足的时候的处理方法：

调用 insert_aux，这个函数接受一个position，表示插入位置，x表示插入值：

在position位置插入元素x

如果空间足够插入此元素，则在position之后的元素往后移动一位。注意直接构造一个新的finish，即在finish处调用一次construct即可，无需在position处使用construct
如果备用空间不够，则计算出现有空间大小，然后开两倍原始空间大小。
1. 调用第二级空间配置器的 allocate 开辟空间
2. 把原始数据拷贝进新的空间中，在finish的地方调用一次construct，完成元素的插入。
销毁原始空间： destroy和deallocate函数
调整参数的位置。

template <class T, class Alloc>
void vector<T, Alloc>::insert_aux(iterator position, const T& x) {
    //在 position位置插入一个元素 x
  if (finish != end_of_storage) {
    construct(finish, *(finish - 1));
    ++finish;
    T x_copy = x;
    copy_backward(position, finish - 2, finish - 1);//从后往前拷贝，元素顺序不变
    *position = x_copy;//空出position这一个位置之后，插入x_copy新元素
  }
  else {
      //空间不够，开内存
    const size_type old_size = size();// start - finish 现有元素的空间size
    const size_type len = old_size != 0 ? 2 * old_size : 1;//开两倍内存，否则为1
    iterator new_start = data_allocator::allocate(len);
    iterator new_finish = new_start;
    __STL_TRY {
      new_finish = uninitialized_copy(start, position, new_start);
      construct(new_finish, x);
      ++new_finish;
      new_finish = uninitialized_copy(position, finish, new_finish);
    }

#       ifdef  __STL_USE_EXCEPTIONS 
    catch(...) {
        //commit or rallback
      destroy(new_start, new_finish); 
      data_allocator::deallocate(new_start, len);
      throw;
    }
#       endif /* __STL_USE_EXCEPTIONS */
    destroy(begin(), end());
    vector_deallocate();
    start = new_start;
    finish = new_finish;
    end_of_storage = new_start + len;
  }
}

HugeYlh

STL源码学习（3）- vector