STL 中的容器对一些应用最为广泛的数据结构进行了实现，它主要分为

序列式容器

和

关联式容器

两类，本文着重介绍使用最频繁的 vector 容器。

一、序列式容器

1.vector

https://zh.cppreference.com/w/cpp/container/vector

vector 是应用最为广泛的顺序容器，可以简单地将它看作是

一个能够存放任意类型元素的动态数组

，是使用 new 创建动态数组的替代品，它的底层实现是一段连续的线性内存空间。

vector 派生自 _Vector_base，_Vector_base 主要有以下三个成员：

pointer _M_start;
pointer _M_finish;
pointer _M_end_of_storage;

三者均为标识数据边界的迭代器，_M_start 标识缓冲区内数据区的

左实边界

，_M_finish 标识缓冲区内数据区的

右实边界

，_M_end_of_storage 标识内存缓冲区的

右虚边界

。


push_back()

可用于向 vector 中插入元素，其具体实现如下：

void push_back(const value_type &__x) {
    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) { // 未满载
        _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
        ++this->_M_impl._M_finish; // 增加 size
    } else { // 满载
        _M_realloc_insert(end(), __x);
    }
}

在向 vector 中插入元素时，如果已分配的空间不足（即发生满载），并不会在后面直接追加分配，而是通过

_M_realloc_insert()

重新分配所有的空间，然后依次拷贝原 vector 中的数据

。因此，为了降低空间分配的性能开销，vector 实际分配的内存大小一般会比需求量更大一些，从而避免在扩容时重新进行内存分配，这便是

容量

（capacity）的概念。通常可以通过

reserve()

为 vector 提前预留指定大小的空间以减少内存拷贝。


_M_realloc_insert()

的具体实现如下：

#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
template<typename... _Args>
void vector<_Tp, _Alloc>::_M_realloc_insert(iterator __position, _Args&&... __args)
#else
template<typename _Tp, typename _Alloc>
void vector<_Tp, _Alloc>::_M_realloc_insert(iterator __position, const _Tp& __x)
#endif
{
	/* _M_check_len 在传入参数为1的情况下，只要没有超出 stl 规定的最大内存大小，每次返回当前容器大小的双倍，初次返回1 */
    const size_type __len = _M_check_len(size_type(1), "vector::_M_realloc_insert");
    
    pointer __old_start = this->_M_impl._M_start;
    pointer __old_finish = this->_M_impl._M_finish;
    const size_type __elems_before = __position - begin();

    pointer __new_start(this->_M_allocate(__len)); // _M_allocate 根据 __len 的值申请相应大小的内存空间
    pointer __new_finish(__new_start);
    
    __try
    {
#if __cplusplus >= 201103L
		/* 向新的 vector 中追加待插入元素，通过完美转发避免了临时变量的生成 */
        _Alloc_traits::construct(this->_M_impl, __new_start + __elems_before, std::forward<_Args>(__args)...);
#else
		/* 向新的 vector 中追加待插入元素，有临时中间变量的生成 */
        _Alloc_traits::construct(this->_M_impl, __new_start + __elems_before, __x);
#endif
        __new_finish = pointer();
        
        /* 把原来的 vector 中的数据拷贝到新 vector 的内存中来 */
        __new_finish = std::__uninitialized_move_if_noexcept_a(__old_start, __position.base(), __new_start, _M_get_Tp_allocator());
        ++__new_finish;
  		/* 重复调用一次针对的是中间插入元素的情况 */
        __new_finish = std::__uninitialized_move_if_noexcept_a(__position.base(), __old_finish, __new_finish, _M_get_Tp_allocator());
    }
    __catch(...)
    {
        if (!__new_finish)
            _Alloc_traits::destroy(this->_M_impl, __new_start + __elems_before);
        else
            std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
        
        _M_deallocate(__new_start, __len);
        __throw_exception_again;
    }
    
    /* 销毁原来的内存并给 _M_start、_M_finish 和 _M_end_of_storage 赋新值 */
    std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
    _M_deallocate(__old_start, this->_M_impl._M_end_of_storage - __old_start);
    this->_M_impl._M_start = __new_start;
    this->_M_impl._M_finish = __new_finish;
    this->_M_impl._M_end_of_storage = __new_start + __len;
}

size_type _M_check_len(size_type __n, const char* __s) const
{
	/* max_size() 为 vector 能获取的最大内存大小 */
    if (max_size() - size() < __n)
        __throw_length_error(__N(__s));

	/* __n 值为1，因此第一次长度增加1，往后每次长度翻倍 */
    const size_type __len = size() + (std::max)(size(), __n);
    
    return (__len < size() || __len > max_size()) ? max_size() : __len;
}

除了

push_back()

，还可以通过

emplace_back()

进行数据插入，其具体实现如下：

vector<_Tp, _Alloc>::emplace_back(_Args &&... __args) {
    if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) { // 未满载
        _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, std::forward<_Args>(__args)...);
        ++this->_M_impl._M_finish; // 增加 size
    } else { // 满载
        _M_realloc_insert(end(), std::forward<_Args>(__args)...);
    }
}

可以看出，二者实现的基本结构类似，但是

emplace_back()

中通过完美转发

std::forward<_Args>(__args)...

来对参数进行传递，从而实现了插入元素的原地构造，避免了在每次插入时创建临时对象。

二者在实际使用过程中的区别如下：

#include <iostream>
#include <utility>
#include <vector>

using namespace std;

