【STL十二】适配器——容器适配器

一、适配器

1、适配器简介

• 适配器本质上是使一事务的行为类似于另一类事务的行为的一种机制。
• 适配器没有提供与元素的保存形式有关的真正数据结构实现，并且它不支持迭代器

2、使用适配器的优点

• 让程序员选择一种合适的底层数据结构。

3、适配器种类

• 容器适配器
• 迭代器适配器
• 函数适配器

3.1、容器适配器

• 容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。

3.2、迭代器适配器

• 迭代器适配器：是修改为某些基本容器定义的迭代器的接口的一种STL组件。
• 反向迭代器和插入迭代器属于迭代器适配器，迭代器适配器扩展了迭代器的功能。

3.3、函数适配器（function adapters)

• 函数适配器：通过转换或者修改其他函数对象使其功能得到扩展。可以将预先定义的仿函数和其他数值结合在一起。
• 函数适配器种类
  • 否定器
  • 绑定器
  • 函数指针适配器

二、容器适配器

1、简介

• 简单的理解容器适配器，其就是将不适用的序列式容器（包括 vector、deque 和 list）变得适用。

2、分类

• STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。

三、stack适配器

1、简介

• stack 栈适配器是一种单端开口的容器（如图 1 所示），实际上该容器模拟的就是栈存储结构，即无论是向里存数据还是从中取数据，都只能从这一个开口实现操作。
• 先进后出（first-in,last-out,FILO)

stack 适配器的开头端通常称为栈顶。由于数据的存和取只能从栈顶处进行操作，因此对于存取数据，stack 适配器有这样的特性，即每次只能访问适配器中位于最顶端的元素，也只有移除 stack 顶部的元素之后，才能访问位于栈中的元素。

2、构造函数

template<
    class T,
    class Container = std::deque<T>
> class stack
1
2
3
4

T - 存储的元素类型。
Container - 用于存储元素的底层容器类型。

3、成员函数

• 3.1、元素访问

• 3.2、容量

• 3.3、修改操作成员函数

4、demo

#include <iostream>
#include <stack>
#include <list>
using namespace std;
int main()
{
    //构建 stack 容器适配器
    list<int> values{ 1, 2, 3 };
    stack<int, list<int>> my_stack(values);
    //查看 my_stack 存储元素的个数
    cout << "size of my_stack: " << my_stack.size() << endl;
    //将 my_stack 中存储的元素依次弹栈，直到其为空
    while (!my_stack.empty())
    {
        cout << my_stack.top() << endl;
        //将栈顶元素弹栈
        my_stack.pop();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

输出

size of my_stack: 3
3
2
1

三、queue适配器

1、简介

• queue 容器适配器有 2 个开口，其中一个开口专门用来输入数据，另一个专门用来输出数据
• 先进先出（first-in,first-out,FIFO)

STL queue 容器适配器模拟的就是队列这种存储结构，因此对于任何需要用队列进行处理的序列来说，使用 queue 容器适配器都是好的选择

2、构造函数

template<
    class T,
    class Container = std::deque<T>
> class queue
1
2
3
4

T - 存储的元素类型。
Container - 用于存储元素的底层容器

3、成员函数

• 3.1、元素访问

• 3.2、容量

• 3.3、修改操作成员函数

4、demo

#include <iostream>
#include <queue>
#include <list>
using namespace std;
int main()
{
    //构建 queue 容器适配器
    std::deque<int> values{ 1,2,3 };
    // 使用dqueue对 queue 进行初始化
    std::queue<int> my_queue(values);//{1,2,3}
    //查看 my_queue 存储元素的个数
    cout << "size of my_queue: " << my_queue.size() << endl;
    //访问 my_queue 中的元素
    while (!my_queue.empty())
    {
        cout << my_queue.front() << endl;
        //访问过的元素出队列
        my_queue.pop();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

输出

size of my_queue: 3
1
2
3

四、priority_queue 适配器

1、简介

• priority_queue 容器适配器中元素的存和取，遵循的并不是 “First in,First out”（先入先出）原则，而是“First in，Largest out”原则。直白的翻译，指的就是先进队列的元素并不一定先出队列，而是优先级最大的元素最先出队列。

• 那么，priority_queue 容器适配器中存储的元素，优先级是如何评定的呢？很简单，每个 priority_queue 容器适配器在创建时，都制定了一种排序规则。根据此规则，该容器适配器中存储的元素就有了优先级高低之分。

举个例子，假设当前有一个 priority_queue 容器适配器，其制定的排序规则是按照元素值从大到小进行排序。根据此规则，自然是 priority_queue 中值最大的元素的优先级最高。
priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据既定的排序规则找到优先级最高的元素，并将其移动到队列的队头；同样，当 priority_queue 从队头移除出一个元素之后，它也会再找到当前优先级最高的元素，并将其移动到队头。

基于 priority_queue 的这种特性，因此该容器适配器有被称为优先级队列.

2、构造函数

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;
1
2
3
4
5

• typename T：指定存储元素的具体类型；

• typename Container：指定 priority_queue 底层使用的基础容器，默认使用 vector 容器。

• typename Compare：指定容器中评定元素优先级所遵循的排序规则，默认使用std::less按照元素值从大到小进行排序，还可以使用std::greater按照元素值从小到大排序，但更多情况下是使用自定义的排序规则。

其中，std::less 和 std::greater 都是以函数对象的方式定义在 头文件中。关于如何自定义排序规则，后续章节会做详细介绍。

3、成员函数

• 3.1、元素访问

• 3.2、容量

• 3.3、修改操作成员函数

4、demo

#include <iostream>
#include <queue>
#include <array>
#include <functional>
using namespace std;
int main()
{
    //创建一个空的priority_queue容器适配器
    std::priority_queue<int>values;
    //使用 push() 成员函数向适配器中添加元素
    values.push(3);//{3}
    values.push(1);//{3,1}
    values.push(4);//{4,1,3}
    values.push(2);//{4,2,3,1}
    //遍历整个容器适配器
    while (!values.empty())
    {
        //输出第一个元素并移除。
        std::cout << values.top()<<" ";
        values.pop();//移除队头元素的同时，将剩余元素中优先级最大的移至队头
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

demo

4 3 2 1

参考：
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/container
5、哔哩哔哩——侠姐聊算法——8.2.1 适配器与迭代器