C++ 标准模板库（Standard Template Library，STL）

C++ 标准模板库简介

C++ 标准模板库（Standard Template Library）是 C++ 标准库的一部分，不需要另外安装，直接导入即可使用。

STL 为程序员提供了通用的模板类，这些模板类可以用来实现各种数据结构和算法，从而使程序员不必从头开始编写这些代码。

STL 很好地实现了数据结构和算法的分离，大大降低了模块之间的耦合度，程序员可以自由组合 STL 提供的数据结构和算法。

STL 的核心由以下三个部分组成：

  • 容器（Containers）：各种数据结构，如 vector、deque、map、set 等。
  • 算法（Algorithms）：各种算法，如排序、查找、转换等。
  • 迭代器（Iterators）：用于遍历容器的对象。

下面我们将从这三个部分来介绍 STL。

容器（Containers）

容器是用来存储数据的对象，它们提供了一种高效的方式来存储和访问数据。对于不同的任务，我们可以选择不同的容器来存储数据。

STL 的容器分为三类：

  • 序列容器：序列容器会维护插入元素的顺序。常用的序列容器有 vector、deque。
  • 关联容器：关联容器既有有序，也有无序，存储内容为键值对。常用的关联容器有 map、set。
  • 容器适配器：容器适配器是序列容器或关联容器的变体，它们对接口做了更多的限制，并且不支持迭代器。常用的容器适配器有 queue、priority_queue、stack。

序列容器

序列容器是一种线性的数据结构，它们会维护插入元素的顺序。本节我们将介绍 vector、deque 这两种序列容器。

vector

vector 是一个动态数组，它的大小可以动态改变。它可以随机访问、连续存储，长度也非常灵活。

由于它优良的性质，vector 成为了程序设计中首选的序列容器。

在你没有更好的理由选择其他容器的情况下，你应该使用 vector！

vector 以模板类的形式定义在头文件 <vector> 中，并位于 std 命名空间中，因此使用 vector 时需要包含头文件并使用 std 命名空间：

1
2
#include <vector>
using namespace std;

vector 的定义

vector 和 C++ 中基本数据类型的定义类似，只需要在 vector 后面加上尖括号 <>，并在尖括号中指定存储的数据类型即可。

1
vector<类型名> 变量名;

类型名可以是任意的 C++ 基本数据类型，如 int、double等，也可以是 STL 中的容器，如 vector、map 等，甚至可以是自定义的结构体或是自定义的类。

1
2
3
4
5
6
vector<int> v1; // 存储 int 类型的 vector
vector<double> v2; // 存储 double 类型的 vector
vector<vector<int> > v3; // 存储 vector<int> 类型的 vector
// 注意：声明类似 v3 这种结构时，'> >' 之间需要包含空格，以兼容 C++98 标准

vector<int> v4[10]; // 长度为 10 的 vector 数组，每个元素都是一个 vector<int>

vector 定义时还可以指定初始元素的个数和初始值。

1
2
3
4
vector<int> v1(10); // 长度为 10 的 vector，每个元素的初始值为 0
vector<int> v2(10, 1); // 长度为 10 的 vector，每个元素的初始值为 1
vector<int> v3{1, 2, 3}; // 长度为 3 的 vector，每个元素的初始值为 1、2、3
vector<int> v4 = {1, 2, 3}; // 长度为 3 的 vector，每个元素的初始值为 1、2、3

vector 的常用方法

下表列出了 vector 的一些常用方法：

方法说明
v.empty()判断 v 是否为空
v.size()返回 v 的大小
v.push_back(x)在 v 的末尾添加一个元素 x
v.clear()删除 v 中的所有元素

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    cout << v.empty() << endl; // 1，v 为空
    cout << v.size() << endl; // 0，v 的大小为 0

    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    cout << v.empty() << endl; // 0，v 不为空
    cout << v.size() << endl; // 3，v 的大小为 3

    v.clear();
    cout << v.empty() << endl; // 1，v 为空
    cout << v.size() << endl; // 0，v 的大小为 0

    return 0;
}

vector 的遍历

