本文将深入介绍标准库可用的容器，介绍了不同的容器（重点介绍std::vector）、它们的类别以及使用它们之间的权衡。

容器概述

标准库中的容器是泛型数据结构，特别适合保存数据集合。相较于使用传统C风格数组、编写链表和栈，使用标准库容器可以灵活改变其大小（除了array和bitset），能自动增长或收缩，以容纳更多或更少的元素，减少数据溢出和发生某些类型安全攻击的可能性。

标准库提供了16个容器，分为四大类：

• 顺序容器：动态数组vector、deque、list、forward_list和array。
• 关联容器：map，multimap，set，multiset。
• 无序关联容器/哈希表：unordered_map，unordered_multimap，unordered_set，unordered_multiset。
• 容器适配器：queue，priority_queue、stack。

此外，C++的string和流也可在某种程度上用作标准库容器，bitset可以用于存储固定数目的位。

对元素的要求

标准库容器对元素使用 值语义(Value Semanic)，在输入元素时保留元素的一份副本，通过赋值运算符给元素赋值，通过析构函数销毁元素。因此，编写要用于标准库的类时，一定要保证它们是可以复制的。请求容器中的元素时，会返回所存副本中的引用。

标准库容器的一个模板类型参数是分配器（allocator），标准库容器可使用分配器为元素分配或释放内存。例如vector中，有默认的分配器参数：

template<class T, class Allocator = std::allocator<T>> class vector;

某些容器（如map）也允许将比较器（Comparator）作为模板类型参数，其用于排序元素，也有默认值。例如map中，有默认比较器参数：

template<class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<const Key, T>>> class map;

标准库容器经常移动或复制元素，因此 确保容器中存储的对象类型支持移动语义。或至少让拷贝构造函数和拷贝复制运算符尽可能高效。

异常和错误检查

标准库容器提供非常有限的错误检查功能，使用它时应确保正确性。然而，一些容器方法和函数会在特定条件下抛出异常。

顺序容器

顺序容器（Sequence Container），存储一个元素序列，每个元素都有固定的位置，取决于插入时间和地点，和元素值无关。

这里详细介绍一下vector，然后简要介绍其他容器，因为和vector是类似的。

vector

将元素置于一个动态数组中，可以随机存取元素（用索引直接存取）。在vector的尾部添加或删除元素十分迅速，但在中部或头部就比较费时。

vector概览

固定长度的vector

使用vector的最简单方式就是把它当作定长数组来用。可以通过[ ]来访问vector中的元素，但 不推荐这样做，因为还有更好的.at()，它会在数组越界的时候抛出out_of_range异常，方便我们处理。而[ ]只是assert，脱离debug环境就会有隐患。

std::vector<int> ivec{1, 2, 3};
// ok
std::cout << ivec.at(1) << std::endl;
// out_of_range 异常
std::cout << ivec.at(114514);

除此之外，还有返回第一个元素引用的.front()和返回最后一个元素引用的.back()。注意，在空的容器上调用这两个函数会引发未定义的行为（Undefined Behavior）。

动态长度的vector

vector的真正强大之处在于动态增长的能力。可以使用.push_back()和.pop_back()来快速地从尾部添加/删除元素；也能用.insert()来较慢地从前面/中间插入元素，它会返回一个指向新添加元素的迭代器。

vector详解

构造函数

默认构造函数会创建一个不包含元素的vector：

// 函数原型
vector(const std::allocator<T>& al);
// 使用
std::vector<int> iVec;

其中，allocator内存分配器是默认参数。

移动构造函数，可以手动指定分配器：

// 函数原型
vector(std::vector<T>&& right, const std::allocator<T>& al);
// 使用
std::vector<int> ivec{ 1, 2, 3, 4 };
std::vector<int> ivec1(std::move(ivec));

复制构造函数，可以手动指定分配器：

// 函数原型
vector(const std::vector<T>& vec, const std::allocator<T>& al);
// 使用
std::vector<int> ivec{ 1, 2, 3, 4 };
std::vector<int> ivec1(ivec);

初始化列表initializer_list也能给vector初始化：

// 函数原型
vector(std::initializer_list<T> initList, const std::allocator<T>& al);
// 使用
std::vector<int> ivec{ 1, 2, 3, 4 };

也能手动指定元素个数和这些元素的值：

// 函数原型
vector(const size_t count, const T& t);
// 使用: 创建10个值为100的元素
std::vector<int> ivec(10, 100);

如果没有提供默认值，就会对所有元素进行 0初始化：

// 函数原型
vector(const size_t count, const std::allocator<T>& al);
// 使用: 创建10个值为0的元素
std::vector<int> ivec(10);

当然，也能用迭代器（deque，list等的迭代器都能）来进行初始化：

// 函数原型
vector(iter first, iter last, const std::allocator<T>& al);
// 使用
std::set<int> iset{ 1, 1, 2, 3 };
std::vector<int> ivec1(iset.begin(), iset.end());

复制与赋值

除了上边提到的构造函数外，vector还提供了.assign()方法和.swap()方法来让我们对它灵活赋值。

