STL 模板库

STL 介绍

标准模板库（STL，英文全称 Standard Template Library），是C++标准库中的一个重要组成部分。它提供了一套通用的模板类和函数，用于处理数据结构和算法，使开发人员能够更轻松地编写高质量的C++代码。

STL 主要包括以下几部分：

1. 容器（Containers）：容器是存储和管理数据的集合类。STL提供了多种容器类型，如向量（vector）、链表（list）、队列（queue）、栈（stack）、集合（set）、映射（map）等。可以根据需求选择合适的容器来存储和操作数据。
2. 算法（Algorithms）：STL提供了大量的算法，如排序、查找、合并、计数等。这些算法可以直接应用于容器，无需手动实现，极大地提高了开发效率。
3. 迭代器（Iterators）：迭代器是STL中用于访问容器元素的一种方式。它提供了一种统一的接口，使得可以通过类似指针的方式遍历和操作容器中的元素。
4. 适配器（Adapters）：适配器用于将一种接口转换为另一种接口。

STL的优势在于它提供了高度可重用的模块化组件，使得开发人员能够更专注于解决问题，而不是从头开始实现数据结构和算法。通过使用STL，可以减少代码量、提高开发效率、降低错误率，并且可以利用STL的高性能实现来获得更好的程序性能。

容器 Container

容器（Containers）是 STL 中的核心组件，用于存储和管理数据。STL提供了多种容器类型，以满足不同的需求。

根据容器的特点，可以分为两大类：序列式容器和关联式容器。

序列式容器，主要用于按顺序存储元素。常见的有：

• 向量（vector），又称动态数组，支持快速随机访问和在末尾插入/删除元素。
• 列表（list），又称双向链表，支持在任何位置插入/删除元素，但不支持快速随机访问。
• 双端队列（deque），支持在两端插入/删除元素。
• 数组（array），固定大小数组，支持快速随机访问。我们在前面早以学过。
• 单向链表（forward_list），仅支持在头部插入/删除元素。

关联式容器，主要用于按特定顺序存储键值对（key value）。常见的有：

• 集合（set），存储唯一元素，元素按特定顺序排列。
• 映射（map），存储键值对，键唯一且按特定顺序排列。
• 无序集合（unordered_set）：存储唯一元素，使用哈希表实现。
• 无序映射（unordered_map）：无序映射，存储键值对，使用哈希表实现。

向量 vector

Vector 是一个封装了动态大小数组的顺序容器（Sequence Container）。跟任意其它类型容器一样，它能够存放各种类型的对象。可以简单的认为，Vector 是一个能够存放任意类型的动态数组。

Vector 是 C++ STL 中最常用的容器之一，通常也称为向量容器，可以简单的把 Vector 理解为普通数组（Array）的升级版（可变长的数组）。

Vector 属于动态数组，可以实现元素的插入和删除，在元素插入和删除的过程中，Vector 会动态地调整所占用的内存空间，无须人工干预。

向量定义

#include <vector> // 要使用 vector，需要引入相应的头文件

// 定义一个 vector，名字是 v，未初始化
vector<int> v;

// 定义一个未初始化的 vector，然后将 vector 长度调整为 5
vector<int> v;
v.resize(5);

// 定义长度为 5 的 vector，
vector<int> v(5);

// 定义并初始化，初始化后，vector 长度为 3
vector<int> v = {1, 2, 3};

向量初始化

// 方法1
vector<int> v= {1, 2, 4};

// 方法2
// 定义一个长度为 10 的 vector，并将里面所有元素的值设为 1
vector<int> v(10, 1);

// 方法3
vector<int> v(10);
fill(v.begin(), v.end(), 1) // 将 vector 全部填充 1

基本上，使用 array 去完成的操作，在 vector 中都可以完成，而且使用 vector 会更灵活一些。

添加和删除元素

vector<int> v;
v.push_back(5); // 在 v 尾部增加元素 5
v.emplace_back(8); // 在 v 尾部增加元素 8
v.pop_back(); // 删除 v 最的一个元素

这里的 emplace_back() 是 C++ 11 标准新增加的，如果要兼容之前的版本，就使用 push_back()，也比较好记。11 标准以后，推荐使用 emplace_back() 。

emplace_back()，push_back() 的主要区别在于底层实现的机制不同。push_back() 在向容器尾部添加元素时，首先会创建这个元素，然后再将创建出的元素拷贝或移动到容器；而 emplace_back 则是直接在容器尾部创建这个元素，省去了拷贝和移动的过程。emplace_back() 执行效率更高一些。

