C++ STL精通之旅：向量、集合与映射等容器详解

���录

常用容器

顺序容器

向量vector

构造

尾接 & 尾删

中括号运算符

获取长度

清空

判空

改变长度

提前分配好空间

代码演示

运行结果

关联容器

集合set

构造

遍历

其他

代码演示

运行结果​编辑

映射map

常用方法

构造

遍历

其他

代码演示1​编辑

运行结果1

代码演示2

运行结果2

 string map 

代码演示3

运行结果3

 mp没赋初值，默认为0

代码演示4

运行结果4

容器适配器

栈stack

常用方法

代码演示1

运行结果1

vector也可以当栈来用

代码演示2

运行结果2

队列queue

常用方法

代码演示

运行结果

优先队列priority_queue

常用方法

构造

其他

大顶堆

代码演示1

运行结果1

 小顶堆

代码演示2

运行结果2

修改堆顶元素

代码演示3 

运行结果3

字符串

string (basic_string)

常用方法

构造

输入输出

其他

数值与字符串互转（C++11）

尾接字符串一定要用 +=

代码演示​

运行结果

对与元组

二元组pair

常用方法

构造

赋值

取值

判同

​适用场景

代码演示

运行结果

---

STL

STL 作为一个封装良好，性能合格的 C++ 标准库，在算法竞赛中运用极其常见。灵活且正确使用 STL 可以节省非常多解题时间，这一点不仅是由于可以直接调用，还是因为它封装良好，可以让代码的可读性变高，解题思路更清晰，调试过程往往更顺利。

不过 STL 毕竟使用了很多复杂的结构来实现丰富的功能，它的效率往往是比不上自己手搓针对特定题目的数据结构与算法的。因此，STL 的使用相当于使用更长的运行时间换取更高的编程效率。因此，在实际比赛中要权衡 STL 的利弊，不过这一点就得靠经验了。

接下来，博主会分享在算法竞赛中常用的 STL 容器，对于算法，函数和迭代器，就不着重展开讲了。

C++ 标准模板库 (STL, Standard Template Library)：包含一些常用数据结构与算法的模板的 C++ 软件库。其包含四个组件——算法 (Algorithms)、容器 (Containers)、仿函数 (Functors)、迭代器 (Iterators).

示例：