vector 的遍历与数组的遍历类似，可以使用下标来访问各元素的值，也可以使用迭代器来遍历，C++11 中还可以使用范围 for 循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);

    // 使用下标遍历
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ' ';
    }
    cout << endl;

    // 使用迭代器遍历
    for (vector<int>::iterator it = v.begin(); it != v.end(); it++) {
        cout << *it << ' ';
    }
    cout << endl;

    // 使用范围 for 循环
    for (int x : v) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}

除此之外，下标还可以用来随机访问和修改 vector 中的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <vector>
using namespace std;

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

    // 随机访问
    cout << v[0] << endl; // 1
    cout << v[1] << endl; // 2
    cout << v[2] << endl; // 3

    // 修改
    v[0] = 4;
    v[1] = 5;
    v[2] = 6;

    // 遍历
    for (int x : v) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}

deque

deque 是一个双端队列，它的大小可以动态改变。它可以随机访问、连续存储，长度也非常灵活。

deque 和 vector 的区别在于，deque 可以在头部和尾部快速插入和删除元素，而 vector 只能在尾部快速插入和删除元素。

deque 以模板类的形式定义在头文件 <deque> 中，并位于 std 命名空间中，因此使用 deque 时需要包含头文件并使用 std 命名空间：

1
2
#include <deque>
using namespace std;

deque 的定义

deque 的定义与 vector 类似，只需要在 deque 后面加上尖括号 <>，并在尖括号中指定存储的数据类型即可。

1
deque<类型名> 变量名;

类型名可以是任意的 C++ 基本数据类型，如 int、double等，也可以是 STL 中的容器，如 vector、map 等，甚至可以是自定义的结构体或是自定义的类。

1
2
3
4
5
6
deque<int> d1; // 存储 int 类型的 deque
deque<double> d2; // 存储 double 类型的 deque
deque<deque<int> > d3; // 存储 deque<int> 类型的 deque
// 注意：声明类似 d3 这种结构时，'> >' 之间需要包含空格，以兼容 C++98 标准

deque<int> d4[10]; // 长度为 10 的 deque 数组，每个元素都是一个 deque<int>

deque 定义时还可以指定初始元素的个数和初始值。

1
2
3
4
deque<int> d1(10); // 长度为 10 的 deque，每个元素的初始值为 0
deque<int> d2(10, 1); // 长度为 10 的 deque，每个元素的初始值为 1
deque<int> d3{1, 2, 3}; // 长度为 3 的 deque，每个元素的初始值为 1、2、3
deque<int> d4 = {1, 2, 3}; // 长度为 3 的 deque，每个元素的初始值为 1、2、3

deque 的常用方法

下表列出了 deque 的一些常用方法：

方法说明
d.empty()判断 d 是否为空
d.size()返回 d 的大小
d.push_back(x)在 d 的末尾添加一个元素 x
d.push_front(x)在 d 的头部添加一个元素 x
d.pop_back()删除 d 的末尾元素
d.pop_front()删除 d 的头部元素
d.clear()删除 d 中的所有元素

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d;
    cout << d.empty() << endl; // 1，d 为空
    cout << d.size() << endl; // 0，d 的大小为 0

    d.push_back(1);
    d.push_back(2);
    d.push_back(3);
    cout << d.empty() << endl; // 0，d 不为空
    cout << d.size() << endl; // 3，d 的大小为 3

    d.push_front(4);
    d.push_front(5);
    d.push_front(6);
    cout << d.empty() << endl; // 0，d 不为空
    cout << d.size() << endl; // 6，d 的大小为 6

    d.pop_back();
    d.pop_front();
    cout << d.empty() << endl; // 0，d 不为空
    cout << d.size() << endl; // 4，d 的大小为 4

    d.clear();
    cout << d.empty() << endl; // 1，d 为空
    cout << d.size() << endl; // 0，d 的大小为 0

    return 0;
}

deque 的遍历

deque 的遍历与 vector 类似，也可以使用下标、迭代器和范围 for 循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d{1, 2, 3};

    // 使用下标
    for (int i = 0; i < d.size(); i++) {
        cout << d[i] << ' ';
    }
    cout << endl;

    // 使用迭代器
    for (deque<int>::iterator it = d.begin(); it != d.end(); it++) {
        cout << *it << ' ';
    }
    cout << endl;

    // 使用范围 for 循环
    for (int x : d) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}

