常用的STL 汇总

STL是C++标准库的一部分,中文翻译为“标准模板库”,其中包含了一些常用的算法与数据结构,他们通常存储在对应的头文件中如<vector> <stack> <queue>,或者是直接使用<bits/stdc++.h>。
原本的训练内容是栈和队列,但这两种数据结构属于竞赛中 常用的STL ,所以这里进行了一些扩展。下面将简单介绍几种 常用的STL 容器,内容以概括汇总为主,并不涉及很多原型以及特殊用法。
如无特殊说明,以下默认使用x作为变量,使用it指代迭代器。

基本概念

迭代器iterator

STL中存在迭代器的概念,它类似指针操作,指向容器中的某个元素。同样可以使用“*”解除引用,在不同的STL中还分为“随机访问迭代器”和“双向访问迭代器”等等,他们在使用上有所不同。

随机访问迭代器

代表容器:vector
有类似指针的操作,可以对迭代器进行加减从而实现移动;也可以两个迭代器相减获得两个元素的位置。
以vector为例,遍历并输出:

vector a;
for(vector::iterator i=a.begin();i!=a.end();i++)
{
    cout<<*i<<" ";
}
//或者是:

vector::iterator it=a.begin();
for(int i=0;i<a.size();i++)
{
    cout<<it[i];
}

双向访问迭代器

代表容器:set
只能对迭代器进行++或者–操作,不能像随机访问迭代器一样跳跃访问或者是赋值。
像set这样内部有序的容器,++和–操作代表的是按照容器排序规则的上一个元素或者是下一个元素。

容器
对应的迭代器类型
array
随机访问迭代器
vector
随机访问迭代器
deque
随机访问迭代器
list
双向迭代器
set / multiset
双向迭代器
map / multimap
双向迭代器
forward_list
前向迭代器
unordered_map / unordered_multimap
前向迭代器
unordered_set / unordered_multiset
前向迭代器
stack
不支持迭代器
queue
不支持迭代器

For each 遍历容器

我们可以使用下面的方式遍历大多数容器;

map<string,int> m;
for(auto i:m)
{
    cout<<i.first<<" "<<i.second<<endl;
}

 

通用操作

以下是所有容器都支持的操作,之后将不再列出这两个操作:

a.size();//返回容器中元素的数量
a.empty();/如果容器为空返回true,否则返回false

以下一些成员函数经常出现,并且功能类似,这里提前进行介绍,在之后的内容中不再详述:

a.begin();//返回容器首元素的迭代器
a.end();//返回容器最后一个元素之后的迭代器,a.end()-1才是最后一个元素的迭代器
a.clear();//清空容器
a.push(x);//向容器中添加一个元素,类似的还有push_back和pop_front
a.pop();//将容器中的元素弹出,类似的还有pop_back和pop_front

vector向量/动态数组

vector实现的是基于倍增的思想。.

 

一般声明的数组长度是固定的,如果使用链表储存,不断动态申请内存会降低程序运行的效率,并且程序的编写会变得更加复杂,因此我们常使用vector来当作动态数组。在底层实现中,vector也是通过动态申请内存的方式来实现动态存储。当vector被存满的时候会进行扩容操作,基本的过程如下:

  1. 重新申请一个更大的空间。
  2. 将原数据存入新空间。
  3. 释放原有空间。

因为扩容后数据存储到了一个新空间中,因此原有的迭代器、指针和引用有可能会失效,同时为了避免反复申请空间,不同的编译器会申请不同的额外空间,通常是之前数据的两倍。

将所有数据放入新空间的操作尽管花费了更多的时间,但是可以保证内存空间的连续性,这也是为什么vector可以支持随机访问。

常用的成员函数

a.push_back(x);
a.pop_back();
a.clear();
a.push();
a.pop();
a.begin();
a.end();

常用用法

  1. 使用下标进行访问元素
  2. 存储邻接表
  3. hash的拉链法

deque双端队列

参考:C++ STL deque容器底层实现原理(深度剖析) (biancheng.net)

deque 和vector有些类似,都是通过动态申请空间实现。

