C++ STL

C++ STL教程

一直以来在竞赛界一直有着一种传言，自己手搓的数组、栈、队列效率比STL高很多，甚至于还有江湖传说，有的人用自己写的就过了，用STL就超时。但其实STL恰恰在C++一众繁复的特性中，是最受人欢迎的之一。使用STL其实并不会让效率降低很多，反而可以让自己的程序更具有可读性，以及获得更低的编程复杂度(笑，现在真的还有人讲究编程复杂度这种玩意么)。

所以特此写下一篇教程。（也是为了让自己以后忘记STL用法的时候能记起来，hhh）

一、概念

C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。

C++ 标准模板库的核心包括以下三个组件：

组件 描述
容器（Containers） 容器是用来管理某一类对象的集合。C++ 提供了各种不同类型的容器，比如 deque、list、vector、map 等。
算法（Algorithms） 算法作用于容器。它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。
迭代器（iterators） 迭代器用于遍历对象集合的元素。这些集合可能是容器，也可能是容器的子集。

二、简介

以下这个篇章将简单介绍STL容器的一些通用规则。（大部分以vector容器为例）

1.引入与声明

首先你需要什么容器就需要引入什么头文件，

例如你需要vector、stack、pair容器，你就要引入以下头文件：

1
2
3
#include <vector>
#include <stack>
#include <pair>

其次需要在主程序里声明这几个容器，例如：

1
2
3
vector<int> vec;
stack<int> s;
vector<int> vec1{1,2,3,4};  //也可以初始化容器

也可以在容器里叠加其他容器：

1
2
vector<vector<int> > vec1; //二维数组
stack<pair<int,int> > s1;

需要注意的是两个> >之间有空格。

2.访问方式

STL既可以使用传统的数组下标访问（并不是所有的容器都支持数组下标访问），也可以通过迭代器（iterators）访问。需要注意的是使用迭代器访问是更为安全的方法，因为使用数组下标访问时，对于越界并不判定。

传统数组下标访问如下：

1
2
3
4
5
6
7
8
9
10
#include <vector>
#include <iostream>
using namespace std;
int main(){
    vector<int> vec{1,2,3,4,5}; //初始化一个{1,2,3,4,5}的数组
    for (int i=0;i<=4;i++)	//值得注意的时数组下标从0开始
        cout<<vec[i]<<" ";
    cout<<endl;
    return 0;
}

声明迭代器的方法，根据你的容器不同而不同：

1
vector<int>::iterator i;

使用迭代器访问如下：

1
2
3
4
5
6
7
8
9
10
11
#include <vector>
#include <iostream>
using namespace std;
int main(){
    vector<int> vec{1,2,3,4,5};
    vector<int>::iterator i;
    for (int i=vec.begin();i!=vec.end();i++)
        cout<<*i<<" ";
    cout<<endl;
    return 0;
}

PS:在for (int i = vec.begin();i != vec.end();i++)这行中千万不能写成i <= vec.end()！千万不能写成i <= vec.end()！千万不能写成i <= vec.end()！

笔者在这上面调试了半个小时，硬是没找出问题所在，各位猜怎么着？笔者去问了ChatGPT才知道答案（笑）

以下附上ChatGPT的解释：

The loop should not go beyond q.end() as it points to the element after the last element of the deque (similarly to an “end” pointer in C++ STL).

意思为如果使用i<=vec.end()，会造成迭代器越界问题，从而造成一些未知的错误

迭代器就类似一个指针，访问地址中的内容时需要*i。

迭代器也可以进行一些逻辑运算，例如上面这段代码中的i!=vec.end()。

同样支持例如+=、++、--等运算。

当然这个是最常用的正向迭代器，还有反向迭代器、常量正向迭代器、常量反向迭代器。

反向迭代器在使用++等运算的时候是向前一个目标移动，常量正向、反向迭代器就是指向固定的元素而无法改变的迭代器。

三、常用容器介绍

以下这个篇章将介绍vector、stack、queue&priority_queue、deque、map、multimap、string容器的用法。

函数仅介绍了一些很常用的函数，例如cbegin、cend便不在讲解，如有需要请查阅C++ STL文档。

1.vector

此容器相当于一个可变的数组，用以替代传统的int a[1000];的数组声明方式，节省空间。

引入头文件：