除此之外，下标还可以用于修改 deque 中的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> d{1, 2, 3};

    // 修改
    d[0] = 4;
    d[1] = 5;
    d[2] = 6;

    // 遍历
    for (int x : d) {
        cout << x << ' ';
    }
    cout << endl;

    return 0;
}

关联容器

关联容器是一种用于存储一对对关联元素的容器，其中每对元素又称为一个键值对（key-value pair），关联容器中的元素是按照键值对的方式存储的，我们可以通过键来快速查找对应的值。本节将介绍 pair 类和 map、set 这两种关联容器。

pair

pair 是一种用于存储一对元素的模板类，后续介绍的 map 和 set 存储的基本单元就是 pair。

pair 以模板类的形式定义在头文件 <utility> 中，并位于 std 命名空间中，因此使用 pair 时需要包含头文件并使用 std 命名空间：

1
2
#include <utility>
using namespace std;

pair 的定义

pair 的定义格式如下：

1
pair<类型名1, 类型名2> 变量名;

类型名1和类型名2可以是任意的 C++ 内置类型或自定义类型：

1
2
3
4
5
6
pair<int, int> p1; // 定义一个 pair，存储两个 int 类型的元素
pair<string, int> p2; // 定义一个 pair，存储一个 string 类型的元素和一个 int 类型的元素
pair<string, pair<int, int> > p3; // 定义一个 pair，存储一个 string 类型的元素和一个 pair，该 pair 存储两个 int 类型的元素
// 注意：声明类似 p3 这种结构时，'> >' 之间需要包含空格，以兼容 C++98 标准

pair<int, int> p4[10]; // 定义一个长度为 10 的 pair 数组，数组中的每个元素都是一个 pair<int, int>

pair 定义时可以直接初始化：

1
2
pair<int, int> p1(1, 2); // 定义一个 pair，存储两个 int 类型的元素，初始化为 (1, 2)
pair<string, int> p2("hello", 1); // 定义一个 pair，存储一个 string 类型的元素和一个 int 类型的元素，初始化为 ("hello", 1)

pair 的访问与修改

pair 中的元素可以通过 first 和 second 来访问和修改：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <utility>
using namespace std;

int main() {
    pair<int, int> p(1, 2);

    // 访问
    cout << p.first << ' ' << p.second << endl; // 1 2

    // 修改
    p.first = 3;
    p.second = 4;
    cout << p.first << ' ' << p.second << endl; // 3 4

    return 0;
}

map

map 是一种用于存储键值对的关联容器，基于红黑树（一种平衡二叉树）实现，键值对中的键是唯一的，而值则可以重复。map 的默认排序规则是按照键的升序排序，我们可以通过 map 快速查找某个键对应的值。

map 以模板类的形式定义在头文件 <map> 中，并位于 std 命名空间中，因此使用 map 时需要包含头文件并使用 std 命名空间：

1
2
#include <map>
using namespace std;

map 的定义

map 的定义格式如下：

1
map<键类型名, 值类型名> 变量名;

键类型名和值类型名可以是任意的 C++ 内置类型或自定义类型：

1
2
3
4
map<int, int> m1; // 存储 int 类型的键值对
map<string, int> m2; // 存储 string 类型的键和 int 类型的值
map<string, string> m3; // 存储 string 类型的键值对
map<string, vector<int>> m4; // 存储 string 类型的键和 vector<int> 类型的值

map 定义时还可以指定初始元素。

1
2
map<int, int> m1{{1, 2}, {3, 4}, {5, 6}}; // 通过初始化列表指定初始元素
map<int, int> m2(m1); // 通过另一个 map 拷贝构造

map 的常用方法

下表列出了 map 的一些常用方法：

方法说明
m.empty()判断 m 是否为空
m.size()返回 m 的大小
m.insert(pair)向 m 中插入一个键值对
m.emplace(pair)在 m 中构造一个键值对，C++11 支持，效率高于 insert
m.erase(key)删除 m 中键为 key 的键值对
m.clear()删除 m 中的所有键值对
m.count(key)返回 m 中键为 key 的键值对的个数

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> m;
    cout << m.empty() << endl; // 1，m 为空
    cout << m.size() << endl; // 0，m 的大小为 0

    m.insert({1, 2});
    m.insert({3, 4});
    m.insert({5, 6});
    cout << m.empty() << endl; // 0，m 不为空
    cout << m.size() << endl; // 3，m 的大小为 3

    m.erase(1);
    cout << m.empty() << endl; // 0，m 不为空
    cout << m.size() << endl; // 2，m 的大小为 2

    m.clear();
    cout << m.empty() << endl; // 1，m 为空
    cout << m.size() << endl; // 0，m 的大小为 0

    return 0;
}

