C++ STL(五)容器适配器.md
STL容器适配器?
容器就是将不适用的序列式容器(包括 vector、deque 和 list)变得适用。如同电源适配器。
容器适配器本质上还是容器,只不过此容器模板类的实现,利用了大量其它基础容器模板类中已经写好的成员函数。当然,如果必要的话,容器适配器中也可以自创新的成员函数。
STL容器适配器的种类
STL 提供了 3 种容器适配器,分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。其中,各适配器所使用的默认基础容器以及可供用户选择的基础容器,如下表所示。
容器适配器 | 基础容器筛选条件 | 默认使用的基础容器 |
---|---|---|
stack | 基础容器需包含以下成员函数:empty()、size()、back()、push_back()、pop_back()。满足条件的基础容器有 vector、deque、list。 | deque |
queue | 基础容器需包含以下成员函数:empty()、size()、front()、back()、push_back()、pop_front()。满足条件的基础容器有 deque、list。 | deque |
priority_queue | 基础容器需包含以下成员函数:empty()、size()、front()、push_back()、pop_back()。满足条件的基础容器有vector、deque。 | vector |
stack容器适配器
stack 栈适配器是一种单端开口的容器。实际上该容器模拟的就是栈存储结构,即无论是向里存数据还是从中取数据,都只能从这一个开口实现操作。
栈中存储的元素满足“后进先出(简称LIFO)”的准则,stack 适配器也同样遵循这一准则。
stack的创建
由于 stack 适配器以模板类 stack<T,Container=deque>(其中 T 为存储元素的类型,Container 表示底层容器的类型)的形式位于头文件中,并定义在 std 命名空间里。因此,在创建该容器之前,程序中应包含以下 2 行代码:
1 |
|
std 命名空间也可以在使用 stack 适配器时额外注明。
创建 stack 适配器,大致分为如下几种方式。
1.
创建一个不包含任何元素的 stack 适配器,并采用默认的 deque 基础容器:
1 | std::stack<int> values; |
上面这行代码,就成功创建了一个可存储 int 类型元素,底层采用 deque 基础容器的 stack 适配器。
2.
上面提到,stack<T,Container=deque> 模板类提供了 2 个参数,通过指定第二个模板类型参数,我们可以使用出 deque 容器外的其它序列式容器,只要该容器支持 empty()、size()、back()、push_back()、pop_back() 这 5 个成员函数即可。
在介绍适配器时提到,序列式容器中同时包含这 5 个成员函数的,有 vector、deque 和 list 这 3 个容器。因此,stack 适配器的基础容器可以是它们 3 个中任何一个。例如,下面展示了如何定义一个使用 list 基础容器的 stack 适配器:
1 | std::stack<std::string, std::list<int>> values; |
3.
可以用一个基础容器来初始化 stack 适配器,只要该容器的类型和 stack 底层使用的基础容器类型相同即可。例如:
1 | std::list<int> values {1, 2, 3}; |
注意,初始化后的 my_stack 适配器中,栈顶元素为 3,而不是 1。另外在第 2 行代码中,stack 第 2 个模板参数必须显式指定为 list(必须为 int 类型,和存储类型保持一致),否则 stack 底层将默认使用 deque 容器,也就无法用 lsit 容器的内容来初始化 stack 适配器。
4.
还可以用一个 stack 适配器来初始化另一个 stack 适配器,只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如:
1 | std::list<int> values{ 1, 2, 3 }; |
可以看到,和使用基础容器不同,使用 stack 适配器给另一个 stack 进行初始化时,有 2 种方式,使用哪一种都可以。
注意,第 3、4 种初始化方法中,my_stack 适配器的数据是经过拷贝得来的,也就是说,操作 my_stack 适配器,并不会对 values 容器以及 my_stack1 适配器有任何影响;反过来也是如此。
stack成员函数
和其他序列容器相比,stack 是一类存储机制简单、提供成员函数较少的容器。
成员函数 | 功能 |
---|---|
empty() | 当 stack 栈中没有元素时,该成员函数返回 true;反之,返回 false。 |
size() | 返回 stack 栈中存储元素的个数。 |
top() | 返回一个栈顶元素的引用,类型为 T&。如果栈为空,程序会报错。 |
push(const T& val) | 先复制 val,再将 val 副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。 |
push(T&& obj) | 以移动元素的方式将其压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。 |
pop() | 弹出栈顶元素。 |
emplace(arg…) | arg… 可以是一个参数,也可以是多个参数,但它们都只用于构造一个对象,并在栈顶直接生成该对象,作为新的栈顶元素。 |
swap(stack & other_stack) | 将两个 stack 适配器中的元素进行互换,需要注意的是,进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。 |
queue容器适配器
和 stack 栈容器适配器不同,queue 容器适配器有 2 个开口,其中一个开口专门用来输入数据,另一个专门用来输出数据。
这种存储结构最大的特点是,最先进入 queue 的元素,也可以最先从 queue 中出来,即用此容器适配器存储数据具有“先进先出(简称 “FIFO” )”的特点,因此 queue 又称为队列适配器。
queue的创建
queue 容器适配器以模板类 queue<T,Container=deque>(其中 T 为存储元素的类型,Container 表示底层容器的类型)的形式位于头文件中,并定义在 std 命名空间里。因此,在创建该容器之前,程序中应包含以下 2 行代码:
1 |
|
创建 queue 容器适配器的方式大致可分为以下几种。
1.
创建一个空的 queue 容器适配器,其底层使用的基础容器选择默认的 deque 容器:
1 | std::queue<int> values; |
通过此行代码,就可以成功创建一个可存储 int 类型元素,底层采用 deque 容器的 queue 容器适配器。
2.
当然,也可以手动指定 queue 容器适配器底层采用的基础容器类型。queue 容器适配器底层容器可以选择 deque 和 list。
作为 queue 容器适配器的基础容器,其必须提供 front()、back()、push_back()、pop_front()、empty() 和 size() 这几个成员函数,符合条件的序列式容器仅有 deque 和 list。
例如,下面创建了一个使用 list 容器作为基础容器的空 queue 容器适配器:
1 | std::queue<int, std::list<int>> values; |
注意,在手动指定基础容器的类型时,其存储的数据类型必须和 queue 容器适配器存储的元素类型保持一致。
3.
可以用基础容器来初始化 queue 容器适配器,只要该容器类型和 queue 底层使用的基础容器类型相同即可。例如:
1 | std::deque<int> values{1,2,3}; |
由于 my_queue 底层采用的是 deque 容器,和 values 类型一致,且存储的也都是 int 类型元素,因此可以用 values 对 my_queue 进行初始化。
4.
还可以直接通过 queue 容器适配器来初始化另一个 queue 容器适配器,只要它们存储的元素类型以及底层采用的基础容器类型相同即可。例如:
1 | std::deque<int> values{1,2,3}; |
注意,和使用基础容器不同,使用 queue 适配器给另一个 queue 进行初始化时,有 2 种方式,使用哪一种都可以。
值得一提的是,第 3、4 种初始化方法中 my_queue 容器适配器的数据是经过拷贝得来的,也就是说,操作 my_queue 容器适配器中的数据,并不会对 values 容器以及 my_queue1 容器适配器有任何影响;反过来也是如此。
queue成员函数
queue 容器适配器和 stack 有一些成员函数相似,但在一些情况下,工作方式有些不同。
成员函数 | 功能 |
---|---|
empty() | 如果 queue 中没有元素的话,返回 true。 |
size() | 返回 queue 中元素的个数。 |
front() | 返回 queue 中第一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。 |
back() | 返回 queue 中最后一个元素的引用。如果 queue 是常量,就返回一个常引用;如果 queue 为空,返回值是未定义的。 |
push(const T& obj) | 在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。 |
emplace() | 在 queue 的尾部直接添加一个元素。 |
push(T&& obj) | 以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。 |
pop() | 删除 queue 中的第一个元素。 |
swap(queue &other_queue) | 将两个 queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。 |
和 stack 一样,queue 也没有迭代器,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素。
priority_queue容器适配器(优先级队列)
priority_queue 容器适配器模拟的也是队列这种存储结构,即使用此容器适配器存储元素只能“从一端进(称为队尾),从另一端出(称为队头)”,且每次只能访问 priority_queue 中位于队头的元素。
但是,priority_queue 容器适配器中元素的存和取,遵循的并不是 “First in,First out”(先入先出)原则。而是根据优先级。
那么,priority_queue 容器适配器中存储的元素,优先级是如何评定的呢?很简单,每个 priority_queue 容器适配器在创建时,都制定了一种排序规则。根据此规则,该容器适配器中存储的元素就有了优先级高低之分。
priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素,每当有新元素进入,它都会根据既定的排序规则找到优先级最高的元素,并将其移动到队列的队头;同样,当 priority_queue 从队头移除出一个元素之后,它也会再找到当前优先级最高的元素,并将其移动到队头。
基于 priority_queue 的这种特性,因此该容器适配器有被称为优先级队列。
STL 中,priority_queue 容器适配器的定义如下:
1 | template <typename T, |
可以看到,priority_queue 容器适配器模板类最多可以传入 3 个参数,它们各自的含义如下:
-
typename T:指定存储元素的具体类型;
-
typename Container:指定 priority_queue 底层使用的基础容器,默认使用 vector 容器。
作为 priority_queue 容器适配器的底层容器,其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数,STL 序列式容器中只有 vector 和 deque 容器符合条件。
-
typename Compare:指定容器中评定元素优先级所遵循的排序规则,默认使用std::less<T>
按照元素值从大到小进行排序,还可以使用std::greater<T>
按照元素值从小到大排序,但更多情况下是使用自定义的排序规则。
其中,
std::less<T>
和std::greater<T>
都是以函数对象的方式定义在<function>
头文件中。关于如何自定义排序规则,后续章节会做详细介绍。
priority_queue的创建
由于 priority_queue 容器适配器模板位于头文件中,并定义在 std 命名空间里,因此在试图创建该类型容器之前,程序中需包含以下 2 行代码:
1 |
|
创建 priority_queue 容器适配器的方法,大致有以下几种。
1.
创建一个空的 priority_queue 容器适配器,第底层采用默认的 vector 容器,排序方式也采用默认的
1 | std::less<T> 方法: |
2.
可以使用普通数组或其它容器中指定范围内的数据,对 priority_queue 容器适配器进行初始化:
1 | //使用普通数组 |
注意,以上 2 种方式必须保证数组或容器中存储的元素类型和 priority_queue 指定的存储类型相同。另外,用来初始化的数组或容器中的数据不需要有序,priority_queue 会自动对它们进行排序。
3.
还可以手动指定 priority_queue 使用的底层容器以及排序规则,比如:
1 | int values[]{ 4,1,2,3 }; |
事实上,std::less 和 std::greater 适用的场景是有限的,更多场景中我们会使用自定义的排序规则。
由于自定义排序规则的方式不只一种,因此这部分知识将在后续章节做详细介绍。
priority_queue成员函数
成员函数 | 功能 |
---|---|
empty() | 如果 priority_queue 为空的话,返回 true;反之,返回 false。 |
size() | 返回 priority_queue 中存储元素的个数。 |
top() | 返回 priority_queue 中第一个元素的引用形式。 |
push(const T& obj) | 根据既定的排序规则,将元素 obj 的副本存储到 priority_queue 中适当的位置。 |
push(T&& obj) | 根据既定的排序规则,将元素 obj 移动存储到 priority_queue 中适当的位置。 |
emplace(Args&&… args) | Args&&… args 表示构造一个存储类型的元素所需要的数据(对于类对象来说,可能需要多个数据构造出一个对象)。此函数的功能是根据既定的排序规则,在容器适配器适当的位置直接生成该新元素。 |
pop() | 移除 priority_queue 容器适配器中第一个元素。 |
swap(priority_queue& other) | 将两个 priority_queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 priority_queue 容器适配器中存储的元素类型以及底层采用的基础容器类型,都必须相同。 |
和 queue 一样,priority_queue 也没有迭代器,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素。
queue自定义排序
前面讲解 priority_queue 容器适配器时,还遗留一个问题,即当 头文件提供的排序方式(std::less<T>
和 std::greater<T>
)不再适用时,如何自定义一个满足需求的排序规则。
首先,无论 priority_queue 中存储的是基础数据类型(int、double 等),还是 string 类对象或者自定义的类对象,都可以使用函数对象的方式自定义排序规则。例如:
1 |
|
运行结果为:
2 3 4 5 6
注意,C++ 中的 struct 和 class 非常类似,前者也可以包含成员变量和成员函数,因此上面程序中,函数对象类 cmp 也可以使用 struct 关键字创建:
1 | struct cmp |
可以看到,通过在 cmp 类(结构体)重载的 () 运算符中自定义排序规则,并将其实例化后作为 priority_queue 模板的第 3 个参数传入,即可实现为 priority_queue 容器适配器自定义比较函数。
除此之外,当 priority_queue 容器适配器中存储的数据类型为结构体或者类对象(包括 string 类对象)时,还可以通过重载其 > 或者 < 运算符,间接实现自定义排序规则的目的。
注意,此方式仅适用于 priority_queue 容器中存储的为类对象或者结构体变量,也就是说,当存储类型为类的指针对象或者结构体指针变量时,此方式将不再适用,而只能使用函数对象的方式。
要想彻底理解这种方式的实现原理,首先要搞清楚 std::less<T>
和 std::greater<T>
各自的底层实现。实际上,<function>
头文件中的 std::less<T>
和 std::greater<T>
,各自底层实现采用的都是函数对象的方式。比如,std::less<T>
的底层实现代码为:
1 | template <typename T> |
可以看到,std::less<T>
和 std::greater<T>
底层实现的唯一不同在于,前者使用 < 号实现从大到小排序,后者使用 > 号实现从小到大排序。
那么,是否可以通过重载 < 或者 > 运算符修改 std::less<T>
和 std::greater<T>
的排序规则,从而间接实现自定义排序呢?答案是肯定的,举个例子:
1 |
|
输出结果为:
x y
1 2
2 2
2 3
3 3
3 4
可以看到,通过重载 < 运算符,使得 std::less<T>
变得适用了。
读者还可以自行尝试,通过重载 > 运算符,赋予 std::greater<T>
和之前不同的排序方式。
当然,也可以以友元函数或者成员函数的方式重载 > 或者 < 运算符。需要注意的是,以成员函数的方式重载 > 或者 < 运算符时,该成员函数必须声明为 const 类型,且参数也必须为 const 类型,至于参数的传值方式是采用按引用传递还是按值传递,都可以(建议采用按引用传递,效率更高)。
例如,将上面程序改为以成员函数的方式重载 < 运算符:
1 | class node { |
同样,在以友元函数的方式重载 < 或者 > 运算符时,要求参数必须使用 const 修饰。例如,将上面程序改为以友元函数的方式重载 < 运算符。例如:
1 | class node { |
总的来说,以函数对象的方式自定义 priority_queue 的排序规则,适用于任何情况;而以重载 > 或者 < 运算符间接实现 priority_queue 自定义排序的方式,仅适用于 priority_queue 中存储的是结构体变量或者类对象(包括 string 类对象)。
priority_queue的底层实现
priority_queue 优先级队列之所以总能保证优先级最高的元素位于队头,最重要的原因是其底层采用堆数据结构存储结构。
当然不使用堆来实现也是可以的,只要符合优先级队列的特性即可。但是使用堆的执行效率比一般情况高。
那么,堆到底是什么,它又是怎样组织数据的呢?
priority_queue底层的堆存储结构:
简单的理解堆,它在是完全二叉树的基础上,要求树中所有的父节点和子节点之间,都要满足既定的排序规则:
- 如果排序规则为从大到小排序,则表示堆的完全二叉树中,每个父节点的值都要不小于子节点的值,这种堆通常称为大顶堆;
- 如果排序规则为从小到大排序,则表示堆的完全二叉树中,每个父节点的值都要不大于子节点的值,这种堆通常称为小顶堆;
图 1 展示了一个由 {10,20,15,30,40,25,35,50,45}
这些元素构成的大顶堆和小顶堆。其中经大顶堆组织后的数据先后次序变为 {50,45,40,20,25,35,30,10,15}
,而经小顶堆组织后的数据次序为{10,20,15,25,50,30,40,35,45}
。
可以看到,大顶堆中,每个父节点的值都不小于子节点;同样在小顶堆中,每个父节点的值都不大于子节点。但需要注意的是,无论是大顶堆还是小顶堆,同一父节点下子节点的次序是不做规定的,这也是经大顶堆或小顶堆组织后的数据整体依然无序的原因。
可以确定的一点是,无论是通过大顶堆或者小顶堆,总可以筛选出最大或最小的那个元素(优先级最大),并将其移至序列的开头,此功能也正是 priority_queue 容器适配器所需要的。
为了验证 priority_queue 底层确实采用堆存储结构实现的,我们可以尝试用堆结合基础容器 vector 或 deque 实现 priority_queue。值得庆幸的是,STL 已经为我们封装好了可以使用堆存储结构的方法,它们都位于 头文件中。表 2 中列出了常用的几个和堆存储结构相关的方法。
函数 | 功能 |
---|---|
make_heap(first,last,comp) | 选择位于 [first,last) 区域内的数据,并根据 comp 排序规则建立堆,其中 fist 和 last 可以是指针或者迭代器,默认是建立大顶堆。 |
push_heap(first,last,comp) | 当向数组或容器中添加数据之后,此数据可能会破坏堆结构,该函数的功能是重建堆。 |
pop_heap(first,last,comp) | 将位于序列头部的元素(优先级最高)移动序列尾部,并使[first,last-1] 区域内的元素满足堆存储结构。 |
sort_heap(first,last,comp) | 对 [first,last) 区域内的元素进行堆排序,将其变成一个有序序列。 |
is_heap_until(first,last,comp) | 发现[first,last)区域内的最大堆。 |
is_heap(first,last,comp) | 检查 [first,last) 区域内的元素,是否为堆结构。 |
下面例子中,使用了表 2 中的部分函数,并结合 vector 容器提供的成员函数,模拟了 priority_queue 容器适配器部分成员函数的底层实现:
1 |
|
运行结果为:
4 2 3 1
添加元素:
4 2 3 1 5
5 4 3 1 2
移除元素:
4 2 3 1 5
4 2 3 1
上面程序可以用 priority_queue 容器适配器等效替代:
1 |
|
如果调试此程序,查看各个阶段 priority_queue 中存储的元素,可以发现,它和上面程序的输出结果是一致。也就是说,此程序在创建 priority_queue 之后,其存储的元素依次为 {4,2,3,1},同样当添加元素 5 之后,其存储的元素依次为 {5,4,3,1,2},移除一个元素之后存储的元素依次为 {4,2,3,1}。