1.前言

C++标准模板库(standard template library, STL)不仅是一个可复用组件库，而且是一个包罗算法与数据结构的模板框架。 STL已完全被内置到支持C++的编译器中，无需额外安装，

STL包括六大组件，可以互相组合套用：

• 1. 容器（containers）：各种数据结构的模板类，如vector，list，deque，set，map等用来存放数据。
• 2. 算法（algorithm）：sort，search，copy，erase等模板函数，大部分算法都包含在头文件<algorithm>中，少部分位于头文件 <numeric> 中。
• 3. 迭代器（iterator）：容器与算法之间的胶合剂，也就是”泛型指针“。
• 4. 仿函数（functors）：如果一个类将 ‘()’ 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象。由于该类对象的行为类似函数，又称为仿函数。
• 5. 配接器（adapters）：一种用来修饰容器、仿函数或者迭代器接口的东西。
• 6. 配置器（allocators）：负责内存空间配置与管理。

2. vector容器

vector被称为向量容器，该容器擅长在尾部插入或删除元素，时间复杂度为O(1)；而对于在vector容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶O(n)。使用vector容器，需要包含<vector>，注意这里无扩展名。

2.1 vector内存扩容策略

vector属于序列式容器(sequence_container)：其中的元素都可序，但未必有序。

如图所示，vector的内存模型与数组较为相似，但vector的内存模型是动态增长的线性空间，动态增长的实质是：需求空间超过当前可用空间后，不是在原空间之后接续新空间。这是因为线性空间后不一定有足够大小的空间，因此重新申请一块更大的空间来作为载体，然后复制已有数据到新申请的内存空间。

具体操作为：首先配置一块新空间，然后将元素从原空间搬到新的空间上，再把原空间释放。（涉及到了新空间的配置和旧空间的释放）

新空间的大小为一般为原空间大小的二倍。注意：二倍增长并不是必然的，不同的编译环境可以有不同的实现，但若增长倍数小于2则可能会导致扩容频繁；增长倍数较大则可能导致申请了较大的空间而未使用，从而造成浪费。 此外，vector为了降低空间扩容的速度，在配置空间时留有一部分空间以便之后扩容，这就是size()和capacity()的区别。size()返回使用了多少空间，capacity()返回了配置了多少空间。当两者相等时说明vector容器已经满了，再插入元素需要扩容。

2.2 vector迭代器

迭代器是行为类似指针的变量，相当于容器和算法之间的中介。迭代器可以指向容器中的某个元素，通过迭代器就可以读写它指向的元素。

如上图所示，两个迭代器start和finish来指向目前线性空间已使用的头和尾，以迭代器end_of_storage来指向当前配置空间的尾端。该图中扩容和迭代器变化步骤如下：

• 1. vector vec(2,5)，即申请两个元素空间并赋值5，此时start指向起始地址，finish指向两元素空间末尾，end_of_storage指向申请空间（两元素）末尾；
• 2. 当push_back(4)时，原2个元素空间已满，申请二倍空间，复制5，5于新空间，并填入4，此时由于空间重新分配，原迭代器失效，新start指向起始地址，finish指向4之后，end_of_storage指向申请空间（四个元素）末尾；
• 3. push_back(3)时，原空间共有4个位置，已填入3个元素，3加入后刚好填满；
• 4. 当push_back(2)时，原4个元素空间已满，便申请一块8元素的新空间，再将2填入；
• 5. 再将1填入，此时仍有两个元素的空位以供备用； 所以finish和end_of_storage不是一个含义，finish指的是使用空间的末尾，end_of_storage是申请的空间的末尾。因此，使用size()和capacity()进行区分，size()的大小时start到finish的大小，capacity()的大小则是start到end_of_storage的大小。 此处需要注意的是，对vector的操作如果引起的空间重新分配，那么原vector的所有迭代器就都失效。

class vector {
    ……
protected:
    iterator start;			 //当前已用空间的头部
    iterator finish;		    //当前已用空间的尾端
    iterator end_of_storage;	//当前配置空间的尾端
};

2.3 '[]'操作符

vector可以像数组一样，支持使用'[]'操作符根据下标获取元素。简单来讲，vector中元素大小固定，在知道start的基础上，我们只需要在其基础上进行地址偏移就能找到所需元素。（经典面试题：vector的随机访问如何做到？）源码如下：

reference operator[](size_type n){
    return *(begin() + n);
}

2.4 迭代器的常用方法

vector的所有操作都可以从源码中看出端倪，此处将常用操作源码总结：

STL中规定容器的区间遵循前闭后开原则，即容器中的一对迭代器start和finish标识的前闭后开区间，从start开始，直到finish-1.迭代器finish所指的是“最后一个元素的下一位置”。这样定义的好处主要有两点：1. 为“遍历元素时，循环的结束时机”提供一个简单的判断依据。只要尚未到达end()，循环就可以继续下去; 2. 不必对空区间采取特殊处理手段。空区间的begin()就等于end();