map 的遍历

map 的遍历可以使用迭代器和范围 for 循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> m{{1, 2}, {3, 4}, {5, 6}};

    // 使用迭代器
    for (map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
        cout << it->first << ' ' << it->second << endl;
    }

    // 使用范围 for 循环
    for (pair<int, int> p : m) {
        cout << p.first << ' ' << p.second << endl;
    }

    return 0;
}

map 的查找

map 的查找可以使用 find 方法，该方法返回一个迭代器，指向键为 key 的键值对，如果 key 不存在，则返回 end 迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> m{{1, 2}, {3, 4}, {5, 6}};

    map<int, int>::iterator it = m.find(3);
    if (it != m.end()) {
        cout << it->first << ' ' << it->second << endl;
    }

    return 0;
}

我们更常用的是使用下标运算符 [] 来查找或插入键值对，如果 key 不存在，则会自动插入一个键值对，其值为默认值。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> m{{1, 2}, {3, 4}, {5, 6}};

    cout << m[3] << endl; // 4
    cout << m[7] << endl; // 0，7 不存在，会自动插入一个键值对
    cout << m.size() << endl; // 4，m 的大小为 4

    return 0;
}

下标运算符 [] 还可以用于修改键值对的值。

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> m{{1, 2}, {3, 4}, {5, 6}};

    m[3] = 7;
    cout << m[3] << endl; // 7

    return 0;
}

除此之外，map 还有一个无序的版本 unordered_map，其定义和使用方法与 map 类似，只是 unordered_map 是基于哈希表实现的，因此查找和插入的时间复杂度为O(1)O(1)，而 map 是基于红黑树实现的，因此查找和插入的时间复杂度为O(log⁡n)O(\log n)。

set

set 是一个集合，其元素是唯一的，不允许重复，本质上是一个键值相等的 map。

set 以模板类的形式定义在头文件 <set> 中，并位于 std 命名空间中，因此使用 set 时需要包含头文件并使用 std 命名空间：

1
2
#include <set>
using namespace std;

set 的定义如下：

1
set<类型名> 变量名;

类型名可以是任意的 C++ 内置类型或自定义类型：

1
2
3
4
set<int> s1; // 定义一个 set，元素类型为 int
set<string> s2; // 定义一个 set，元素类型为 string
set<set<int> > s3; // 定义一个 set，元素类型为 set<int>
// 注意：声明类似 s3 这种结构时，'> >' 之间需要包含空格，以兼容 C++98 标准

set 定义时还可以指定初始元素。

1
2
set<int> s1{1, 2, 3}; // 通过初始化列表指定初始元素
set<int> s2(s1); // 通过另一个 set 拷贝构造

set 的常用方法

下表列出了 set 的一些常用方法：

方法说明
s.empty()判断 s 是否为空
s.size()返回 s 的大小
s.insert(key)向 s 中插入元素 key
s.emplace(key)在 s 中构造元素 key，C++11 支持，效率高于 insert
s.erase(key)删除 s 中的元素 key
s.clear()清空 s
s.count(key)返回 s 中元素 key 的个数，key 不存在时返回 0

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;

    cout << s.empty() << endl; // 1，s 为空
    cout << s.size() << endl; // 0，s 的大小为 0

    s.insert(1);
    s.insert(3);
    s.insert(5);
    cout << s.empty() << endl; // 0，s 不为空
    cout << s.size() << endl; // 3，s 的大小为 3

    s.erase(1);
    cout << s.empty() << endl; // 0，s 不为空
    cout << s.size() << endl; // 2，s 的大小为 2

    s.clear();
    cout << s.empty() << endl; // 1，s 为空
    cout << s.size() << endl; // 0，s 的大小为 0

    return 0;
}

set 的遍历

