幻冰の博客

一条咸鱼的垂死挣扎

算法竞赛入门指南_0x04 使用 STL

STL 简介

标准模板库(英文:Standard Template Library,缩写:STL),是一个C++软件库,大量影响了C++标准程序库但并非是其的一部分。其中包含4个组件,分别为算法、容器、函数、迭代器。

使用 STL 能极大提升编码效率,尤其在竞赛当中合理运用 STL 中的容器和算法能能使我们将注意力更多的关注到题目本身,而不会在构建数据结构上浪费时间。STL 中还有一个东西叫做空间配置器,他比手动申请释放内存高效许多。STL 中的其他内容会在下面逐步介绍。

下面这个表格列举了 STL 中常用的容器,容器实质上是一组相同类型对象的集合,但它不仅仅是数组那么简单,它实现了比数组更复杂的数据结构,能够实现更复杂的功能。

表格中只需要关注容器名称、特征、搜寻速度、头文件,在使用相关容器之前必须包含相应头文件。

除了表格中罗列的容器外还有基于 deque 实现的 stack (栈) 、queue (队列),基于堆(heap)实现的 priority_queue (优先队列)。其中 stack 的头文件是 <stack> ,queue 与 priority_queue 的头文件是 <queue>。准确的来说这三个是容器适配器,是对容器的进一步封装。

vector

vetor 类似于数组,但是 vector 的长度是可变的。以形如 vector<int> v; 来使用 vector ,其中 <>之间包含的是元素类型,可以是基本数据类型也可以是自定义结构体,也可以是另一个 vector ,如 vector<vector<int> > ,两个 > > 一定要分开写,否则会被编译器认为是输入流。

其他容器也一样可以是任意的数据类型,若是需要排序的容器则需要重载一些运算符,关于重载会在以后的博文中讲到,这里仅作了解,这篇博文也不会用到重载相关内容。

在定义 vector 的时候还可以指定大小,如 vector<int> v(1000)这样就能避免在插入时大量的内存拷贝,因为在不定长度的 vector 插入元素时会将原来的数据拷贝到另外一个更大的内存空间里。

vector 有如下几个常用基本操作

  1. [] – 获取或设置指定下标的元素,用法与数组相同
  2. push_back() – 将元素插入到 vector 尾部
  3. pop_back() – 移除最后一个元素
  4. insert() – 将元素插入指定位置
  5. erase() – 从 vector 中删除指定元素或者指定范围的元素
  6. swap() – 交换两个元素的值
  7. clear() – 清空 vector
  8. size() – vector 中元素个数

下面的代码用到了 begin()end()这是迭代器(iterator),又被称为游标(cursor),类似指针,会在后面讲解

上面的代码运行结果为

从 STL 开始将接触一个新的概念,迭代器。迭代器和指针类似,不同的是指针运算建立在内存连续的基础上,而迭代器无需关心容器对象的内存分配的实现细节。并且迭代器是安全的,他不能访问不是分配给容器的内存。下面给出使用迭代器遍历 vector 的一个例子

其中  vector<int> 指明了迭代器的类型,从 v.begin() 这个迭代器开始一直到 v.end() 前结束。 vector<int>::iterator 可以替换为 auto ,编译器将自动判断迭代器类型。注意一点,程序设计大部分使用左闭右开区间,正如这个例子中 v 的元素范围是 [v.begin(),v.end()),使用这样的规定会使一些算法更容易实现,这将在以后学习的算法中体现出来。

如上的写法也是正确的。

set

set 正如他的名字一样——集合,基本的 set 与数学上的集合有一样的特性无序性、互异性、确定性。但是在 STL 中可以指定集合的排序方式

set 基本操作有

  1. begin() – 返回第一个元素的迭代器
  2. end() – 返回最后一个元素之后的迭代器
  3. size() – 返回 set 中元素个数
  4. empty() – 返回 set 是否为空
  5. erase(g) – 移除元素 g
  6. clear() – 清空集合
  7. find(g) – 查找元素 g,如果找到返回指向 g 的迭代器,否则返回迭代器 end()
  8. count(g) – 计数元素 g ,若 g 存在返回 1 ,不存在返回 0

可以通过  set <int, greater <int> > s1; 来指定 set 中元素递减排列,其中 greater<int> 是模板(template) ,包含在头文件 <functional> ,其实 set 默认是 set <int, less <int> > s1;,递增的元素排列方式。在算法竞赛中不大量涉及模板,在这里就不做详细解释,有兴趣可自行查阅资料。