遍历 Vector

既然 Vector 可以看作是一种动态数组，你可以像数组那样利用循环去遍历 Vector。

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

// vector 遍历
int main() {
    vector<int> v = {2, 1, -3, 8, -15};

    for (int i = 0; i < v.size(); i++) {
      cout << v[i] << " ";
    }

    return 0;
}

这里的 v.size() 是用来获取 Vector 的长度（也就是元素的个数），其它的操作与遍历数组是完全一样的。

也可以使用 v.length() 去获取 Vector 的长度，与 v.size() 是同样的效果，v.size() 是为了兼容 STL 容器的操作在 C++ 11 后加入的。

与数组一样，也可以直接使用 Ranged for 来遍历 Vector 中的所有元素。

for (const int& i : v) {
  cout << i << " ";
}

迭代器 iterator 遍历

迭代器（iterator）是标准库中一个核心的概念，可以将其理解为一种用于遍历和访问容器（如数组、向量、链表等）元素的对象或指针。迭代器提供了一种统一的方式来访问容器中的元素，使得我们可以按照特定的顺序遍历容器并执行操作。

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // 迭代器的声明和初始化
    vector<int>::iterator it = v.begin();

    // 使用迭代器遍历容器并输出元素
    while (it != v.end()) {
        cout << *it << endl;
        ++it;  // 移动到下一个元素
    }

    return 0;
}

程序运行结果：

1
2
3
4
5

在使用迭代器的时候，你可以不用关心容器类型及其内部的实现，直接使用统一方式去遍历并访问元素。这种抽象化的设计使得我们可以更加灵活地处理不同类型的容器，并进行各种操作（如查找特定元素、修改元素值、删除元素等）。

栈 stack

栈（Stack）是其中一种比较简单，但很常见的数据结构。它是一种 后进先出（Last In First Out，简称 LIFO） 的数据结构，也就是最后进入的元素最先被取出。

有点像咱们平时买乒乓球或羽毛球那种直直的收纳筒。下面是一个示意图，放乒乓球时，最先放入的乒乓球在直筒的最下面，当我们取乒乓球的时候，直筒最上面（最后放入）的乒乓球会被最先取出。

对于栈这种结构来说，往里面加入数据的操作称为 push，从栈取出数据的操作称为 pop。

定义与初始化

STL 中提供了栈（stack）的实现，要使用它，需要引入相应的头文件：

#include <stack>

然后可以像下面这样创建一个栈：

stack<int> st; // 创建了一个名为 st 的栈，存放整数类型的数据

常见操作

下面是对栈的一些常见操作方法：

• push(x)：添加一个元素 x 到栈顶
• pop()：移除栈顶元素，并返回该元素
• top()：返回栈顶元素（但不删除栈顶元素）
• empty()：如果栈为空，则返回 true
• size()：返回栈中元素的个数

我们也可以自己用数组来实现栈的功能，作为练习，大家可以下去尝试一下。

通过一个简单的示例来看看具体怎么使用上面这些方法：

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> st;

    for (int i = 0; i < 10; i++) {
        st.push(i);
    }

    cout << "栈中元素的个数为：" << st.size() << endl;
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }

    cout << endl;

    if (st.empty()) {
        cout << "栈为空" << endl;
    }

    return 0;
}

程序运行结果

栈中元素的个数为：10
9 8 7 6 5 4 3 2 1 0
栈为空

栈的应用

栈是一种遵循「后进先出」原则的数据结构， 最后放入的元素首先被取出，在实际编程中，栈常用于处理函数调用、表达式求值、括号匹配等场景。在后面的算法实践中，我们会逐一接触到。

队列 queue

队列（Queue）是另外一种常见的数据结构，遵循 先进先出（First In First Out，简称 FIFO） 的原则，也就是说，最先进入队列的元素也是最先出来。

队列很像我们平时排队购票的场景，如下图所示，最先来的人排在前面，队首，也就是最前面的人也是最先可以购买到票的人，最后来的人排在队列的尾上。

定义与初始化

STL 中提供了队列（queue）的实现，要使用它，需要引入相应的头文件：

#include <queue>

然后可以像下面这样创建一个队列：

queue<int> q; // 创建了一个名为 q 的队列，存放整数类型的数据

常见操作

下面是对队列的一些常见操作方法：

