博客

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

  • Post author:
  • Post category:其他



✅作者简介：人工智能专业本科在读，喜欢计算机与编程，写博客记录自己的学习历程。

🍎个人主页：

小嗷犬的个人主页


🍊个人网站：

小嗷犬的技术小站


🥭个人信条：为天地立心，为生民立命，为往圣继绝学，为万世开太平。

本文目录



C++ 标准模板库简介


C++ 标准模板库

（

S

tandard

T

emplate

L

ibrary）是 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

命名空间： 

#include <vector>
using namespace std;


vector 的定义


vector

和 C++ 中基本数据类型的定义类似，只需要在

vector

后面加上尖括号

<>

，并在尖括号中指定存储的数据类型即可。 

vector<类型名> 变量名;

类型名可以是任意的 C++ 基本数据类型，如

int

、

double

等，也可以是 STL 中的容器，如

vector

、

map

等，甚至可以是自定义的结构体或是自定义的类。 

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 定义时还可以指定初始元素的个数和初始值。 

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

中的所有元素

示例代码如下： 

#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 循环。 

#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

中的元素。 

#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

命名空间： 

#include <deque>
using namespace std;


deque 的定义


deque

的定义与

vector

类似，只需要在

deque

后面加上尖括号

<>

，并在尖括号中指定存储的数据类型即可。 

deque<类型名> 变量名;

类型名可以是任意的 C++ 基本数据类型，如

int

、

double

等，也可以是 STL 中的容器，如

vector

、

map

等，甚至可以是自定义的结构体或是自定义的类。 

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

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

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

中的所有元素

示例代码如下： 

#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 循环。 

#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

中的元素。 

#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

命名空间： 

#include <utility>
using namespace std;


pair 的定义


pair

的定义格式如下： 

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

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

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

定义时可以直接初始化： 

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

来访问和修改： 

#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

命名空间： 

#include <map>
using namespace std;


map 的定义


map

的定义格式如下： 

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

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

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

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

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

的键值对的个数

示例代码如下： 

#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 循环。 

#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

迭代器。 

#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

不存在，则会自动插入一个键值对，其值为默认值。 

#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;
}

下标运算符

[]

还可以用于修改键值对的值。 

#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)






O


(


1


)





，而

map

是基于红黑树实现的，因此查找和插入的时间复杂度为



O

(

log

⁡

n

)

O(\log n)






O


(


lo

g





n


)





。



set


set

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

map

。


set

以模板类的形式定义在头文件

<set>

中，并位于

std

命名空间中，因此使用

set

时需要包含头文件并使用

std

命名空间： 

#include <set>
using namespace std;


set

的定义如下： 

set<类型名> 变量名;

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

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


set

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

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

示例代码如下： 

#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 循环。 

#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()

。 

#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

是否存在。 

#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)






O


(


1


)





，而

set

是基于红黑树实现的，因此查找和插入的时间复杂度为



O

(

log

⁡

n

)

O(\log n)






O


(


lo

g





n


)





。



容器适配器

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



queue


queue

是一个先进先出的队列，其元素只能从队尾插入，从队首删除，其默认基于

deque

实现，因此

queue

的插入和删除操作的时间复杂度为



O

(

1

)

O(1)






O


(


1


)





。


queue

以模板类的形式定义在头文件

<queue>

中，并位于

std

命名空间中，因此使用

queue

时需要包含头文件并使用

std

命名空间： 

#include <queue>
using namespace std;


queue

的定义如下： 

queue<类型名> 变量名;

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

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


queue

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

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

中的队尾元素

示例代码如下： 

#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

方法访问队首和队尾元素。 

#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)






O


(


lo

g





n


)





。


priority_queue

以模板类的形式定义在头文件

<queue>

中，并位于

std

命名空间中，因此使用

priority_queue

时需要包含头文件并使用

std

命名空间： 

#include <queue>
using namespace std;


priority_queue

的定义如下： 

priority_queue<类型名> 变量名;

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

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

中的队首元素

示例代码如下： 

#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

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

#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;
}

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

#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;
}

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

#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)






O


(


1


)





。


stack

以模板类的形式定义在头文件

<stack>

中，并位于

std

命名空间中，因此使用

stack

时需要包含头文件并使用

std

命名空间： 

#include <stack>
using namespace std;


stack

的定义如下： 

stack<类型名> 变量名;

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

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

中的栈顶元素

示例代码如下： 

#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

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

#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

命名空间： 

#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

位

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

#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

为例的迭代器的使用示例： 

#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 文档

。


版权声明：本文为qq_63585949原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。