STL 中除了 set 外还有 multiset ,它允许存在重复的元素,使用方法与 set 基本一致,不再赘述。

map

map 既是映射,同数学中的映射类似 map 是元素一一对应的,一个元素只能对应一个元素,称之为键值对。通过键(key)可以访问值(value),而反过来则不行。

值得注意的一点是 map 的迭代器指向一个 pair 的,pair 有两个成员 first 和second ,下面是 pair 使用实例

如果是指向 pair 的迭代器则需要将 . 替换为 ->。map 的迭代器与 vector 和 set 大致相同,这里不再赘述。

map 基本操作

  1. [k] – 根据键 k 来查询或设置值,如果键 k 不存在则会创建键 k
  2. find(k) – 根据键 k 查询,如果存在则返回指向这个键值对的迭代器,否则返回指向 end() 的迭代器。
  3. count(v) – 返回 map 中值 v 的个数

map 与 set 一样默认递增排列 也可以通过使用 greater<int> 来实现递减排列

queue

queue 意为队列,是一种先进先出的数据结构(First In First Out,FIFO),使用队列存取数据元素时,数据元素只能从表的一端进入队列,另一端出队列。数据元素全部由队尾陆续进队列,由队头陆续出队列。

queue 基本操作

  1. empty() – 返回队列是否为空
  2. size() – 返回队列的大小
  3. front() – 返回队列中第一个元素
  4. back() – 返回队列中最后一个元素
  5. push(g) – 将元素 g 放入队列尾部
  6. pop() – 将第一个元素弹出队列

priority_queue

priority_queue 为优先队列,虽然他和队列很像但队列和优先队列在底层实现上完全不同,现阶段还无需了解优先队列是如何实现的,只要知道两者不同就可以令人。在优先队列中每次取出来的元素是按照递增或者递减的方式排列的第一个,除此之外优先队列与队列操作一致。

priority_queue 中元素默认是递减排列的,可以通过使用  priority_queue<int,vector<int>,greater<int> >pq;来使 priority_queue 中的元素从递增排列。

stack

stack 意为栈,与 queue 一样也是使用非常频繁的数据结构,stack 是一种先进后出(First In Last Out,FILO)的数据结构,栈只能从表的固定一端对数据进行插入和删除操作,另一端是封死的。

由于栈只有一边开口存取数据,称开口的那一端为“栈顶”,封死的那一端为“栈底”

使用栈存储数据元素,对数据元素的“存”和“取”有严格的规定:数据按一定的顺序存储到栈中,当需要调取栈中某数据元素时,需要将在该数据元素之后进栈的先出栈,该数据元素才能从栈中提取出来。

stack 的基本操作

  1. empty() – 返回栈是否为空
  2. size() – 返回栈的大小
  3. top() – 返回栈顶元素
  4. push(g) – 将元素 g 压入栈顶
  5. pop() – 将栈顶元素弹出栈

sort()

sort() 是 STL 中的排序函数,它包含在头文件 <algorithm> 中,他可以对任何数据类型进行排序(自定义结构体需要提供比较函数,详见下面的代码),sort 可以看作是快速排序(一种优秀的排序算法),它的复杂度是 O(N·log(N)) 而冒泡排序复杂度是 O(N·N) ,N 是排序元素的个数。

上图给出 sort 是如何工作的,所以前面说的是可看作快速排序

sort 有三个参数

  1. 开始排序元素的地址或者迭代器
  2. 最后一个要排序元素之后的地址或者迭代器
  3. 比较函数,不写则默认从小到大排序,自定义结构体必须有

运行结果

后记

STL 对于算法竞赛十分重要,务必掌握。尤其是栈、优先队列、映射。学习 STL 可以说是入门算法的第一课,从这里开始接触的是真正的算法而非简单的进行模拟计算。

参考

  1. 标准模板库 – 维基百科,自由的百科全书
  2. 跟我学STL系列(1)——STL入门介绍 – Learning hard – 博客园
  3. C++ Archives – GeeksforGeeks
  4. 队列(Queue):“先进先出”的数据结构
  5. 栈(Stack)的概念和应用及C语言实现
  6. C++一道深坑面试题:STL里sort算法用的是什么排序算法? – 知乎

原创文章,转载请注明: 转载自鱼塘

本文链接地址: 算法竞赛入门指南_0x04 使用 STL

点赞
  1. 啦啦啦说道:

    :razz: :razz: 这个作者很。。。。

    1. 幻冰说道:

      是博主😒

    2. 幻冰说道:

      被回复会收到邮件

发表评论

电子邮件地址不会被公开。 必填项已用*标注

1 × 2 =