• push(x)：添加一个元素 x 到队尾
• pop()：移除队首元素，并返回该元素
• front()：返回队首元素（但不删除队首元素）
• back()：返回队尾元素（但不删除队尾元素）
• empty()：如果队列为空，则返回 true
• size()：返回队列中元素的个数

下面通过具体代码演示了队列的一些常见操作：

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> q;

    // 向队列中添加元素
    q.push(1);
    q.push(2);
    q.push(3);

    // 输出队首和队尾的元素
    cout << "队头元素: " << q.front() << endl;
    cout << "队尾元素: " << q.back() << endl;

    // 弹出队首元素
    q.pop();

    // 再次输出队头和队尾的元素
    cout << "队头元素: " << q.front() << endl;
    cout << "队尾元素: " << q.back() << endl;

    // 输出队列的元素个数
    cout << "队列的元素个数: " << q.size() << endl;

    // 检查队列是否为空
    if (q.empty()) {
        cout << "队列为空" << endl;
    } else {
        cout << "队列是非空的" << endl;
    }

    return 0;
}

队列的应用

队列是一种遵循「先进先出」原则的数据结构， 最早进入队列的元素首先被取出，在实际编程中，队列常用于处理任务调度、消息传递、缓冲区管理等场景。在后面的算法实践中，我们也会接触到一些列队的应用。

优先级列队 priority_queue

优先级队列（priority_queue）是一种特殊类型的队列，它提供了一种按照优先级进行元素访问的方式。

优先级队列 priority_queue 是使用堆（heap）数据结构来实现的。

定义与初始化

要创建优先级队列，需要引入同样的 queue 头文件。

STL 中提供了优先级队列（priority_queue）的实现，与 queue 在同样的头文件。

#include <queue>

然后可以像下面这样创建一个优先级队列：

priority_queue<int> pq; // 创建了一个名为 pq 的优先级队列，存放整数类型的数据

常见操作

下面是对优先级队列的一些常见操作方法：

• push(x)：插入元素到优先级队列
• pop()：移除最高优先级的元素
• top()：返回最高优先级的元素
• size()：返回元素的个数
• empty()：如果队列为空，返回 true

下面看一个例子：

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

int main() {
  priority_queue<int> pq;  // 创建一个存储整数的优先级队列

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

  // 访问并打印队列中的元素
  while (!pq.empty()) {
    cout << pq.top() << " ";  // 访问队列中优先级最高的元素（默认为最大值）
    pq.pop();   // 移除队列中优先级最高的元素（默认为最大值）
  }

  return 0;
}

运行程序，输出结果为：

30 20 10 5

默认情况下，优先级队列的元素是按从小到大的优先级来排列的，队首为最大值。这个默认的优先级行为是可以更改的。

我们在定义优先级队列时，可以根据需要来自定义元素类型和比较规则。下面是明确指定了比较规则：

// 更改为从大到小排列，队首为最小值
priority_queue<int, vector<int>, greater<int>> pq;

默认行为相当于：

// 更改为从小到大排列，队首为最大值
priority_queue<int, vector<int>, less<int>> pq;

当然，你也可以手动指定比较函数，如下：

bool cmp(int a, int b) {
  return a > b;
}
// 这与前面的 greater<int> 是等价的
priority_queue<int, vector<int>, cmp> pq;

优先级队列的应用

priority_queue 插入和删除操作的时间复杂度为 $O(logn)$ ，都比较高效；但无法随机问题它当中的元素，这也意味着你不能直接访问队列中除了是高优先级元素以外的其它元素。

priority_queue 中的元素是按优先级来排列的，因此一定特定的场景中非常有用，比如贪心算法中，通常需要在每个步骤中选择最高（或最低）优先级的元素，正好可以使用 priority_queue 。另外，在事件调度、模拟系统及图算法等领域中也有广泛的应用。

集合 set

set 是一个有序容器（默认从小到大排列），并且它里面的元素是唯一的（元素不重复），加外 set 容器里元素的值是不可以修改的，但可以插入或删除。

集合 set 是使用红黑树（red-black tree）数据结构来实现的。

定义与初始化

STL 中提供了集合（set）的实现，要使用它，需要引入相应的头文件：

#include <set>

然后可以像下面这样创建一个集合：

set<int> my_set; // 创建了一个名为 my_set 的集合，存放整数类型的数据

常见操作

下面是对集合的一些常见操作方法：