set 的遍历可以使用迭代器或范围 for 循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s{1, 2, 3};

    // 使用迭代器
    for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
        cout << *it << endl;
    }

    // 使用范围 for 循环
    for (int x : s) {
        cout << x << endl;
    }

    return 0;
}

set 的查找

set 的查找可以使用 find 方法，其返回值是一个迭代器，如果 key 不存在，则返回 end()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s{1, 2, 3};

    set<int>::iterator it = s.find(2);
    if (it != s.end()) {
        cout << *it << endl;
    }

    return 0;
}

我们也可以使用 count 方法来判断 key 是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s{1, 2, 3};

    if (s.count(2)) {
        cout << "2 exists" << endl;
    }

    return 0;
}

除此之外，set 还有一个无序的版本 unordered_set，其定义和使用方法与 set 类似，只是 unordered_set 是基于哈希表实现的，因此查找和插入的时间复杂度为O(1)O(1)，而 set 是基于红黑树实现的，因此查找和插入的时间复杂度为O(log⁡n)O(\log n)。

容器适配器

容器适配器是序列容器或关联容器的特殊变体，它们基于底层容器实现，但对接口做了更多限制，不支持迭代器，因此不能与 STL 算法一起使用。

queue

queue 是一个先进先出的队列，其元素只能从队尾插入，从队首删除，其默认基于 deque 实现，因此 queue 的插入和删除操作的时间复杂度为O(1)O(1)。

queue 以模板类的形式定义在头文件 <queue> 中，并位于 std 命名空间中，因此使用 queue 时需要包含头文件并使用 std 命名空间：

1
2
#include <queue>
using namespace std;

queue 的定义如下：

1
queue<类型名> 变量名;

类型名可以是任意的 C++ 内置类型或自定义类型：

1
2
queue<int> q1; // 定义一个 queue，元素类型为 int
queue<string> q2; // 定义一个 queue，元素类型为 string

queue 定义时还可以指定初始元素。

1
2
queue<int> q1{1, 2, 3}; // 通过初始化列表指定初始元素
queue<int> q2(q1); // 通过另一个 queue 拷贝构造

queue 的常用方法

下表列出了 queue 的一些常用方法：

方法说明
q.empty()判断 q 是否为空
q.size()返回 q 的大小
q.push(x)插入元素 x 到 q 的队尾
q.pop()删除 q 中的队首元素
q.front()返回 q 中的队首元素
q.back()返回 q 中的队尾元素

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;

    cout << q.empty() << endl; // 1，q 为空
    cout << q.size() << endl; // 0，q 的大小为 0

    q.push(1);
    q.push(2);
    q.push(3);
    cout << q.empty() << endl; // 0，q 不为空
    cout << q.size() << endl; // 3，q 的大小为 3

    cout << q.front() << endl; // 1，q 的队首元素为 1
    cout << q.back() << endl; // 3，q 的队尾元素为 3

    q.pop();
    cout << q.front() << endl; // 2，q 的队首元素为 2

    return 0;
}

queue 不支持随机访问，也不能像 vector、deque 那样遍历，它只能通过 front 和 back 方法访问队首和队尾元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q{1, 2, 3};

    while (!q.empty()) {
        cout << q.front() << ' ';
        q.pop();
    }
    cout << endl;
    // 1 2 3

    return 0;
}

priority_queue

priority_queue 是一个优先队列，其元素按照优先级排序，优先级最高的元素在队首，优先级最低的元素在队尾，其默认基于 vector 实现，priority_queue 的插入和删除操作的时间复杂度为O(log⁡n)O(\log n)。

priority_queue 以模板类的形式定义在头文件 <queue> 中，并位于 std 命名空间中，因此使用 priority_queue 时需要包含头文件并使用 std 命名空间：

1
2
#include <queue>
using namespace std;

priority_queue 的定义如下：

1
priority_queue<类型名> 变量名;

类型名可以是任意的 C++ 内置类型或自定义类型：

1
2
priority_queue<int> q1; // 定义一个 priority_queue，元素类型为 int
priority_queue<string> q2; // 定义一个 priority_queue，元素类型为 string

priority_queue 的常用方法

下表列出了 priority_queue 的一些常用方法：

