C++容器之顺序容器

容器是一种特定类型对象的集合，顺序容器则为程序员提供了存放元素的能力，且这种容器不受元素的值影响，元素的位置只受元素加入容器时的位置。

还有关联容器和无序容器，我们会在未来介绍。

概述

常用容器

以下是C++常用的顺序容器：

容器	描述	主要特点
std::vector	动态数组，支持随机访问。	- 动态调整大小 - 支持快速随机访问 - 在末尾插入和删除操作效率高
std::deque	双端队列，支持在两端进行插入和删除操作。	- 动态调整大小 - 支持随机访问 - 在两端插入和删除操作效率高
std::list	双向链表，允许在中间高效插入和删除元素。	- 动态调整大小 - 不支持随机访问 - 在任意位置插入和删除操作效率高
std::forward_list	单向链表，允许在中间高效插入和删除元素。	- 动态调整大小 - 不支持随机访问 - 在任意位置插入和删除操作效率高，内存使用更少
std::array	固定大小数组，大小在编译时确定。	- 固定大小 - 支持快速随机访问 - 无法动态调整大小

string也算是顺序容器，未来会单独讲。

如此多种类的顺序容器，我们应该在何时使用哪一种容器呢？基本遵循以下规则：

• 不知道选什么，选vector就对了；
• 要求随机访问元素，选vector或deque；
• 需要在容器中间插入或删除元素，选list或forward_list；
• 既要在中间插入元素，又要随机访问：
  • 确定一下，中间插入元素有必要吗？咱们实在不行，先全都插在尾部，最后sort一下？
  • 先用list创建，待所有元素归位后转换成vector;

容器的基本操作

以下介绍的操作对所有容器都生效（可能有极少数情况），这里的容器指的是顺序容器、关联容器和无序容器。

类型别名

• iterator：此容器的迭代器；
• const_iterator：此容器的迭代器，只读元素；
• size_type：无符号整数类型，保存容器大小；
• difference_type：带符号整数类型，保存两个迭代器之间的距离；
• value_type：元素的类型；
• reference：元素的左值类型，等价于value_type&；
• const_reference：元素的const左值类型；

用法如下：

vector<int> nums{ 1, 2, 3, 4, 5, 6 };
vector<int>::iterator ibegin= nums.begin();	// 第一个元素的迭代器
vector<int>::const_iterator cibegin = nums.cbegin();	// 第一个元素的常量迭代器

cout << *ibegin << " " << *cibegin << endl;	// 1 1

vector<int>::size_type size = nums.size();	// 元素大小
vector<int>::difference_type end2begin = nums.end() - nums.begin();	// 元素从头到尾的距离

cout << size << " " << end2begin << endl;	// 6 6

vector<int>::value_type elem = *(nums.begin() + 2);	// 第三个元素的拷贝
vector<int>::reference relem = *(nums.begin() + 2);	// 第三个元素的引用
vector<int>::const_reference crelem = *(nums.begin() + 2);	// 第三个元素的常量引用

cout << elem << " " << relem << " " << crelem << endl;	// 3 3 3

以上的用法任一一个容器都能使用。

构造函数

• C c：调用默认构造函数，对于array则为构造空容器；
• C c1(c2)或C c1 = c2：创建c2的拷贝；
• C c(b, e)：将迭代器b到e之间的元素拷贝到c，array不支持。
• C c{a, b, c,...}或C c = {a, b, c,...}：使用列表初始化c。
• C seq(n)，创建了一个容器seq，其中有n个元素，每个元素进行了值初始化，如果是对象，要求该类有默认构造函数。
• C seq(n, t)，创建了一个容器seq，其中有n个为t的元素。

赋值，swap

• c1 = c2：替换元素；
• c1 = {a, b, c,...}：替换为列表中的元素，array不支持；
• a.swap(b)：交换a和b的元素；
• swap(a, b)：同上。

添加/删除元素（array不支持, 不同容器接口有所差别）

• c.insert(args)：将args指定的元素拷贝进c；
• c.emplace(inits)：在c中使用inits的初始化一个元素；
• c.erase(args)：在c中删除args指定的元素；
• c.clear()：清空c的所有元素；

迭代器相关

• c.begin(), c.end()：返回c的首元素和尾元素之后的迭代器；
• c.cbegin(), c.cend()：返回c的首元素和尾元素之后的const迭代器；
• c.rbegin(), c.rend()：返回c的尾元素和首元素之前的反向迭代器；
• c.crbegin(), c.crend()：返回c的尾元素和首元素之前的const反向迭代器；
• reverse_iterator：反向迭代器；
• const_reverse_iterator：const类型的反向迭代器；

容器大小操作

• c.size()：返回容器的元素个数，forward_list不适用；
• c.empty()：当元素个数为空时返回true，否则为false；
• 关系运算符，相同类型容器相比较。