.assign()方法会删除当前vector中的所有元素，并添加任意数目的新元素，适合用于vector的重用。

// 填充5个值为100的元素
ivec.assign(5, 100);
// 接收initializer_list
ivec.assign({1, 2, 3});

.swap()方法会交换两个vector的内容，且时间复杂度为\(O(1)\)，效率很高：

vec1.swap(vec2);

迭代器操作

可以通过.(c)begin()和.(c)end()返回指向第一个元素和最后一个元素的后一个元素的(const)迭代器。也能通过.(c)rbegin()和.(c)rend()返回指向第一个元素的前一个元素和最后一个元素的(const) 反向迭代器。

auto iter = ivec.begin();

const_iterator，对const对象调用.begin()，.end()或直接调用.cbegin()，.cend()得到的迭代器。是只读的，不能修改它引用的元素。

iterator可以被转换为const_iterator，但后者不能转换为前者。

如果不需要修改迭代器中的元素，建议使用const_iterator，除了更安全，编译器对它也有特定的优化。

获取到迭代器后，就能通过解引用运算符*获取它所引用的元素，也能直接通过->访问对象成员/调用对象方法（如果它引用的元素是个对象）。

std::cout << *iter << std::endl;
iter->doSth();

vector迭代器是随机访问的，可以通过++iter等方式移动迭代器，这样也带来了一些越界等问题的安全隐患。

PS：也能通过std::begin()等函数获取迭代器。

添加和删除元素

再对.insert()方法进行一下补充，它在迭代器指定位置处添加1个或多个元素，并将所有后续元素向后移动，给新元素腾出空间，因此比较耗时。并且，.insert()还会 返回指向新添加首个元素位置的迭代器。.insert()一共有5种不同的重载形式：

• 插入单个元素
• 插入单个元素的n份副本
• 从某个迭代器范围插入元素，区间前闭后开。
• 以移动语义方式插入一个元素
• 通过initializer_list添加一系列元素

ivec.insert(ivec.begin() + 3, ivec2.begin(), ivec3.end());

相对的，.erase()可在vector的任意位置删除元素；.clear()可以删除所有元素，然后 返回指向被删除元素后一个元素位置的迭代器。.erase()有两种重载，一种是接收单个迭代器，删除单个元素；另一种是接收两个迭代器，删除指定范围的元素（区间前闭后开）。

ivec.erase(ivec.begin() + 1, ivec.end() - 1);

在C++20中，引入std::erase()和std::erase_if()两个函数，它支持删除所有满足条件的元素。前者需要输入满足条件的值，后者需要输入满足条件的可调用对象（函数指针、函数对象、lambda表达式等）。

// 删除所有 < 2 的元素
std::erase_if(ivec1, [](int i){ return i < 2; });

内存管理

在谈vector的内存管理前，先康康vector内存相关信息是如何获得的：

• .size()可以查看当前vector里有几个元素。也能用std::size()查看（类型为size_t）。在C++20中，能用std::ssize()查看（类型为long long），两者区分靠类型是否为有符号。
• .capacity()可以查看当前vector最多能存储几个元素（超过就要进行内存重分配）。
• .empty()可以判断当前容器是否为空，vector可以为空，但容量不能是0。也能用std::empty()判断。
• 如果想获得数据的指针，可以通过.data()或std::data()来获取。在比较旧的代码中可能会看见诸如&vec[0]的形式，这样的写法是不安全的。

vector会自动分配内存来保存插入的元素。由于不可能请求在当前vector的尾部添加内存，每次vector扩容时都一定会在另一个位置分配一块新的更大的内存块（通常是capacity的2倍或1.5倍），然后将所有元素复制/移动到新的内存块，十分耗时。

vector的内存重分配除了影响效率外，还会使引用vector元素的所有迭代器失效。如果不注意的话会有安全隐患。尽量避免内存重分配的方法如下：

• 可以通过.reserve()预分配vector要保存几个元素，如果超过了才进行内存重分配，节省时间。
• 使用.resize()和.assign()指定保存几个元素。

如果当前的vector生命周期很长，它一直在内存重分配，却无法释放内存，就得需要一个使用临时变量来释放内存的小技巧：

std::vector<int> longLife;
// ......
vector<int>().swap(longLife);

将这个vector与临时创建的空vector进行交换，原来的内存现在全给这个新的临时变量了，而临时变量很快就会被销毁。

vector<bool>特化

C++标准要求对vector<bool>进行特化，目的是通过”打包“布尔值的方式来优化空间分配，因为布尔值可以用一个位来表示。因此，vector<bool>不是普通的vector。

空间虽然优化了，但读取效率却反而慢了。因此建议使用bitset而不是这个，如果确实需要动态大小的位字段，可以用vector<std::int_fast8_t>或vector<unsigned char>。

deque

双端队列（double end queue），几乎和vector等同，本质是优化过的动态数组。它与vector的区分如下：

• 不要求元素保存在连续内存中
• 首尾都能快速添加/删除元素了（.push_front()，.pop_front()），但略慢于vector。
• 在首尾插入元素时，它不会使迭代器失效。
• 没有.reserve()和.capacity()。

list