方法说明
q.empty()判断 q 是否为空
q.size()返回 q 的大小
q.push(x)插入元素 x 到 q
q.pop()删除 q 中的队首元素
q.top()返回 q 中的队首元素

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> q;

    cout << q.empty() << endl; // 1，q 为空
    cout << q.size() << endl; // 0，q 的大小为 0

    q.push(1);
    q.push(2);
    q.push(3);
    cout << q.empty() << endl; // 0，q 不为空
    cout << q.size() << endl; // 3，q 的大小为 3

    cout << q.top() << endl; // 3，q 的队首元素为 3

    q.pop();
    cout << q.top() << endl; // 2，q 的队首元素为 2

    return 0;
}

和 queue 一样，priority_queue 也不支持迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。

priority_queue 默认为最大堆，即越大的元素优先级越高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> q;
    q.push(4);
    q.push(5);
    q.push(2);
    q.push(3);
    q.push(1);

    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;
    // 输出：5 4 3 2 1
    return 0;
}

如果想要实现最小堆，可以通过模板参数指定比较函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> q;
    q.push(4);
    q.push(5);
    q.push(2);
    q.push(3);
    q.push(1);

    while (!q.empty()) {
        cout << q.top() << " ";
        q.pop();
    }
    cout << endl;
    // 输出：1 2 3 4 5
    return 0;
}

或是在插入和删除元素时对元素取反：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> q;
    q.push(-4);
    q.push(-5);
    q.push(-2);
    q.push(-3);
    q.push(-1);

    while (!q.empty()) {
        cout << -q.top() << " ";
        q.pop();
    }
    cout << endl;
    // 输出：1 2 3 4 5
    return 0;
}

stack

stack 是一个栈，其元素按照先进后出的顺序排序，其默认基于 deque 实现，stack 的插入和删除操作的时间复杂度为O(1)O(1)。

stack 以模板类的形式定义在头文件 <stack> 中，并位于 std 命名空间中，因此使用 stack 时需要包含头文件并使用 std 命名空间：

1
2
#include <stack>
using namespace std;

stack 的定义如下：

1
stack<类型名> 变量名;

类型名可以是任意的 C++ 内置类型或自定义类型：

1
2
stack<int> s1; // 定义一个 stack，元素类型为 int
stack<string> s2; // 定义一个 stack，元素类型为 string

stack 的常用方法

下表列出了 stack 的一些常用方法：

方法说明
s.empty()判断 s 是否为空
s.size()返回 s 的大小
s.push(x)插入元素 x 到 s
s.pop()删除 s 中的栈顶元素
s.top()返回 s 中的栈顶元素

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;

    cout << s.empty() << endl; // 1，s 为空
    cout << s.size() << endl; // 0，s 的大小为 0

    s.push(1);
    s.push(2);
    s.push(3);
    cout << s.empty() << endl; // 0，s 不为空
    cout << s.size() << endl; // 3，s 的大小为 3

    cout << s.top() << endl; // 3，s 的栈顶元素为 3

    s.pop();
    cout << s.top() << endl; // 2，s 的栈顶元素为 2

    return 0;
}

和 queue 一样，stack 也不支持迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);

    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
    // 输出：5 4 3 2 1
    return 0;
}

以上仅介绍了一些常用的 STL 容器，更多容器和使用方法可以参考 Microsoft C++ stl-containers 文档。

算法（Algorithm）

STL 中还提供了一些常用的算法，它们都定义在头文件 <algorithm> 中，并位于 std 命名空间中，因此使用算法时需要包含头文件并使用 std 命名空间：

1
2
#include <algorithm>
using namespace std;

下表列出了部分常用算法：

