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

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



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>

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

构造

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>

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

集合三要素 解释 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>

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

映射:                                        

                                                                 

性质 解释 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 <stack>

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

常用方法
作用 用法 示例
构造 stack<类型> stk stack<int> stk;
进栈 .push(元素) stk.push(1);
出栈 .pop() stk.pop();
取栈顶 .top() int a = stk.top();
查看大小 / 清空 / 判空
代码演示1

运行结果1

vector也可以当栈来用
代码演示2

运行结果2

  • 队列queue

头文件#include <queue>

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

常用方法
作用 用法 示例
构造 queue<类型> que queue<int> que;
进队 .push(元素) que.push(1);
出队 .pop() que.pop();
取队首 .front() int a = que.front();
取队尾 .back() int a = que.back();
查看大小 / 清空 / 判空
代码演示

运行结果

  • 优先队列priority_queue

头文件#include <queue>

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

常用方法
构造

priority_queue<类型, 容器, 比较器> pque

  • 类型:要储存的数据类型
  • 容器:储存数据的底层容器,默认为 vector<类型>,竞赛中保持默认即可
  • 比较器:比较大小使用的比较器,默认为 less<类型>,可自定义
priority_queue<int> pque1;                            // 储存int的大顶堆
priority_queue<int, vector<int>, greater<int>> 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<char>)

头文件#include <string>

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

常用方法
构造

输入输出

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 <utility>

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

常用方法
构造

pair<第一个值类型, 第二个值类型> pr

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

赋值

老式

列表构造 C++11

取值

直接取值

  • 取第一个值:.first
  • 取第二个值:.second

结构化绑定 C++17

判同

直接用 == 运算符

适用场景

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

代码演示

运行结果

希望对你有帮助!加油!

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

目录
相关文章
|
9天前
|
存储 C++ 容器
C++STL(标准模板库)处理学习应用案例
使用C++ STL,通过`std:vector`存储整数数组 `{5, 3, 1, 4, 2}`,然后利用`std::sort`进行排序,输出排序后序列:`std:vector&lt;int&gt; numbers; numbers = {5, 3, 1, 4, 2}; std:sort(numbers.begin(), numbers.end()); for (int number : numbers) { std::cout &lt;&lt; number &lt;&lt; &quot; &quot;; }`
15 2
|
22小时前
|
程序员 索引 Python
06-python数据容器-set(集合)入门基础操作
06-python数据容器-set(集合)入门基础操作
|
9天前
|
存储 算法 C语言
【C++初阶】8. STL初阶 + String类
【C++初阶】8. STL初阶 + String类
45 1
|
20天前
|
算法 C++ 容器
【C++练级之路】【Lv.10】【STL】priority_queue类和反向迭代器的模拟实现
【C++练级之路】【Lv.10】【STL】priority_queue类和反向迭代器的模拟实现
|
20天前
|
C++ 容器
【C++练级之路】【Lv.9】【STL】stack类和queue类的模拟实现
【C++练级之路】【Lv.9】【STL】stack类和queue类的模拟实现
|
1月前
|
Java Go 开发者
Docker容器技术简介及其与Go语言的结合点
【2月更文挑战第23天】本文首先概述了Docker容器技术的核心概念和优势,接着探讨了Go语言与Docker容器技术的结合点。通过阐述Docker的轻量级、可移植性和版本控制等特性,以及Go语言在容器化应用中的优势,本文旨在说明两者结合能够实现更高效、灵活的应用开发和部署。
|
1月前
|
Oracle 关系型数据库 数据库
|
7天前
|
Linux Docker 容器
docker 容器常用命令
docker 容器常用命令
11 0
|
16天前
|
Kubernetes 网络协议 Docker
Docker 容器的DNS
Docker 容器的DNS
23 1
|
18天前
|
关系型数据库 MySQL Nacos
【深入浅出Nacos原理及调优】「实战开发专题」采用Docker容器进行部署和搭建Nacos服务以及“坑点”
【深入浅出Nacos原理及调优】「实战开发专题」采用Docker容器进行部署和搭建Nacos服务以及“坑点”
42 1