class Car {
private:
    int m_id;
    string m_name;

public:
    Car(int id, string name) : m_id(id), m_name(std::move(name)) {
        cout << "Car(" << this->m_id << ", " << this->m_name << ")" << endl;
    }

    Car(Car &&other) noexcept: m_id(other.m_id), m_name(std::move(other.m_name)) {
        cout << "move Car(" << this->m_id << ", " << this->m_name << ")" << endl;
    }
};

int main(int argc, char *argv[]) {
    vector<Car> v;
    v.reserve(10);

    v.push_back(Car(1, "first"));
    cout << "---" << endl;
    v.emplace_back(2, "second");

    return 0;
}

atreus@MacBook-Pro % clang++ main.cpp -o main -std=c++11
atreus@MacBook-Pro % ./main                             
Car(1, first) // 构造临时对象
move Car(1, first) // 从临时对象向 vector 中拷贝（使用 emplace_back 时不会有此过程）
~Car(1) // 析构临时对象（使用 emplace_back 时不会有此过程）
---
Car(2, second) // 直接在 vector 末尾构造
atreus@MacBook-Pro % 

2.array

https://zh.cppreference.com/w/cpp/container/array

vector 功能比普通数组强大，但付出的代价是效率稍低，因此在需要

长度固定的数组

时，使用普通数组是更好的选择，但缺点是不那么方便和安全。C++11 新增了模板类 array，它也位于名称空间 std 中。

和普通数组一样，array 对象的长度也是固定的，无法动态扩展或收缩，使用栈（静态内存分配）而不是自由存储区，因此其效率与普通数组基本相同，但使用起来更方便，安全性也更好

。

3.deque

https://zh.cppreference.com/w/cpp/container/deque

deque 模板类表示

双端队列

，deque 允许在常数时间内对两端元素进行插入或删除操作，同时它没有 vector 中所谓的容量（capacity）概念，因为

它由分段的连续空间动态组合而成

，随时可以增加一段新的空间并链接起来。

具体来说，

deque 采用一块所谓的 map 作为

中控器

，这里所谓的 map 指的并不是 STL 中的 map 容器，而是一小块连续空间，其中每个元素（或者说节点）都是指针，指向另一段较大的连续线性空间，称为

缓冲区

，缓冲区才是 deque 的储存空间主体

。

deque 派生自 _Deque_base，_Deque_base 主要有以下四个成员：

_Map_pointer _M_map;
size_t _M_map_size;
iterator _M_start;
iterator _M_finish;

deque

支持随机访问

，但其迭代器的复杂度远高于 vector，因此除非需要双端队列数据结构，否则应尽可能使用 vector 而不是 deque。我们在对含有大量数据的 deque 进行排序时，最好是将数据先复制到 vector 中进行排序后再复制回 deque 以节省时间。

其迭代器主要包括以下四个成员：

_Elt_pointer _M_cur;   // 指向当前正在遍历的元素
_Elt_pointer _M_first; // 指向当前连续空间的首地址
_Elt_pointer _M_last;  // 指向当前连续空间的末尾地址
_Map_pointer _M_node;  // 一个二级指针，指向 map 数组中存储的指向当前连续空间的指针

deque 是连续空间（至少逻辑上看来如此），连续线性空间总令我们联想到 array 或 vector。但 array 无法成长，vector 虽可成长，却只能向尾端成长，而且其所谓成长也只是

寻找新空间、复制数据、释放原空间

的假象，这样的成长代价是相当高昂的。而 deque 则通过较为复杂的迭代器结构避免频繁的内存申请与释放，换取了更高的时间效率。

4.list

https://zh.cppreference.com/w/cpp/container/list

list 模板类表示

双向链表

，除首尾元素外的所有元素都与前后的元素相连接，这意味着可以双向遍历链表。list 和 vector 的关键区别在于，在 list 中任一位置进行插入和删除永远为常数时间，但很显然 list 不支持随机访问。此外，相较于 vector 的连续线性空间，list 每次插人或删除一个元素，就会配置或释放一个元素空间。因此 list 对于空间的利用绝对的精准，一点也不浪费。

list 所采用的的节点类型为 _List_node，其实现大致如下：

struct _List_node_base {
    _List_node_base* _M_next;
    _List_node_base* _M_prev;
};

template<typename _Tp>
struct _List_node : public _List_node_base {
    _Tp _M_data;
};

实际上，list 容器的底层实现为

双向循环链表

，采用循环链表的好处就是只需借助一个指针即可表示 list 容器的首尾元素。另外，为了更方便的实现 list 模板类提供的函数，该模板类在构建容器时，会刻意在容器链表中添加一个空白节点，作为该双向循环链表的

头节点

。

5.forward_list

https://zh.cppreference.com/w/cpp/container/forward_list

C++11 新增了容器类 forward_list，它实现了

单链表

，即每个节点都只链接到下一个节点，相比于 list，forward_list 更简单且更紧凑，但功能也更少。

二、关联式容器

1.set、multiset、unordered_set和unordered_multiset

https://zh.cppreference.com/w/cpp/container/set

set 表示

关联集合

，可反转可排序，且数值是唯一的，所以不能存储多个相同的值，但 multiset 允许数值重复。

2.map、multimap、unordered_map和unordered_multimap

https://zh.cppreference.com/w/cpp/container/map

map 是

有序键值对

容器，它里面的所有元素都是 pair，同时拥有实值（value）和键值（key），且 pair 的第一元素被视为键值，第二元素被视为实值。map 不允许两个元素拥有相同的键值，但 multimap 允许键值重复。

三、迭代器失效