算法说明
sort(v.begin(), v.end())对 v 中的元素进行排序
reverse(v.begin(), v.end())将 v 中的元素反转
find(v.begin(), v.end(), x)在 v 中查找元素 x，返回其迭代器
lower_bound(v.begin(), v.end(), x)在 v 中查找第一个大于等于 x 的元素，返回其迭代器，要求 v 有序
upper_bound(v.begin(), v.end(), x)在 v 中查找第一个大于 x 的元素，返回其迭代器，要求 v 有序
binary_search(v.begin(), v.end(), x)在 v 中查找元素 x，返回 true 或 false，要求 v 有序
max_element(v.begin(), v.end())返回 v 中的最大元素的迭代器
min_element(v.begin(), v.end())返回 v 中的最小元素的迭代器
accumulate(v.begin(), v.end(), x)返回 v 中所有元素的和，x 为初始值
copy(v.begin(), v.end(), v2.begin())将 v 中的元素复制到 v2 中
count(v.begin(), v.end(), x)返回 v 中元素 x 的个数
count_if(v.begin(), v.end(), f)返回 v 中满足条件 f 的元素个数
fill(v.begin(), v.end(), x)将 v 中的所有元素赋值为 x
replace(v.begin(), v.end(), x, y)将 v 中的所有元素 x 替换为 y
replace_if(v.begin(), v.end(), f, x)将 v 中满足条件 f 的元素替换为 x
unique(v.begin(), v.end())将 v 中的重复元素移动至容器末尾，返回指向第一个重复元素的迭代器
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin())将 v1 和 v2 合并到 v3 中
inplace_merge(v.begin(), v.begin() + n, v.end())将 v 中的前 n 个元素和后面的元素合并
partition(v.begin(), v.end(), f)将 v 中满足条件 f 的元素放在前面，不满足的放在后面，返回指向第一个不满足条件 f 的元素的迭代器
random_shuffle(v.begin(), v.end())将 v 中的元素随机打乱
next_permutation(v.begin(), v.end())返回 v 的下一个排列，如果不存在下一个排列，则返回 false
prev_permutation(v.begin(), v.end())返回 v 的上一个排列，如果不存在上一个排列，则返回 false
rotate(v.begin(), v.begin() + n, v.end())将 v 中的元素循环左移 n 位

其中一些算法的使用示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

    // 将 v 中的元素反转
    reverse(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
    // 输出：5 4 3 2 1

    // 将 v 中的元素排序
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
    // 输出：1 2 3 4 5

    // 在 v 中查找元素 3
    vector<int>::iterator it = find(v.begin(), v.end(), 3);
    if (it != v.end()) {
        cout << "找到元素 3" << endl;
    } else {
        cout << "未找到元素 3" << endl;
    }
    // 输出：找到元素 3

    // 在 v 中查找第一个大于等于 3 的元素
    it = lower_bound(v.begin(), v.end(), 3);
    if (it != v.end()) {
        cout << "找到第一个大于等于 3 的元素：" << *it << endl;
    } else {
        cout << "未找到第一个大于等于 3 的元素" << endl;
    }
    // 输出：找到第一个大于等于 3 的元素：3

    // 在 v 中查找第一个大于 3 的元素
    it = upper_bound(v.begin(), v.end(), 3);
    if (it != v.end()) {
        cout << "找到第一个大于 3 的元素：" << *it << endl;
    } else {
        cout << "未找到第一个大于 3 的元素" << endl;
    }
    // 输出：找到第一个大于 3 的元素：4

    // 计算 v 中所有元素的和
    int sum = accumulate(v.begin(), v.end(), 0);
    cout << "v 中所有元素的和为：" << sum << endl;
    // 输出：v 中所有元素的和为：15

    // 随机打乱 v 中的元素，设置随机种子为 0
    srand(0);
    random_shuffle(v.begin(), v.end());
    cout << "随机打乱后的 v：" << endl;
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
    // 输出：随机打乱后的 v：3 1 5 4 2

    // 查找 v 中最大的元素
    it = max_element(v.begin(), v.end());
    cout << "v 中最大的元素为：" << *it << endl;
    // 输出：v 中最大的元素为：5

    // 查找 v 中最小的元素
    it = min_element(v.begin(), v.end());
    cout << "v 中最小的元素为：" << *it << endl;
    // 输出：v 中最小的元素为：1

    // 将 v 中的元素循环右移 1 位
    rotate(v.begin(), v.begin() + 1, v.end());
    cout << "将 v 中的元素循环左移 1 位后的结果：" << endl;
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
    // 输出：将 v 中的元素循环左移 1 位后的结果：1 5 4 2 3

    // 输出 v 的下一个排列
    next_permutation(v.begin(), v.end());
    cout << "v 的下一个排列为：" << endl;
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }

    // 将 v 中的元素降序排列
    sort(v.begin(), v.end(), greater<int>());
    cout << "将 v 中的元素降序排列后的结果：" << endl;
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";
    }
    cout << endl;
    // 输出：将 v 中的元素降序排列后的结果：5 4 3 2 1

    return 0;
}