• insert(x)：插入元素到集合
• erase(x)：从集合移除指定元素
• clear()，删除集合中的所有元素
• count(x)，判断元素在集合中是否存在，存在返回 1，不存在返回 0
• size()：返回集中的元素个数
• empty()：如果集合为空，返回 true

下面看一个例子：

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

int main() {
  set<int> my_set;  // 创建一个存储整数的 set

  // 向集合中插入元素
  my_set.insert(10);
  my_set.insert(5);
  my_set.insert(20);
  my_set.insert(15);

  // 遍历并打印集合中的元素
  for (const auto& element : my_set) {
    cout << element << " ";
  }

  return 0;
}

程序运行结果为：

5 10 15 20

set 与 vector 的区别

容器内的元素是否重复

set 容器中的元素是不重复的，而 vector 中的元素可以重复

容器内的元素是否可修改

set 容器中的元素是不可修改的，而 vector 中元素的值可以修改

容器内的元素是否有序

set 容器中的元素是有序排列的，跟插入顺序无关；而 vector 中的元素排列顺序与插入的顺序直接相关

集合的应用

set 在一些数据处理、图形算法及字符串处理等领域也有广泛应用。它也是许多其它算法或数据结构的底层实现之一，如果平衡二叉搜索树（BST）就是通过 set 来实现的。

需要注意的是，当你选择使用set时，要权衡其优点和缺点。set的插入和删除操作相对较慢，因为它需要维护有序性。此外，set的内存占用也比较大，因为它需要额外的指针来维护树结构。因此，在特定的应用场景中，你可能需要考虑其他容器，如unordered_set，它提供了更快的插入和删除操作，但不保证元素的有序性。

映射 map

映射（map） 是一个关联容器，用于存储键-值对（key-value pairs）。map 提供了一种基于键进行高效查找和插入的机制。

定义与初始化

常见操作

映射的应用

算法 Algorithm

C++ 的 STL 中，提供了许多强大和灵活的算法，这些算法都是泛型的，因此可以与任何容器一起使用，主要用于对容器中的元素执行各种操作（如排序、查找、复制、变换等），目标是通过这种方式提高代码的可读性和可维护性。

要使用这些算法，我们需要包括下面三个头文件：

// 大量与排序、查找相关的算法都在这里面
#include <algorithm>

// 涉及到一些数值运算的模板函数
#include <numeric>

// 一些用于声明函数对象模板类
#include <functional>

在后面的算法章节，会更细致的讲解各种算法背后的原理，好些算法在 STL 中已经有了，从学习（包括竞赛）的角度，我们既要学会如何使用 STL 中的这些算法，也需要弄明白这些算法背后的原理（很多算法自己要能够手写出来）。

下面讲一讲常用的几类算法及示例。

排序算法 Sorting Algorithm

排序算法主要用于将元素按特定顺序排列。

我们在后面会讲到不同的排序算法的实现方式及算法复杂度分析，STL 中的排序算法函数 sort() ，实际上是快速排序（quick sort）的实现，快排相对来说是综合性比较好的一种排序算法。

1. sort()

对范围内的元素进行排序（默认为升序）。

下面是一个对 vector 进行排序的简单示例：

#include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> vec = {6, 5, 1, 2, 8};

  sort(vec.begin(), vec.end());

  for (int n : vec) {
    cout << n << " ";
  }
  // 输出: 1 2 5 6 8
  return 0;
}

sort() 也可以对普通数组进行排序。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int q[] = {6, 5, 1, 2, 8};
  sort(q, q + 5);

  for (int i = 0; i < 5; i++) {
    cout << q[i] << " ";
  }

  return 0;
}

2. stable_sort()

对范围内的元素进行稳定排序，稳定的意思是保持相等元素的相对顺序不变。

下面是一个示例：

// stable_sort() 示例
#include <bits/stdc++.h>
using namespace std;

struct Person {
    int age;
    string name;
};

bool compare(const Person& a, const Person& b) {
  return a.age < b.age;
}

int main() {

    vector<Person> vec = {{25, "Alice"}, {22, "Bob"}, {25, "Charlie"}};
    stable_sort(vec.begin(), vec.end(), compare);

    for (const auto& person : vec) {
        cout << person.age << ": " << person.name << " ";
    }
    // 输出: 22: Bob 25: Alice 25: Charlie
    return 0;
}

3. partial_sort()

对范围内的一部分元素进行排序，将指定数量的最小元素移动到范围的开始位置。

下面是一个示例：

搜索 Searching

组合 Permutations

迭代器 Iterators