下面就来详细讲解这些的用法。

迭代器

有的人可能会想，迭代器可以用*访问其元素，也可以进行递增和递减操作，所以可不可以认为迭代器是一种指针呢？

答案很显然不是，迭代器与指针的相似之处也仅限于上面两种情况，迭代器还有更加高级的用法和功能。以下的一个小实验可以证明迭代器的功能更强大。

我们知道list的元素在内存空间中并不是相连的，如果用指针以此访问，不能使用递增操作，但是list的迭代器就不能一样了：

list<int> l{ 1, 2, 3, 4 };
list<int>::iterator begin = l.begin();
while (begin != l.end())
{
	cout << *begin << " ";    // 输出 1 2 3 4
	++begin;
}

即使不是连续空间，迭代器依然可以通过递增操作遍历整个链表。并且迭代器还支持不同类型，例如反向迭代器。迭代器也可以知道自己是属于那种容器类型的迭代器。

迭代器范围

在 C++ 中，迭代器范围是指一对迭代器，通常表示一个容器或子容器中的一系列元素。这个范围由两个迭代器定义：一个指向范围的起始位置（通常称为 begin 迭代器），另一个指向范围的结束位置（通常称为 end 迭代器）。end 迭代器不指向范围内的元素，而是指向范围的一个位置之后。

begin迭代器能够通过递增操作在某个时刻变成end，因此我们可以假定：

while (begin != end)
{
	// 一些操作
	++begin;
}

上述这种情况始终成立。

begin和end符合要求需要程序员自觉遵守。

大多数容器提供了begin和end的成员，这两个迭代器常用的用途就是形成一个包含容器中所有元素的迭代器。

在C++11中，引入了c开头的cbegin和cend，用以支持auto来推断变量类型。c开头的迭代器返回的是const_iterator类型。

容器中关系运算符

比较两个容器，实际上是容器中每个元素依次进行比较。有以下规则：

假设有两个容器 a 和 b，它们的类型相同，并且包含的元素类型也支持相应的关系运算符。

运算符	比较规则
==	a == b 当且仅当 a 和 b 的大小相同，并且每个对应位置的元素都相等，即 a[i] == b[i] 对所有 i 成立。
!=	a != b 当且仅当 a == b 不成立。
<	a < b 当且仅当 a 在字典序列上小于 b，即找到第一个不同的元素 a[i] 和 b[i]，使得 a[i] < b[i]，或者 a 是 b 的前缀并且 a 的大小小于 b。
<=	a <= b 当且仅当 a < b 或 a == b。
>	a > b 当且仅当 b < a。
>=	a >= b 当且仅当 b <= a。

三个vector<int>，a、b和c，分别为：a = {1, 2, 3}，b = {1, 2, 3, 4}，c = {1, 2, 3, 5}，尝试用关系运算符表示三者的关系。

操作顺序容器

之前我们讲到的容器操作对于大部分容器都适用，也有一些只适用与顺序容器的操作：

添加元素

array不支持改变容器的大小，所以以下的操作array均不支持。

• c.push_back(t)：在容器后面插入一个元素。
• c.emplace_back(args)：在容器后面原地构造一个元素。
• c.push_front(t)：在容器前面插入一个元素，vector不支持。
• c.emplace_front(args)：在容器前面原地构造一个元素，vector不支持。
• c.insert(p, t)：在迭代器p之前插入元素t；
• c.emplace(p, args)：在迭代器p之前构造一个由args构造的元素。
• c.insert(p, args)：在p之前插入数个元素，arg为容器构造函数的参数列表。

连续空间的容器在中间插入元素会导致迭代器，引用指针失效其性能也很差。

使用push_back()和push_front()

单端容器只支持push_back()，例如vector,string。双端容器两者都支持，例如list、deque。

deque<int> dq{ 1, 2, 3 };
dq.push_back(4);	// 1, 2, 3, 4
dq.push_front(0);	// 0, 1, 2, 3, 4

vector<int> vc{ 1, 2, 3 };
vc.push_back(4);	// 1, 2, 3, 4
// vc.push_front(0)	// 不支持

使用insert()

insert()除了可以添加一个元素外，还可以使用类似填入构造函数参数的形式插入多个元素，必须要传入一个迭代器，并在迭代器前面插入这些元素，其返回值为插入第一个元素的迭代器。

vector<int> vc{ 1, 2, 3 };
vc.insert(--vc.end(), 4);	// 1, 2, 4, 3
vc.insert(--vc.end(), 2, 7);	// 插入2个7（构造函数类似）, 1, 2, 4, 7, 7, 3
//vc.insert(vc.end(), vc.begin(), vc.end()) 插入范围不能是目标容器

list<int> l{ 10, 11, 12 };
vc.insert(--vc.end(), l.begin(), l.end());	// 插入迭代器范围（构造函数类似），1, 2, 4, 7, 7, 10, 11, 12, 3