• 算法（Algorithms）：STL中的算法是一组对容器进行操作的函数，它们独立于任何特定的数据结构，可以用于执行各种任务，如搜索、排序、复制和修改容器中的元素。这些算法是泛型的，意味着它们可以用于不同类型和容器的数据，体现了泛型编程的思想。

  • 容器（Containers）：容器是用来存储数据的对象，例如数组、队列、链表、集合等。STL提供了多种容器类型，每种都设计用于特定类型的数据访问和存储。容器管理对象的集合，并提供插入、删除和遍历元素等操作。

    • 仿函数（Functors）：仿函数是重载了操作符()的类或类对象，它可以像函数一样被调用。在STL中，仿函数通常用作算法的参数，允许用户自定义算法的行为，使得算法更加灵活和可配置。

      • 迭代器（Iterators）：迭代器是一种类似于指针的对象，用于在容器中遍历元素。每个容器都定义了相应的迭代器类型，迭代器提供了读取和修改容器元素的方法。迭代器分为输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器，不同类型的迭代器支持不同的操作。

        常用容器

        顺序容器

        • 向量vector

          头文件：#include

          连续的顺序的储存结构（和数组一样的类别），但是有长度可变的特性。

          构造

          vector arr(长度, [初值])

          时间复杂度：O(n)

          尾接 & 尾删

          • push_back(元素)：在 vector 尾接一个元素，数组长度 +1.

          • pop_back()：删除 vector 尾部的一个元素，数组长度 -1.

            时间复杂度：均摊 O(1)

            中括号运算符

            和一般数组一样的作用

            时间复杂度：O(1)

            获取长度

            .size()

            获取当前 vector 的长度

            时间复杂度：O(1)

            清空

            .clear()

            清空 vector

            时间复杂度：O(n)

            判空

            .empty()

            如果是空返回 true 反之返回 false.

            时间复杂度：O(1)

            改变长度

            .resize(新长度, [默认值])

            修改 vector 的长度

            • 如果是缩短，则删除多余的值

            • 如果是扩大，且指定了默认值，则新元素均为默认值（旧元素不变）

              时间复杂度：O(n)

              提前分配好空间

              代码演示

              运行结果

              关联容器

              • 集合set

                头文件#include

                提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。

                集合三要素	解释	set	multiset	unordered_set
                确定性	一个元素要么在集合中，要么不在	✔	✔	✔
                互异性	一个元素仅可以在集合中出现一次	✔	❌（任意次）	✔
                无序性	集合中的元素是没有顺序的	❌（从小到大）	❌（从小到大）	✔

                构造

                set st

                • 类型：要储存的数据类型

                • 比较器：比较大小使用的比较器，默认为 less，可自定义

                  对于需要自定义比较器的情况，涉及一些初学时容易看迷糊的语法（重载小括号运算符 / lambda 表达式），在此就不展开讲了。

                  遍历

                  其他

                  作用	用法	示例
                  插入元素	.insert(元素)	st.insert(1);
                  删除元素	.erase(元素)	st.erase(2);
                  查找元素	.find(元素)	auto it = st.find(1);
                  判断元素是否存在	.count(元素)	st.count(3);
                  查看大小 / 清空 / 判空	略	略

                  增删查时间复杂度均为 O(\log n)

                  代码演示

                   运行结果

                  • 映射map

                    头文件#include

                    提供对数时间的有序键值对结构。底层原理是红黑树。

                    映射：                                        

                                                                                    ​   

                    性质	解释	map	multimap	unordered_map
                    互异性	一个键仅可以在映射中出现一次	✔	❌（任意次）	✔
                    无序性	键是没有顺序的	❌（从小到大）	❌（从小到大）	✔

                    常用方法

                    构造

                    map mp

                    • 键类型：要储存键的数据类型

                    • 值类型：要储存值的数据类型

                    • 比较器：键比较大小使用的比较器，默认为 less，可自定义

                      遍历

                      其他

                      作用	用法	示例
                      增 / 改 / 查元素	中括号	mp[1] = 2;
                      查元素（返回迭代器）	.find(元素)	auto it = mp.find(1);
                      删除元素	.erase(元素)	mp.erase(2);
                      判断元素是否存在	.count(元素)	mp.count(3);
                      查看大小 / 清空 / 判空	略	略

                      增删改查时间复杂度均为 O(\log n)

                      代码演示1
                      

                       运行结果1

                       代码演示2

                       

                        运行结果2

                       string map 

                      代码演示3

                       运行结果3

                       mp没赋初值，默认为0

                      代码演示4

                       运行结果4

                      容器适配器

                      • 栈stack

                        头文件#include

                        通过二次封装双端队列 (deque) 容器，实现先进后出的栈数据结构。

                        常用方法

                        作用	用法	示例
                        构造	stack stk	stack stk;
                        进栈	.push(元素)	stk.push(1);
                        出栈	.pop()	stk.pop();
                        取栈顶	.top()	int a = stk.top();
                        查看大小 / 清空 / 判空	略	略

                        代码演示1

                        运行结果1

                        vector也可以当栈来用

                        代码演示2

                        运行结果2

                        • 队列queue

                          头文件#include

                          通过二次封装双端队列 (deque) 容器，实现先进先出的队列数据结构。

                          常用方法

                          作用	用法	示例
                          构造	queue que	queue que;
                          进队	.push(元素)	que.push(1);
                          出队	.pop()	que.pop();
                          取队首	.front()	int a = que.front();
                          取队尾	.back()	int a = que.back();
                          查看大小 / 清空 / 判空	略	略

                          代码演示

                          运行结果

                          • 优先队列priority_queue

                            头文件#include

                            提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。

                            常用方法

                            构造

                            priority_queue pque

                            • 类型：要储存的数据类型

                            • 容器：储存数据的底层容器，默认为 vector，竞赛中保持默认即可

                            • 比较器：比较大小使用的比较器，默认为 less，可自定义

                              priority_queue pque1;                            // 储存int的大顶堆priority_queue pque2; // 储存int的小顶堆

                              其他

                              作用	用法	示例
                              进堆	.push(元素)	que.push(1);
                              出堆	.pop()	que.pop();
                              取堆顶	.top()	int a = que.top();
                              查看大小 / 判空	略	略

                              进出队复杂度 O(\log n)，取堆顶 $O(1).

                              大顶堆

                              代码演示1

                               运行结果1

                               小顶堆

                              代码演示2

                              运行结果2

                              修改堆顶元素

                              代码演示3 

                              运行结果3

                              字符串

                              • string (basic_string)

                                头文件#include

                                顾名思义，就是储存字符串的。

                                常用方法

                                构造

                                输入输出

                                C++

                                C

                                其他

                                作用	用法	示例
                                修改、查询指定下标字符	[]	s[1] = 'a';
                                是否相同	==	if (s1 == s2) ...
                                字符串连接	+	string s = s1 + s2;
                                尾接字符串	+=	s += "awa";
                                取子串	.substr(起始下标, 子串长度)	string sub = s.substr(2, 10);
                                查找字符串	.find(字符串, 起始下标)	int pos = s.find("awa");

                                数值与字符串互转（C++11）

                                源	目的	函数
                                int / long long / float / double / long double	string	to_string()
                                string	int	stoi()
                                string	long long	stoll()
                                string	float	stof()
                                string	double	stod()
                                string	long double	stold()

                                尾接字符串一定要用 +=

                                 代码演示

                                 运行结果

                                对与元组

                                • 二元组pair

                                  头文件#include

                                  顾名思义，就是储存二元组的。

                                  常用方法

                                  构造

                                  pair pr

                                  • 第一个值类型：要储存的第一个值的数据类型

                                  • 第二个值类型：要储存的第二个值的数据类型

                                    赋值

                                    老式

                                    列表构造 C++11

                                    取值

                                    直接取值

                                    • 取第一个值：.first

                                    • 取第二个值：.second

                                      结构化绑定 C++17

                                      判同

                                      直接用 == 运算符

                                      
                                      适用场景

                                      所有需要二元组的场景均可使用，效率和自己定义结构体差不多。

                                      代码演示

                                       运行结果

                                       

                                      希望对你有帮助！加油！

                                      若您认为本文内容有益，请不吝赐予赞同并订阅，以便持续接收有价值的信息。衷心感谢您的关注和支持！