Intro

集合提供了一种存储数据的方法。C++ 标准库（STL）提供了许多不同种类的集合，因此了解何时使用哪些集合是非常要的。这篇文章里将讨论 C++ 中常用的集合。

Big-O 表示法

Big-O 表示法用于描述一个算法的运行时间和占用空间随着问题规模的扩展而相应扩展的速率，这个速率分别被称为时间复杂度和空间复杂度。

接下来我们主要讨论时间复杂度，空间复杂度与它的情况类似。

下表列出了最常见的从最快到最慢的时间复杂度。具有指数或更慢的时间复杂度的算法太慢，一般不会使用。

下表列出了常见的搜索和排序算法的时间复杂度和空间复杂度：

有时候，对于特定规模的问题，具有更差的时间复杂度的算法可能表现得更好。例如，快速排序算法的平均时间复杂度为 $O(n \log n)$，而插入排序算法的时间复杂度为 $O(n^2)$。但是，对于小问题集来说（如集合中元素的个数小于 20），插入排序算法会比快速排序算法具有更快的执行时间，因为插入排序不使用递归算法。因此，需要根据实际情况选择合适的算法。

向量

向量是一个动态数组，它可以根据集合中的元素个数自动调整数组大小。如果想要把元素插入向量，可以使用 push_back 或 emplace_back 成员函数。这两个函数可以在向量的末端添加一个元素。对于非空向量，我们可以使用数组下标表示法来访问向量中的特定元素。例如，下面的代码声明了一个元素类型为浮点数的向量，然后在向量的末尾处添加了三个元素，最后在终端输出向量中的第三个元素：

1
2
3
4
5
6

// #include <vector> to use std::vector
std::vector<float> vectorOfFloats;
vectorOfFloats.push_back(5.0f); // Contents: { 5.0f }
vectorOfFloats.push_back(7.5f); // Contents: { 5.0f, 7.5f }
vectorOfFloats.push_back(10.0f); // Contents: { 5.0f, 7.5f, 10.0f }
std::cout << "vectorOfFloats[2] = " << vectorOfFloats[2] << std::endl;

从长远来看，往向量后端插入元素的算法的平均时间复杂度为 $O(1)$。但是，因为向量存在于一个连续的内存块中，所以往向量中的任意一个位置插入元素的算法的平均时间复杂度为 $O(n)$。基于上述原因，程序员应该避免随意向向量中插入元素。向量的连续内存分布带来的优点是访问索引处的元素的时间复杂度为 $O(1)$。

链表

链表可以把集合中的每个元素存储在内存中的任意位置中，并使用指针把它们链接在一起。我们可以通过 push_front 或 emplace_front 函数向链表的前端插入元素，通过 push_back 或 emplace_back 函数向链表的末端插入元素。以下代码段创建了一个元素类型为整数的链表，并插入了一些整数元素：

1
2
3
4
5
6
7

// #include <list> to use std::list
std::list<int> intList;
intList.push_back(4);
intList.push_back(6);
intList.push_back(8);
intList.push_back(10);
intList.push_front(2);

下图展示了所有插入操作完成后的 intList 链表。链表的优点是向链表的任意一端插入元素的时间复杂度都是 $O(1)$，缺点是访问链表的第 $n$ 个元素的时间复杂度是 $O(n)$。

  
flowchart LR
	id1[[2]] --> id2[[4]]
	id2 --> id3[[6]]
	id3 --> id4[[8]]
	id4 --> id5[[10]]
	id5 --> id4
	id4 --> id3
	id3 --> id2
	id2 --> id1

  

队列

队列的特点是先进先出（FIFO）。std::queue 的队列实现使用 push 函数或 emplace 函数进行插入操作，使用 pop 函数进行删除操作，通过 front 函数访问队列前端的元素。

示例代码如下：

1
2
3
4
5
6
7
8
9
10

// #include <queue> to use std::queue
std::queue<int> intQueque;
intQueue.push(10);
intQueue.push(20);
intQueue.push(30);
for(int i = 0; i < 3; i++)
{
    std::cout << intQueue.front() << ' ';
    intQueue.pop();
} // output: 10 20 30

std::queue 的队列实现保证了插入、访问和删除操作的时间复杂度为 $O(1)$。

栈

栈的特点是后进后出（LIFO）。std::stack 的实现使用 push 函数或 emplace 函数进行插入操作，使用 pop 函数进行删除操作，通过 top 函数访问“栈顶”的元素。