双向链表，不能随机存取元素，在任何位置插入/删除元素都比较迅速（头部操作慢于deque，尾部操作慢于deque和vector）。

访问元素

只有.front()和.back()，访问其他元素只能通过迭代器。

迭代器

list的迭代器是双向的，不像vector的迭代器那样提供随机访问，只能有++p，--p这样的遍历操作。

内存管理

和deque一样，list不暴露底层的内存模型。它支持.size()，.empty()和.resize()，但不支持.reserve()和.capacity()。

特殊操作

串联

可以在一个list的任意位置串联（splice）或插入另一个list:

listA.splice(it, listB);

注意：在串联操作后，listB中的元素会被删除。

一些算法

forward_list

是单链表，是受限的list:

• 只支持前向迭代。.before_begin()提供指向”假想头节点“的迭代器，但它后边就是.begin()所指向的内容。
• 没有.size()，因为C++标准要求它最小化内存使用。
• 没有指向最末元素的锚点，因此没有.back()等方法。

array

和vector类似，但 array的大小是固定的，更像C风格数组了。这个类的目的是让array能分配在栈上，而不是像vector那样总要访问自由存储区。

array也支持随机访问迭代器，元素存在连续内存中。

声明array需要两个模板参数，指定元素类型和元素数量：

std::array<int, 3> arr{1, 2, 3};

除了用迭代器和[ ]来获取数组元素外，还能通过std::get<>()来获取，使用它的好处是可以通过编译期检查提前发现索引是否有效：

int i = std::get<1>(arr);

在C++20中，std::to_array()可以将给定的C风格 一维数组 转换为std::array。

auto arr1 = std::to_array({11, 22, 33});

span

C++20提供了查看 vector，array和C风格数组等数据序列的统一视图 span<T>。就像string_view对于string那样，span的复制成本很低，只有一个指向序列第一个元素的指针和序列元素的数量，因此它是可以对底层元素进行修改的（而string_view是只读的）。

以下是一个使用span的例子，包含如何构造视图，利用subspan()创建子视图等：

// 这里用const int防止数据被修改
void print(span<const int> values)
{
	for (const auto& value : values)
	{
		cout << value << " ";
	}
	cout << endl;
}

int main()
{
    // vector
	vector<int> iVec{ 1, 2, 3, 4, 5 };
	print(iVec);						// 隐式转换
    print({v.data() + 1, 3});			// 地址+元素个数
    
    // 显式创建span
    span mySpan{ iVec };
	print(mySpan);
	// 创建子视图(偏移量, 元素个数)
	print(mySpan.subspan(2, 3));
    
    // array
	array<int, 5> arr{ 1, 2, 3, 4, 5 };
	print(arr);

	// C风格数组
	int carr[]{ 1, 2, 3, 4 };
	print(carr);    
}

有序关联容器

关联容器（associated container），元素位置取决于元素的值，和插入顺序无关。

set/multiset

使用”红黑树“实现，二叉树的本质决定了set/multiset的元素存取值取决于元素本身的值，和插入顺序无关。内部元素的值根据元素的值自动排列，与插入顺序无关。set内部相同数值的元素仅能出现一次，而multiset内部相同数值的元素可出现多次。

std::set<int> myset{1, 2, 3, 3};

for (auto& elem : myset)
{
	std::cout << elem << std::endl;
}

map/multimap

使用”红黑树“实现，内部元素是成对的<key, map>，内部元素根据键值进行排序。map内部相同的键值只能出现一次，而multimap则可以出现多次。

std::map<int, std::string> mymap;
mymap.insert(std::make_pair(10, "second"));
mymap.insert(std::pair<int, std::string>(1, "first"));

for (auto& elem : mymap)
{
	std::cout << elem.first << " -> " << elem.second << std::endl;
}

无序关联容器

unordered_map/unordered_multimap

使用”哈希表”实现，实现了真正的无序，和map/multimap类似。

unordered_set/unordered_multiset

使用“哈希表”实现，和set/multiset类似。

容器的选择

有序关联容器和无序关联容器的对比

• 关联式容器都是有序的，对那些对顺序有要求的操作，效率会高很多。（例如增加元素，删除元素）
• 无序容器都是真正的无序，在查找数据方面有优势。（比如查找元素，修改特定元素）
• 从内存消耗角度来说，无序容器要高于有序容器。

总的来说，增加/删除元素频繁就选有序关联容器；查找/修改频繁就用无序关联容器。

根据处理数据不同选择不同的容器

1. 需要使用存储键值对的容器时，用map类，然后根据操作种类的频繁性选择有序/无序容器
2. 处理普通元素：
   1. 元素需要频繁插入删除，选择顺序容器
      1. 尾部插入删除，vector
      2. 头部，尾部插入删除，deque
      3. 中间插入、删除，list
   2. 元素需要频繁查找，用set类
      1. 频繁增加、删除，set
      2. 频繁查找，修改，unordered_set

大型项目中，需要对各种容器进行测试；普通练习中，常用vector或set。

容器适配器

详见Part5的适配器与分配器这一篇文章。

参考资料

• 飘零的落花 - 现代C++详解
• C++20高级编程