C++ 头文件系列(queue)

时间:2022-09-18 18:46:10

简介

这个头文件定义了两个跟队列有关的类----quque、priority_queue,分别实现的是队列优先队列这两个概念。 但是与这两个类模版与其它类模版(vector、array等)最大的不同是,它们是 容器适配器

容器适配器

顾名思义,容器适配器是对容器的适配,从代码层面来讲,它就是对容器的再封装。 因此,这些容器适配器实际上都是由其他容器的功能实现的。 不难看出, 容器适配器所具有的功能是内部容器功能的子集

普通的类封装一般是为了封装成特定问题领域下的类,提供特定的接口,以解决开发中遇到的实际问题为主要目的; 而作为一门语言库中的库类,它们更多考虑的是可重用性,所以库类一般封装成像stack、quque等具有抽象性的概念。

队列

你可以把队列看成一种被适配的容器,它有两个重要的特性:

  • FIFO(first-in first-out): 先入队的元素总是先出队。
  • 两端出入: 元素从一端入队,从另一端出队。

C++ 头文件系列(queue)

操作对应的成员函数

  • 入队 -> push
  • 出队 -> pop

为什么少了很多常见函数

细心的你们肯定发现了,queue类模版提供的函数很少,一些非常常见的函数都没有。 如果让我用一句话来解释的话,那就是----所有涉及头尾两端外的位置的函数,都不在队列的概念内!

因为在队列中,所有元素的存取都只能通过入队和出队操作。 如果你想获取位于中间位置的元素,那么对不起,你只能先把前面的元素取出来;如果你想对队中的元素本身进行操作,抱歉,你得先获取它(当然,然,出于实际上的方便使用,queue类模版还是包含了一些本不在概念内的函数:size、back等)。 在队列上的操作是非常有限的,所以队列只在一些特殊且适合情况下才被使用。

那这些消失的函数都包括哪些呢?

  1. 所有Iterator函数: 没错,是所有,你没有看错! 因为所有迭代器都可以通过步进(advance函数或者算数加减)操作,从而指向队列中间的元素。
  2. 更改大小的非pop非push函数(包括增加和删除): 队列大小的改变只能被入队出队操作影响。
  3. 所有随机存取函数 : 元素的获取只能按序,而获取是操作的前提。

优先队列

优先队列也是一中容器适配器,这种队列主要具有以下两个性质:

  • 按优先级排序
  • 按优先级获取

C++ 头文件系列(queue)

在优先队列中,所有的元素都是按照优先级排序。 具体来说,当每一次元素入队时,都会对队列进行优先级排序,优先级最高的排在最前面,优先级最低的排在最后面。 而获取元素时,只能按优先级从高到底依次获取。

从某种意义上来说,队列(queue)和 优先队列(priority_queue)是相似的,甚至可以说 队列是优先队列的特殊情况。 它们都按照某种规律排序,只是排序的规则不同: 队列按元素的入队时间排序,优先队列按元素优先级排序。

优先级

那么如何定义该种队列的优先级呢? 在声明优先队列对象的时候,你可以传递一个二元谓词(Binary Predicate)来执行排序的任务。 如果你不传递自定义的二元谓词,则优先队列默认使用functional头文件中的less函数对象。

这个二元谓词执行严格弱序排序(Strick Weak Ordering)。这个排序有以下四个属性(假设comp为比较操作,x、y、z为待比较的元素, x non-comp y等价于(x comp y) == false && (x comp y) == false)):

  • 自反性((x comp x) == false)
  • 不对称性((x comp y) != (y comp x))
  • 传递性(((x comp y) == true, (y comp z) == true)) => ((x comp z) == true)))
  • 不可比性((x non-comp y, y non-comp z) => (x non-comp z))

这着实有点晦涩,搞得我都头晕了。 简单的讲,这个二元谓词比较两个元素,如果第一个比较的元素应该排在第二个前面(即第一个元素的优先级高于第二个),那么它返回true。 元素的相等性也是通过这个谓词操作推出来的:如果第一个元素的优先级不高于第二个元素,并且第二个元素的优先级也不高于第一个元素,那么这两个元素就相等。

操作对应的函数

  • 入队 -> push
  • 出队 -> pop

值得注意的是,不像队列那样,优先队列里的元素没有时间前后之分,所以priority_queue模版类去掉了front和back成员函数,代之以top函数,用以指代下一个出队的优先级最高的元素。