示例代码如下：

1
2
3
4
5
6
7
8
9
10

// #include <stack> to use std::stack
std::stack<int> intStack;
intStack.push(10);
intStack.push(20);
intStack.push(30);
for(int i = 0; i < 3; i++)
{
    std::cout << intStack.top() << ' ';
    intStack.pop();
} // output: 30 20 10

std::stack 的实现保证了插入、访问和删除操作的时间复杂度为 $O(1)$。

映射

映射是按键排序的键值对 {key : value} 集合。映射中的每一个键都是唯一的。

示例代码如下：

1
2
3
4
5
6

// #include <map> to use std::map
std::map<int, std::string> months;
months.insert(pair<int, std::string>(1, "January"));
months[2] = "February";
months.emplace(3, "March");
std::cout << months[2];  // output: February

只有在键存在的时候，才可以使用上面的访问元素的代码。可以通过 find 函数来确认键是否存在，如果存在，函数会返回元素的迭代器。

std::map 内部的实现使用的是平衡二叉搜索树。这意味着它可以在 $O(\log n)$ 的时间复杂度内根据键找到对应的元素。向映射中插入或删除元素的时间复杂度也是 $O(\log n)$。此外，这也导致循环映射中的内容是按键的升序排列的。

散列映射

散列映射是无序的映射，它的插入、删除和搜索操作的时间复杂度都是 $O(1)$。因此，在需要映射但不需要排序的情况下使用散列映射性能会优于普通映射。

std::unordered_map 与 std::map 有着相同的功能和函数。要使用散列映射需要添加 #include <unordered_map>。

迭代器、Auto 和基于范围的 For 循环

为了遍历向量中的元素，可以使用遍历数组的方法。但是 C++ 语言标准库中的许多集合不支持这种语法，例如 list 和 map。为了遍历这些集合中的元素，我们需要使用迭代器。STL 中的集合都支持迭代器。STL 中的集合都有一个 begin() 函数和一个 end() 函数，分别用来返回指向集合中第一个元素和最后一个元素的迭代器。迭代器的类型是集合的类型后面再跟上 ::iterator。例如，下面的代码会创建一个列表，然后使用迭代器遍历列表中的元素。

1
2
3
4
5
6
7

std::list<int> numbers;
numbers.emplace_back(2);
numbers.emplace_back(4);
numbers.emplace_back(6);
for(std::list<int>::iterator iter = numbers.begin(); iter != numbers.end(); iter++) {
    std::out << *iter << std::endl;
}

需要注意的是，迭代器使用 * 进行间接引用，与指针间接引用的方式相同。使用迭代器遍历其它集合的方法与上面的例子类似。

映射的迭代器指向的是 std::pair。因此，给定映射中元素的迭代器，需要分别使用 first 和 second 来访问迭代器指向的元素的键和值。回到之前的映射例子中，可用下面的方法获得元素的迭代器并输出数据：

1
2
3
4
5
6
7

// Get an iterator to the element with the key 2
std::map<int, std::string>::iterator iter = months.find(2);
if(iter != months.end()) // This is true if found
{
    std::cout << iter->first << std::endl; // Outputs 2
    std::cout << iter->second << std::endl; // Outputs February
}

因为迭代器的类型名称过于冗长，C++ 11 提供了 auto 关键字来帮助人们减少这种痛苦，它可以告诉编译器根据指定的值来推导出迭代器变量的类型。使用 auto 虽然可能会导致代码可读性变差，但不会导致程序产生性能损失。

利用 auto 重写遍历代码如下：

1
2
3
4

// auto is deduced to be std::list<int>::iterator
for(auto iter = numbers.begin(); iter != numbers.end(); iter++) {
    std::out << *iter << std::endl;
}

然而，即便是用了 auto，使用迭代器来遍历集合中的元素也显得代码过于笨重，因此许多其它编程语言提供了 for each 的构造，C++ 11 中有一个类似的结构，被称为基于范围的 for 循环。它的语法如下：

1
2
3

for(int i : numbers) {
    std::cout << i << std::endl;
}

上面的语法在进行遍历的时候会对每个元素进行复制。如果要修改集合中的元素，可以通过 & 进行引用传递。也可以使用 const 来避免对元素的复制和修改。

这里也可以使用 auto 作为类型，并可以同 const 和 & 一起使用。

基于范围的 for 循环的一个缺点是，在遍历过程中，程序员无法添加或删除集合中的元素。

References

1. Time Complexity Of Algorithms