上面的示例仅展示了 STL 中部分常用算法的部分用法，更多函数和详细用法可以参考 Microsoft C++ <algorithms> 文档。

迭代器（Iterator）

迭代器是一种用于访问容器中元素的对象，类似指针，可以用来遍历容器中的元素。

迭代器按照定义可以分为四种：

  • 正向迭代器：只能从前向后遍历容器中的元素，不能从后向前遍历。
  • 常量正向迭代器：只能从前向后遍历容器中的元素，不能从后向前遍历，且只能读取容器中的元素，不能修改容器中的元素。
  • 反向迭代器：只能从后向前遍历容器中的元素，不能从前向后遍历。
  • 常量反向迭代器：只能从后向前遍历容器中的元素，不能从前向后遍历，且只能读取容器中的元素，不能修改容器中的元素。

它们的定义方法如下表所示：

迭代器类型定义方法
正向迭代器容器类名::iterator 迭代器名;
常量正向迭代器容器类名::const_iterator 迭代器名;
反向迭代器容器类名::reverse_iterator 迭代器名;
常量反向迭代器容器类名::const_reverse_iterator 迭代器名;

所有的迭代器都支持 ++ 操作，即递增操作，用于访问容器中的下一个元素。对于正向迭代器，++ 操作会使其指向容器中的后一个元素，而反向迭代器则是指向容器中的前一个元素。

使用 *迭代器名 可以访问迭代器所指向的元素，对于非常量迭代器，还可以使用 *迭代器名 = 新值 来修改迭代器所指向的元素。

<algorithm> 中的许多函数都是以迭代器作为返回值来返回的。

迭代器按功能分类可以分为三种：

  • 正向迭代器：支持 ++、*、==、!= 操作，两个正向迭代器还可以相互赋值。
  • 双向迭代器：支持正向迭代器的所有操作，还支持 -- 操作，-- 操作的移动方向与 ++ 相反。
  • 随机访问迭代器：支持双向迭代器的所有操作，还支持 +、-、+=、-=、<、<=、>、>=、[] 操作。

对于这些操作的简单解释如下：

操作说明
++使迭代器指向容器中的下一个元素
--使迭代器指向容器中的前一个元素
*返回迭代器所指向的元素
==判断两个迭代器是否指向同一个元素
!=判断两个迭代器是否指向不同的元素
+i返回原迭代器向后移动 i 个位置后的迭代器
-i返回原迭代器向前移动 i 个位置后的迭代器
+=i使原迭代器向后移动 i 个位置
-=i使原迭代器向前移动 i 个位置
<迭代器1 指向的元素是否在 迭代器2 指向的元素之前
<=迭代器1 指向的元素是否在 迭代器2 指向的元素之前或相等
>迭代器1 指向的元素是否在 迭代器2 指向的元素之后
>=迭代器1 指向的元素是否在 迭代器2 指向的元素之后或相等
[i]返回原迭代器后第 i 个元素

不同的容器支持的迭代器功能也不同，如下表所示：

容器迭代器功能
vector随机访问迭代器
deque随机访问迭代器
list双向迭代器
set双向迭代器
map双向迭代器
queue不支持迭代器
priority_queue不支持迭代器
stack不支持迭代器

使用容器自带的 begin() 和 end() 函数可以得到容器的首迭代器和尾迭代器，两迭代器相减可以得到它们在容器中的下标之差（可为负）。

下面是以 vector 为例的迭代器的使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

    // 使用迭代器遍历
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;
    // 输出：3 1 5 4 2

    auto ma = max_element(v.begin(), v.end());
    auto mi = min_element(v.begin(), v.end());

    cout << "v 的最大值：" << *ma << endl;  // 输出：v 的最大值：5
    cout << "v 的最小值：" << *mi << endl;  // 输出：v 的最小值：1
    cout << "v 最大值与最小值元素下标差：" << ma - mi << endl;  // 输出：v 最大值与最小值之间元素下标差：1

    return 0;
}

更详细的迭代器使用方法可以参考 Microsoft C++ iterators 文档。