1
#include <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 <vector>
#include <iostream>
using namespace std;
int main()
{
    vector<int> a{1, 2, 3, 4, 5}, b{1, 2, 3}; // 声明两个vector变量a,b
    vector<int>::iterator i, j;
    i = a.begin();    // begin函数返回第一个元素的迭代器
    j = a.end();      // end函数返回最后一个元素的迭代器
    int n = a.size(); // size函数返回容器大小
    if (a.empty() == false)
    {                             // empty函数返回一个bool值，用以确定容器非空
        a.reserve(20);            // 将容器的大小扩大到20个元素(若容器大于20个元素，则此命令不执行)
        a.insert(a.begin(), 100); //	在a.begin()后面插入一个int值为100的元素
        a.erase(a.end());         // 删除a.end()上的元素
        a.push_back(101);         // 在数组末尾插入一个int值为101的元素
        a.pop_back();             // 删除最后一个元素
        b.clear();                // 清空b容器中的所有元素
        swap(a, b);               // 交换a,b容器中的内容
    }
    for (i = b.begin(); i != b.end(); i++)
        cout << *i << " ";
    cout << endl;
    return 0;
}

以上程序简单介绍了vector的简单用法，输出结果：

1
100 1 2 3 4 101

2.stack

栈是一种后进先出的数据结构，一般用于深度优先搜索等算法：

栈的定义及实现- Crystal_Guang - 博客园

stack容器提供了这样的数据结构，可以避免手工模拟。

引入头文件：

1
#include <stack>

常用函数,例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stack>
#include <iostream>
using namespace std;
int main()
{
    stack<int> a, b;
    a.push(101);
    //    stack<int>::iterator i,j; stack容器没有迭代器
    //    i = a.begin();
    //    j = a.end();
    int n = a.size(); // size函数返回容器大小
    if (a.empty() == false)
    {                            // empty函数返回一个bool值，用以确定容器非空
        cout << a.top() << endl; // top函数返回栈顶元素(不弹出)
        a.pop();                 // 弹出栈顶元素
        a.push(100);             // 往栈顶加入一个元素
        swap(a, b);              // 交换a,b容器中的内容
    }
    return 0;
}

值得注意的是stack容器并不常用，因为其不能使用迭代器，遍历也较为麻烦，一般还是使用vector容器。

PS:stack不支持随机访问，即数组下标访问

2.queue&priority_queue

队列是一种先进先出的数据结构，一般用于广度优先搜索等算法中，使用queue容器：

img

优先队列，也被称之为堆，加入的每个元素都拥有不同的优先级，根据不同的优先级决定出队列的顺序。

根据不同的顺序，堆也分为大根堆和小根堆，大根堆就是将大的元素放在堆顶的堆，小根堆就是将小的元素放在堆顶的堆。

C++中priority_queue默认实现的是大根堆。

priority_queue和queue以下我将分别介绍。

两种容器引入的头文件是相同的：

1
#include <queue>

以下这个例子将介绍queue的用法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <queue>
#include <iostream>
using namespace std;
int main()
{
    queue<int> a, b;
    a.push(101);
    //    queue<int>::iterator i,j; queue容器没有迭代器
    //    i = a.begin();
    //    j = a.end();
    int n = a.size(); // size函数返回容器大小
    if (a.empty() == false)
    {                              // empty函数返回一个bool值，用以确定容器非空
        cout << a.front() << endl; // front函数返回队列头元素(不弹出)
        a.pop();                   // 弹出队列头元素
        a.push(100);               // 往队列尾加入一个元素
        swap(a, b);                // 交换a,b容器中的内容
    }
    return 0;
}

priority_queue的声明较为复杂，除了默认大根堆，也可以声明小根堆。

第一种方式较为巧妙，如果堆中的元素均为正数，那么可将其全部取相反数，这样绝对值较小的元素便会被排序在前面。再取出的时候再次取反，便可以达到小根堆的效果。

第二种方式是声明小根堆（笔者也不明白其中原理，hhhhh）：

1
priority_queue<int,vector<int>,greater<int> >q;