// vector没有push_front，可以用insert近似代替
list<int>::const_iterator il = l.begin();
vector<int>::iterator iter = vc.begin();
while (il != l.end())
{
	iter = vc.insert(iter, *il);	// 每次在头部添加元素，最终结果 12, 11, 10, 1, 2, 4, 7, 7, 10, 11, 12, 3
	++il;
}

使用insert()需要注意以下几点：

• 在连续空间容器中插入元素是合法的，但性能很差，因为需要移动很多元素，再插入。链表类型没有这个问题。
• 如果使用迭代器范围插入元素，其范围不属于目标类型，否则会运行时报错，这是程序员不想见到的。
• 返回值是插入元素第一个的迭代器。
• 元素插入插入的是拷贝，不是元素本身。

使用emplace()

C++11引入了新的操作emplace、emplace_back和emplace_front，这些操作是直接构造而不是拷贝元素，一定程度上提升了性能。这三个操作分别对应了insert、push_back和push_front。其参数为构造函数的参数，如果有默认构造函数，可以不填参数。

vector<vector<int>> matrix;
matrix.emplace_back(3);	// 第一个元素为{0, 0, 0}
matrix[0] = { 1, 2, 3 };	// 重新赋值
matrix.emplace_back(matrix[0].crbegin(), matrix[0].crend());	// 第二个元素为{3, 2, 1}
matrix.emplace(--matrix.end(), 3, 10);	// 插入一个元素{10 ,10, 10}

访问元素

访问容器内元素的方法有以下几种：

• 下标访问：使用[2]为访问容器第三个元素。链表不支持随机访问。
• c.at(index)：更安全的下标访问，编译器会检查是否超出访问范围。
• c.front()，返回容器第一个元素的引用。
• c.back()，返回容器最后一个元素的引用。

array<int, 5> c{ 1, 2, 3, 4, 5 };
//cout << c.at(5) << endl;	// 编译时会报错out_of_range
cout << c.at(3) << " " << c[3] << endl;	// 4 4
cout << c.front() << " " << c.back() << endl;	// 1 5

删除元素

删除元素改变了容器的大小，array不支持以下操作。

• c.pop_back()：删除最后一个元素；
• c.pop_front()：删除第一个元素；
• c.erase(p)：删除迭代器p指向的元素;
• c.erase(b, e)：删除迭代器范围的元素；
• c.clear()：删除c的所有元素；

forward_list不支持pop_back()，且有特殊版本的erase()，vector不支持pop_front。

使用这些操作需要注意一下几点：

• pop_back()和pop_front()的返回值是void。
• erase()返回的是删除元素后面的一个元素的迭代器位置。

可以用下面的程序来删除一个表中所有的奇数元素：

auto iter = c.begin();
while (iter != c.end())
{
	if (*iter % 2 == 1)
	{
		iter = c.erase(iter);
	}
	else
	{
		++iter;
	}
}

改变容器的大小

• c.resize(n)，将容器的大小改为n，变大则进行值初始化，变小则丢弃元素。
• c.resize(n ,t)，将容器的大小改为n，如果需要添加元素，则将元素赋值为t

常用顺序容器介绍

vector

vector是可变且连续空间，这种操作不好满足。我们可以试着编写一个程序，看看vector是如何增长的。

• c.shrink_to_fit()：将capacity()减少到size()的大小。
• c.capacity()：查看容器的容量，超出容量则会扩容，capacity()会改变。
• c.reserve(n)：分配至少能容纳n个元素的内存空间。

vector<int> c;
for (int i = 0; i < 23; ++i)
{
	c.push_back(i);
	cout << "size: " << c.size() << ", capacity:" << c.capacity() << endl;
}

不同的编译器扩容的方式不同，但是只有一个原则，如何占用尽可能少的空间，添加元素时性能还更快。

看看你的环境vector扩容策略吧。

改变vector的容器可能会使迭代器失效，其规则如下：

• vector的内存被重新分配，例如扩容操作，会使其元素的迭代器，指针和引用全部失效。
• vector插入元素，但是内存没有重新分配，插入元素及之后的元素迭代器，指针和引用全部失效。
• vector删除元素，被删元素之后的迭代器，指针和引用无效。

deque

deque的访问效率不如vector，deque 使用一系列固定大小的内存块（或称为“缓冲区”）来存储元素。这些块在内存中不一定是连续的。虽然 deque 也支持随机访问，但由于其分段存储的结构，访问任意位置的元素需要先确定该元素所在的块，然后在块内进行访问。这增加了额外的计算和指针间接访问的开销。

deque衍生出两个容器适配器stack和queue，这会在之后介绍。

改变deque容器可能会使迭代器失效：