不同的是deque存储数据的空间是由一段一段等长的连续空间构成,各段空间之间并不一定是连续的,可以位于在内存的不同区域。然后使用一个map数组记录每一段的地址,由此保证整体有序。

当要在队首或者队尾插入新的数据时,只需要新申请一段空间,然后将其地址存入map数组中。

当map数组存满以后使用类似vector的方式重新申请空间并转移数据。

deque实例

deque实例

常用的成员函数

q.push_back(x);
q.push_front(x);
q.pop_back();
q.pop_front();
q.front();//返回队首元素
q.back();//返回队尾元素
q.clear();
q.begin();
q.end();

常用用法

stack、list、queue的底层均使用了deque实现。

stack栈

栈是一种基础的数据结构,也被称为FILO表(先进后出),底层使用deque实现。

常用的成员函数

s.push(x);
s.pop();//弹出栈顶元素
s.top();//返回栈顶元素的引用

注意,栈并没有提供迭代器可以遍历所有元素,也没有提供clear来快速清空。

queue队列

队列是一种基础数据结构,也被称为FIFO表(先进先出),底层使用deque实现。

常用的成员函数

q.push(x);
q.pop();
q.front();//返回队首元素
q.back();//返回队尾元素

常用用法

在进行广度优先搜索时会使用到queue,有些算法可能会使用到堆优化,则需要使用下面的priority_queue

priority_queue优先队列

优先队列底层通过vector实现,并在其内部维护了一个堆,因此可以保证top的元素为最大(最小)。
我们在大多数情况下可以使用优先队列来代替堆。

声明方式

priority_queue q;//默认大根堆
priority_queue <int,vector,greater> q;//声明大根堆
priority_queue <int,vector,less> q;//声明小根堆

对于大根堆和小根堆,还可以通过结构体的重载运算符实现,但如果不存储结构体变量,上述的声明方式更加简洁.

常用的成员函数

q.push(x);
q.pop();
q.top();//返回堆顶元素,也就是最大值(最小值)

常用用法

  1. 代替堆
  2. 需要维护最大或者最小值的情况

扩展操作:懒惰删除法

相比于自己手写的堆,STL的灵活性并没有那么高,不能进行单点修改、单点删除等。为此我们可以使用懒惰删除法。
我们采取的策略是额外记录删除信息,当我们从堆顶取出来的时候再判断元素是否已经被删除,也就是说删除操作要在堆顶进行。
(示例暂缺)

set/multiset集合

这两个容器维护的是一个集合,前者不允许集合中存在相同的元素,后者允许相同的元素存在。

在集合中的元素都是有序的(默认从小到大,可以重载运算符)。

常用的成员函数

s.clear();
s.begin();
s.end();
s.insert(x);//插入一个元素
s.find(x);//查找等于x的元素并返回他的迭代器,如果不存在则返回s.end();
s.lower_bound(x);//查找大于等于x的元素中最小的一个,并返回指向他的迭代器
s.upper_bound(x);//查找大于x的元素中最小的一个,并返回指向他的迭代器
s.erase(it);//删除it指向的元素
s.erase(x);//删除所有等于x的元素(multiset)
s.count(x);//计算集合中x的数量(multiset)

关于lower_bound和upper_bound

这两个函数的区别在于是否取到等于号,也常被用在二分中。

map/multimap映射

该容器存储一个键值对(key-value)

常用的成员函数

m.clear();
m.begin();
m.end();
m.insert(make_pair(key,value));
m.erase(it);
m.erase(key);//以上和set功能类似
m.find(key);//查找到key所在的二元组并返回迭代器,如果不存在则返回m.end()

[ ]操作符

该容器也可以使用[ ]来访问元素,但索引不是下标,而是key值(类似PHP中Array的键值对),同时可以对其进行复制操作改变value

常用用法

当做hash表使用。

参考内容:

[1]李煜东.算法竞赛进阶指南.

[2]C语言中文网:C语言程序设计门户网站(入门教程、编程软件) (biancheng.net)

2022寒假导航

2022寒假导航 – Bulbul (bulbul559.cn)

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