以下以默认的大根堆为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <queue>
#include <iostream>
using namespace std;
int main()
{
    priority_queue<int> a, b;
    a.push(101);
    a.push(102);
    a.push(103);
    //    priority_queue<int>::iterator i,j; priority_queue容器没有迭代器
    //    i = a.begin();
    //    j = a.end();
    int n = a.size(); // size函数返回容器大小
    if (a.empty() == false)
    {                              // empty函数返回一个bool值，用以确定容器非空
        cout << a.top() << endl; // top函数返回堆顶元素(不弹出)
        a.pop();                   // 弹出堆顶元素
        a.push(100);               // 往队列尾加入一个元素,此时容器会自动维护堆，始终是最大的元素保持在堆顶
        swap(a, b);                // 交换a,b容器中的内容
    }
    return 0;
}

值得注意的是如果使用的是priority_queue，那么返回栈顶元素是top函数，而并非front函数；如果是queue那么返回队列头元素是front函数，而并非top函数。

PS:priority_queue与queue均不支持随机访问，即数组下标访问

3.deque

双端队列是队列的进阶版本，队列是队列头弹出元素，队列尾加入元素；双端队列两端都可以加入与弹出元素。

值得注意的是queue、priority_queue均为deque的某种变种，且deque相较之而言可以使用迭代器进行遍历，也可以使用数组下标进行随机访问，因而实际应用中，笔者以为deque是更为灵活更为实用的一种容器。

使用deque容器时一定要小心，因为大部分vector容器适用的insert、erase等函数在deque也可以适用，但是这些函数的运用可能会破坏其作为双端队列的性质，要谨慎使用，因此如下的例子中将不再介绍与vector相同的函数

引入头文件：

1
#include <deque>

以下这个例子将介绍deque的应用：

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 <deque>
#include <iostream>
using namespace std;
int main()
{
    deque<int> a{1, 2, 3, 4, 5}, b{1, 2, 3}; // 声明两个vector变量a,b
    deque<int>::iterator i, j;
    i = a.begin();                                // begin函数返回第一个元素的迭代器
    j = a.end();                                  // end函数返回最后一个元素的迭代器
    int n = a.size();                             // size函数返回容器大小
    cout << a.front() << " " << a.back() << endl; // front和back函数返回容器中第一个和最后一个元素
    if (a.empty() == false)
    {                      // empty函数返回一个bool值，用以确定容器非空
        a.push_back(101);  // push_back函数在队列尾部插入一个元素
        a.pop_back();      // pop_back函数在队列尾弹出一个元素
        a.push_front(102); // push_front函数在队列头插入一个元素
        a.pop_front();     // pop_front函数在队列头弹出一个元素
        b.clear();         // 清空b容器中的所有元素
        swap(a, b);        // 交换a,b容器中的内容
    }
    for (i = b.begin(); i != b.end(); i++)
        cout << *i << " ";
    cout << endl;
    return 0;
}

4.map

map 是一个关联容器，用于存储一对键值（key-value）映射，可用于哈希表等数据结构。

在这里插入图片描述

引入头文件：

1
#include <map>

以下这个例子将介绍map的应用：

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 <map>
#include <iostream>
using namespace std;
int main()
{                              
    map<string, int> a{{"a", 1}, {"b", 2}, {"c", 3}}; // 建立一个string->int的映射，初始化为a->1,b->2,c->3
    map<string,int> b;
    map<string, int>::iterator i, j;
    i = a.begin();                           // begin函数返回第一个元素的迭代器
    j = a.end();                             // end函数返回最后一个元素的迭代器
    int n = a.size();                        // size函数返回容器大小
    cout << a["a"] << " " << a["b"] << endl; // 输出b容器中"a","b"对应的值
    if (a.empty() == false)
    {                      // empty函数返回一个bool值，用以确定容器非空
        a.erase("c");        // 删除a容器中"c"指向的元素
        a.insert({"d", 4}); // 向a容器中插入一个元素"d"->4
        a.insert(make_pair("e", 5)); // 向a容器中插入一个元素"e"->5
        a.swap(b);          // 交换a,b容器中的内容
        a.clear();         // 清空b容器中的所有元素
    }
    for (i = b.begin(); i != b.end(); i++)
        cout << i->first << " " << i->second << endl; // 输出b容器中的所有元素
    cout << endl;
    return 0;
}

PS:因为在map里面存储的是一个个pair容器，所以a.insert(make_pair("e", 5));也可以起到插入一个键值映射的效果。

5.multimap

map容器只能一个key对应一个实值，而multimap则可以一个key对应多个实值。