• 首尾之外插入和删除会使所有元素的迭代器，指针和引用都会失效。
• 在首尾位置添加元素会使迭代器失效，但指针和引用不会失效。
• 在首尾位置删除元素指向被删除元素的迭代器，指针和引用失效，其他不会。

list

list不支持随机访问，但是具有高效的增删性能。

forward_list

forward_list的迭代器只能递增，不能递减（不能寻找前驱）。并且没有size()成员。

forward_list本质上是一个单项链表，有些操作不适合单向链表，例如c.erase(p)，想要删除p指向的元素，首先要找到p之前的迭代器，将下一个迭代器指向p之后的元素。根据数据结构的知识，单向链表找前驱需要从头进行遍历，性能将大打折扣。在很多情况下，forward_list都有专属于自己的版本来增删元素。

• lst.before_begin()：返回首前迭代器，不能被解引用。
• lst.before_begin()：返回常量首前迭代器，不能被解引用。
• lst.insert_after(p, t)：在p之后插入元素为t。
• lst.insert_after(p, args)：在p之后插入一些元素，返回插入最后一个元素的迭代器。
• lst.emplace_after(p, args)：在p之后构造一个元素。
• lst.erase_after(p)：删除p之后的一个元素。
• lst.erase_after(b, e)：删除(b, e]之间的元素，删除e之后的迭代器。

forward_list<int> lst{ 1, 2, 3, 4 };
lst.insert_after(lst.before_begin(), 5);	// {5, 1, 2, 3, 4}
auto iter = lst.insert_after(lst.begin(), 6);	// {5, 6, 1, 2, 3, 4}
//lst.insert_after(lst.end(), 5);	// 未定义的行为，end是尾后迭代器，在尾后迭代器后面插入数据无效。
lst.erase_after(iter, lst.end());	// {5, 6}

array

就如同C++原本的数组一样，array需要在一开始确定容器的大小：

array<int, 5> c()

使用这个容器过程中，不能改变容器的大小。它比内置数组更加强大，例如支持迭代器操作，支持拷贝赋值操作，也支持at()来确定范围。

int a1[5] = { 1, 2, 3, 4, 5 };
//int a2[5] = a1;	// 不支持赋值

array<int, 5> a3 = { 1, 2, 3, 4, 5 };
array<int, 5> a4 = a3;	// 支持赋值
array<int, 5> a5(a3);	// 支持拷贝
//array<int, 6> a6 = a3;	// 类型不同，不能赋值

容器适配器

除了顺序容器之外，C++还定义了三个顺序容器适配器：stack，queue和priority_queue。适配器是一个通用概念，能使某种事物的行为看起来像另外一种事务。一个容器适配器接受一种已有的容器类型，使其行为看起来像一种不同的类型。

stack

stack类型定义在stack头文件中。基于deque实现。下面是它的部分操作：

• s.pop()：删除栈顶元素，但不返回元素值。
• s.push(item)：创建一个新元素压入栈顶，拷贝入栈。
• s.emplace(args)：在栈顶使用args构造一个新元素。
• s.top()：返回栈顶元素，但不将元素弹出栈。

queue

队列是一种先进先出（FIFO）的数据结构，类似于排队等候的情景。基于deque实现。下面是它的部分操作：

• q.push(val)：将元素val加入队尾。
• q.pop()：移除队首元素，不返回该元素的值。
• q.front()：返回队首元素的值。
• q.back()：返回队尾元素的值。
• q.empty()：检查队列是否为空，返回布尔值。
• q.emplace(args)：在队尾使用args构造元素。

priority_queue

优先队列是一种特殊的队列数据结构，其中每个元素都有一个优先级。元素按照优先级顺序进行排序，优先级高的元素先出队。优先队列的常见实现方式是基于堆（如二叉堆）。

操作

以下是优先队列的一些常见操作：

• pq.push(val)：将元素 val 加入优先队列。
• pq.pop()：移除优先队列中的最高优先级元素。
• pq.top()：返回优先队列中的最高优先级元素的值，但不移除它。
• pq.empty()：检查优先队列是否为空，返回布尔值。
• pq.emplace(args)：在优先队列中使用 args 构造元素并插入。

示例代码

以下是一个使用 C++ 标准库中的 priority_queue 的示例：

#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 默认情况下，priority_queue 是一个最大堆
    std::priority_queue<int> pq;

    // 插入元素
    pq.push(10);
    pq.push(20);
    pq.push(15);

    // 查看最高优先级元素
    std::cout << "Top element: " << pq.top() << std::endl;  // 输出 20

    // 移除最高优先级元素
    pq.pop();

    // 查看新的最高优先级元素
    std::cout << "Top element after pop: " << pq.top() << std::endl;  // 输出 15

    // 检查优先队列是否为空
    std::cout << "Is the priority queue empty? " << (pq.empty() ? "Yes" : "No") << std::endl;

    return 0;
}