class vector {
    ……
public:
    /**
     * begin()函数源码
     * 用于返回start迭代器
     **/
    iterator begin() {
        return start;
    }

    /**
     * end()函数源码
     * 用于返回finish迭代器
     **/
    iterator end() {
        // STL容器的前闭后开原则，end迭代器并不指向最后一个元素 而是最后一个元素的后面
        return finish;
    }

    /**
     * size()函数源码
     * 用于返回start-end的值——已保存的元素个数
     **/
    size_type size() const {  // 返回start-end的值 即已保存的元素个数
        return size_type(end() - begin());
    }

    /**
     * capacity()函数源码
     * 返回end_of_storage - start的值——vector能够保存元素上限
     **/
    size_type capacity() const {  // 返回end_of_storage - start的值， 即vector能够保存元素上限
        return size_type(end_of_storage - begin());
    }

    /**
     * empty()函数源码
     * 通过判断start迭代器与finish迭代器是否相等，返回vector是否为空
     **/
    bool empty() const { 
        return begin() == end();
    }

    /**
     * []操作符重载
     * 实现根据下标取元素
     **/
    reference operator[](size_type n) {
        return *(begin() + n);
    }

    /**
     * front函数源码
     * 根据start迭代器，返回第一个元素的值
     **/
    reference front() {  
        return *begin();
    }

    /**
     * back函数源码
     * 根据finish迭代器，返回最后一个元素的值
     * 由于finish迭代器指向的是最后一个元素的后一个位置(STL容器的前闭后开原则)，因此这里需要用finish-1获取最后一个元素的位置
     **/
    reference back() {  // 返回最后一个要素
        return *(end() - 1);
    }
};

此处需要注意的是，对vector的操作如果引起的空间重新分配，那么原vector的所有迭代器就都失效。因此，如果我们将vector的迭代器保存到变量中时，可能会因为空间重新分配导致该变量保存的迭代器失效，例如：

#include <vector>
#include <iostream>
using namespace std;

int main()
{
    vector<int> vec;
    vec.push_back(0);
    auto iter = vec.begin();  // 使用变量保存迭代器
    cout<< *iter << endl;
    for(int i = 0; i < 10; i++)  // 可能会引起vector空间重新分配的代码段
    {
        vec.push_back(i);
    }
    cout<< *iter << endl;  // 原迭代器失效，此处异常中断
}

2.5 vector的常用元素操作方法

vector元素操作方法很多，此处以常用的函数举例，并搭配空间管理加深理解。

2.5.1 push_back(const T& x)

表头	说明
函数功能	将新元素插入vector的尾端，在插入时需要关注两种情况：即vector当前是否还有空间，如果有则直接在备用空间上构造元素，调整迭代器finish；若没有，则需要扩充空间。
参数	1.需要加入的元素
返回值	void
时间复杂度	若vector有备用空间，则为O(1)；否则需要扩充空间时，为O(n)

push_back方法的源码如下：

void push_back(const T& x) {
    if(finish != end_of_storage)
    {
        constrcut(finish,x);
        ++finish;
    }
    else
    {
        insert_aux(end(),x);
    }
}

其中，insert_aux函数涉及到了空间的重新配置问题，这里剖析该函数源码以加深过程理解。

insert_aux方法的源码如下：

template<class T>
void insert_aux(iterator position, const T& x) {
    if(finish != end_of_storage) {										
        // 有备用空间	
    }
    else {
        // 获取当前vector的元素个数
        const size_type old_size = size();  
        // 计算扩展后的vector空间
        // 若扩充前vector是空的，则配置申请一个元素的空间
        // 若扩充前vector非空，则按照二倍扩充原则进行扩充
        const size_type len = old_size != 0 ? 2 * old_size : 1;  

        // 分配器allocator配置新空间
        // new_start和new_finish迭代器指向新分配的空间起点
        iterator new_start = data_allocator::allocate(len);  
        iterator new_finish = new_start;
        try {
            // 拷贝原vector中start到position区间的元素到new_start迭代器所指处 
            // push_back函数中调用insert_aux(end(),x)，因此position就是finish迭代器，这里就将原vector的所有元素拷贝过来
            // 执行后 new_finish迭代器就指向了原vector的所有元素拷贝到新位置的末尾
            new_finish = uninitialized_copy(start,position,new_start);	
            // 在new_finish处构造新元素x
            construct(new_finish,x);	
            // new_finish向后移一个位置	
            ++new_finish;
            // 再将原vector的position到finish区间的元素拷贝到new_finish迭代器所指处		
            // push_back函数中调用insert_aux(end(),x)，因此position就是finish迭代器，这里元素区间是空										    
            new_finish = uninitialized_copy(position,finish,new