和 map 容器相比，multimap 未提供 at() 成员方法，也没有重载 [] 运算符。这意味着，map 容器中通过指定键获取指定指定键值对的方式，将不再适用于 multimap 容器。其实这很好理解，因为 multimap 容器中指定的键可能对应多个键值对，而不再是 1 个。

引入头文件：

1
#include <map>

以下这个例子将介绍multimap的应用：

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
#include <map>
#include <iostream>
using namespace std;
int main()
{
    multimap<string, int> a{{"a", 1}, {"b", 2}, {"b", 3}, {"c", 100}}; // 建立一个string->int的映射，初始化为a->1,b->2,c->3
    multimap<string, int> b;
    multimap<string, int>::iterator i, j;
    i = a.begin();    // begin函数返回第一个元素的迭代器
    j = a.end();      // end函数返回最后一个元素的迭代器
    int n = a.size(); // size函数返回容器大小
    // multimap因为可能一个key对应多个值，所以不能使用[]访问
    // cout << a["a"] << " " << a["b"] << endl;
    if (a.empty() == false)
    {                                // empty函数返回一个bool值，用以确定容器非空
        a.erase("c");                // 删除a容器中"c"指向的元素
        a.insert({"d", 4});          // 向a容器中插入一个元素"d"->4
        a.insert(make_pair("d", 5)); // 向a容器中插入一个元素"e"->5
        a.swap(b);                   // 交换a,b容器中的内容
        a.clear();                   // 清空b容器中的所有元素
    }
    for (i = b.begin(); i != b.end(); i++)
        cout << i->first << " " << i->second << endl; // 输出b容器中的所有元素
    cout << endl;
    multimap<string, int>::iterator begin, end;
    begin = b.lower_bound("b"); // lower_bound函数返回第一个大于等于指定值的元素的迭代器
    end = b.upper_bound("b");   // upper_bound函数返回第一个大于指定值的元素的迭代器
    for (i = begin; i != end; i++)
        cout << i->first << " " << i->second << endl; // 输出b容器中"b"值对应的的所有元素
    return 0;
}

6.string

C风格的字符串（char a[1000];）相当于一个普通的数组，使用比较复杂，许多东西例如插入删除都需要手工模拟，因此C++在STL中引入了一个string的字符串类。

字符串在日常应用中较为普遍，因此笔者将详细介绍string的用法

引入头文件：

1
#include <string>

声明并初始化的几种方法：

1
2
3
string str1;               // 定义一个空字符串str1
string str2("HelloWorld"); // 定义一个字符串str2并初始化为"HelloWorld"
string str3(5, 'a');       // 定义一个字符串str3并初始化为"aaaaa"

可使用一些基本操作符：

1
2
3
4
5
6
string str("HelloWorld");
string str1("iloveyou");
cout << str[3] << endl;   // 输出str的第四个字符(第一个字符从0开始计数)
string str2 = str + str1; // 字符串连接
cout << str2 << endl;
printf("%s", str2); // 使用cout或者printf直接输出输出str2

拼接、查找、替换、删除、提取子串等操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string str("HelloWorld");
string str1("iloveyou");

int len=str.length(); // 返回str字符串的长度

str.append(str1, 3, 4); // 将str1字符串的第三个位置开始的四个字符添加到str字符串的末尾

int pos1 = str.find("Hello");   // 返回str1字符串"Hello"中第一次出现的位置
int pos2 = str.find("love", 1); // 返回str1字符串从第二个位置开始查找"love"中第一次出现的位置

str.replace(1, 3, "love"); // 将str字符串从第二个位置开始的三个字符替换为"love"

str.erase(1, 3); // 将str字符串从第二个位置开始的三个字符删除

str.insert(1, "love"); // 将"love"插入到str字符串的第二个位置
str.insert(5, 2, 'a'); // 将两个'a'插入到str字符串的第六个位置

string str3=str.substr(1,3); // 返回str字符串从第二个位置开始的三个字符

其余的函数，例如empty(),size(),clear()等函数均可以在string类中使用

迭代器也可以在string类中应用。

四、后记

C++的STL也是一个比较复杂的特性，为大程序的编写提供了很多便利。以上笔者仅仅粗浅地介绍了很少一部分。介于笔者水平，难免有理解和描述上有疏漏或者错误的地方，欢迎共同交流。