C++ STL学习之【容器适配器】

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
简介: 适配器(配接器)是 STL 中的六大组件之一,扮演着轴承、转换器的角色,使得 STL 中组件的使用更为灵活,比如 栈和队列 就是属于适配器而非容器,以及神秘的反向迭代器也属于适配器

✨个人主页: 夜 默
🎉所属专栏: C++修行之路
🎊每篇一句: 图片来源

  • A year from now you may wish you had started today.

    • 明年今日,你会希望此时此刻的自己已经开始行动了。

image.png


🌇前言

适配器(配接器)是 STL 中的六大组件之一,扮演着轴承、转换器的角色,使得 STL 中组件的使用更为灵活,比如 栈和队列 就是属于适配器而非容器,以及神秘的反向迭代器也属于适配器

具有多种功能的电源适配器,可以满足多种需求

image.png


🏙️正文

1、适配器模式

从应用角度出发,STL 中的适配器可以分为三类:

  • 容器适配器 container adapters
  • 迭代器适配器 iterator adapters
  • 仿函数适配器 functor adapters

其中,容器适配器 可修改底层为指定容器,如由 vector 构成的栈、由 list 构成的队列;迭代器适配器可以 实现其他容器的反向迭代器(后续介绍);最后的仿函数适配器就厉害了,几乎可以 无限制的创造出各种可能的表达式

本文介绍的是容器适配器,即 队列,最后还会介绍一下常作为这两种容器适配器的默认底层容器 双端队列

image.png

出自 《STL源码剖析》


2、栈 stack

stack 是一种特殊的数据结构,主要特点为 先进后出 FILO,主要操作有:入栈、出栈、查看栈顶元素、判断栈空等;栈在原则上是不允许进行中部或头部操作的,这样会破坏栈结构的完整性

栈在生活中比较少见,比较形象的例子是米缸,最先倒进去的米总是最后才能吃到,这正好契合了栈先进后出的思想

image.png

官方文档中 stack 的接口也是比较少的

image.png

image.png

可以看出,栈有两个模板参数

  • 参数1:T 栈中的元素类型,同时也是底层容器中的元素类型
  • 参数2:Container 实现栈时用到的底层容器,这里为缺省参数,缺省结构为 双端队列 deque

如何优雅的创建一个栈对象?

#include <iostream>
#include <stack>
#include <vector>
#include <list>

using namespace std;

int main()
{
    stack<int> s;    //默认底层容器为 deque

    stack<int, vector<int>> sv;    //显示实例化底层容器为 vector
    
    stack<char, list<char>> sl;    //显示实例化底层容器为 list

    cout << typeid(s).name() << endl;    //查看具体类型
    cout << typeid(sv).name() << endl;
    cout << typeid(sl).name() << endl;

    return 0;
}

image.png

注意:关于参数3 allocator 是空间配置器,这里先不作讲解,后续再学习

2.1、常用接口学习

学习使用接口时,直接使用默认的底层容器即可(不需要传递模板参数2)

因为接口少且非常简单,所以上手起来很方便

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    stack<int> s;    //构造一个栈对象

    cout << "Original:>" << endl;
    cout << "empty(): " << s.empty() << endl;
    cout << "size(): " << s.size() << endl;

    cout << endl << "Push:>" << endl;
    s.push(1);    //入栈3个元素
    s.push(2);
    s.push(3);
    cout << "empty(): " << s.empty() << endl;
    cout << "size(): " << s.size() << endl;
    cout << "top(): " << s.top() << endl;

    cout << endl << "Pop:>" << endl;
    s.pop();    //出栈两次
    s.pop();
    cout << "empty(): " << s.empty() << endl;
    cout << "size(): " << s.size() << endl;
    cout << "top(): " << s.top() << endl;

    return 0;
}

image.png

栈的常用接口就这几个,多用几次就熟悉了

2.2、模拟实现

因为是容器适配器,所以在模拟实现时,需要借助其他容器,这里选择使用 vector

#pragma once
#include <vector>

using namespace std;

namespace Yohifo
{
    //这里选择模板参数2 底层容器 的缺省值为 vector
    template<class T, class Container = vector<int>>
    class stack
    {
    public:
        //需要提供一个带缺省参数的构造函数,因为默认构造函数不接受传参
        stack(const Container& c = Container())
            :_c(c)
        {}

        //不需要显式的去写析构函数,默认生成的够用了
        //同理拷贝构造、赋值重载也不需要

        bool empty() const
        {
            return _c.empty();
        }

        size_t size() const
        {
            return _c.size();
        }

        //top 需要提供两种版本
        T& top()
        {
            return _c.back();
        }

        const T& top() const
        {
            return _c.back();
        }

        //选取的底层容器必须支持尾部操作
        void push(const T& val)
        {
            _c.push_back(val);
        }

        void pop()
        {
            //空栈不能弹出,可在底层容器中检查出来
            _c.pop_back();
        }

    private:
        Container _c;    //成员变量为具体的底层容器
    };
}

适配器的厉害之处就在于 只要底层容器有我需要的函数接口,那么我就可以为其适配出一个容器适配器,比如 vector 构成的栈、list 构成的栈、deque 构成的栈,甚至是 string 也能适配出一个栈,只要符合条件,都可以作为栈的底层容器,当然不同结构的效率不同,因此库中选用的是效率较高的 deque 作为默认底层容器

image.png


3、队列 queue

队列 queue 是另一种特殊的数据结构,遵循先进先出 FIFO,主要操作:入队、出队、判断队空、查看队头尾元素等

队列是一种生活中无处不见的场景,比如食堂打饭、柜台办理业务、排队出车站等等,所谓先来后到,形容的就是队列了

容器适配器.gif

作为容器适配器,queue 官方提供的接口也是一样的少

image.png

image.png

和栈一样,队列也有两个模板参数:

  • 参数1:T 队列中的元素类型,同时也是底层容器中的元素类型
  • 参数2:Container 实现队列时用到的底层容器,这里为缺省参数,缺省结构为 双端队列 deque

双端队列的优点在于高效的头尾操作和极致的空间使用,正好符合 栈和队列 的特殊需求

创建队列对象时,我们也可以指定其底层容器

#include <iostream>
#include<queue>
#include <vector>
#include <list>

using namespace std;

int main()
{
    queue<int> qDeque;    //默认使用 deque
    queue<double, vector<double>> qVector;    //指定使用 vector
    queue<char, list<char>> qList;    //指定使用 list

    cout << typeid(qDeque).name() << endl;    //查看具体类型
    cout << typeid(qVector).name() << endl;
    cout << typeid(qList).name() << endl;
    return 0;
}

image.png

3.1、常用接口学习

queue 中的接口与 stack 差不多,不过 queue 出元素时是在队头操作,同时它支持访问队头、队尾元素,而 stack 只能访问栈顶元素

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    queue<int> q;    //构建出一个队列对象

    cout << "Original:>" << endl;
    cout << "empty(): " << q.empty() << endl;
    cout << "size(): " << q.size() << endl;

    cout << endl << "Push:>" << endl;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    cout << "empty(): " << q.empty() << endl;
    cout << "size(): " << q.size() << endl;
    cout << "front(): " << q.front() << endl;
    cout << "back(): " << q.back() << endl;

    cout << endl << "Pop:>" << endl;
    q.pop();
    q.pop();
    q.pop();
    cout << "empty(): " << q.empty() << endl;
    cout << "size(): " << q.size() << endl;
    cout << "front(): " << q.front() << endl;
    cout << "back(): " << q.back() << endl;

    return 0;
}

image.png

3.2、模拟实现

队列的模拟实现也是相当简单,这里选用 list 作为底层容器

#pragma once
#include <list>

using namespace std;

namespace Yohifo
{
    template<class T, class Container = list<T>>
    class queue
    {
    public:
        queue(const Container& c = Container())
            :_c(c)
        {}

        //这里也不需要提供拷贝构造、赋值重载、析构函数

        bool empty() const
        {
            return _c.empty();
        }

        size_t size() const
        {
            return _c.size();
        }

        //选取的底层容器中,已经准备好了相关函数,如 front、back
        T& front()
        {
            return _c.front();
        }
        const T& front() const
        {
            return _c.front();
        }

        T& back()
        {
            return _c.back();
        }
        const T& back() const
        {
            return _c.back();
        }

        void push(const T& val)
        {
            _c.push_back(val);    //队列只能尾插
        }

        void pop()
        {
            _c.pop_front();    //队列只能头删
        }

    private:
        Container _c;    //成员变量为指定的底层容器对象
    };
}

队列和栈在进行适配时,都是在调用已有的接口,若是特殊接口,比如 toppushpop 等,进行相应转换即可

  • top -> back 尾元素
  • 栈、队列 push -> push_back 尾插
  • pop -> pop_back 尾删
  • 队列 pop -> pop_front 头删

image.png


4、小结

栈和队列在实际开发中作为一种辅助结构被经常使用,比如内存空间划分中的栈区,设计规则符合栈 FILO;操作系统中的各种队列,如阻塞队列,设计规则符合 队列 FIFO。除此以外,在很多 OJ 题中,都需要借助栈和队列进行解题

image.png


注: 二叉树的最近公共祖先可以借助栈完成时间复杂度 O(N) 的解法

注意:

  • 栈和队列都属于特殊的数据结构,原则上是不支持遍历的,因为一旦进行遍历,其中的数据必然被弹出,因此两者都没有提供迭代器
  • 假设容器没有提供头尾操作,比如 mapset,那么就不能拿它们适配出 栈或队列,强行使用会报错

image.png


5、双端队列 deque(了解)

双端队列是官方指定的底层容器,其结构上的特殊设计决定了它只适合于头尾操作需求高的场景:双端队列 = vector + list,设计时就想汲取二者的优点(下标随机访问 + 极致的空间使用),但鱼和熊掌不可兼得,在复杂结构的加持之下,双端队列趋于中庸,无法做到 vectorlist 那样极致,因此实际中也很少使用,比较适合当作适配器的底层容器

image.png

双端队列的数据结构:list + vector

  • 利用 list 构造出一个 map 作为主控数组(通过链式结构链接),数组中元素为数组指针
  • 利用 vector 构造出大小为 N 的小数组(缓冲区),这些小数组才是双端队列存储元素的地方

注意:此处的 map 并非是容器 map,仅仅是名字相同而已

将二者结合起来,就得到了复杂的双端队列

image.png

deque 的扩容机制:只需要对中控数组 map 进行扩容,再将原 map 中的数组指针拷贝过来即可,效率比较高

deque 中的随机访问:

  1. (下标 - 前预留位) / 单个数组长度 获取对应小数组位置
  2. (下标 - 前预留位) % 单个数组长度 获取其在小数组中的对应下标

由此可见,单个数组大小(缓冲区大小)需要定长,否则访问时计算会比较麻烦,但长度定长后,会引发中间位置插入删除效率低的问题

对此 SGI 版的 STL 选择牺牲中间位置插入,提高下标随机访问速度,令小数组定长,这也是将它作为 栈和队列 默认底层容器的原因之一,因为 栈和队列 不需要对中间进行操作

因为中控数组是链式结构,因此双端队列的迭代器设计极为复杂

  • cur 指向当前需要的数据位置
  • first 指向 buffer 数组起始位置
  • last 指向 buffer 数组终止位置
  • node 反向指向中控数组

image.png

这个迭代器还是一个随机迭代器,因此可以使用 std::sort

  • 无论是 deque 还是 list,直接排序的效率都不如借助 vector 间接排序效率高

deque 的缺点

  • 中间位置插入删除比较麻烦,可以令小数组长度不同解决问题,不过此时影响随机访问效率
  • 结构设计复杂,且不如 vectorlist 极致
  • 致命缺陷:不适合遍历,迭代器需要频繁检测是否移动某段小空间的边界,效率很低

凑巧的是,栈和队列 可以完美避开所有缺陷,全面汲取其优点,因此 双端队列 为容器适配器的默认底层容器

对于这种中庸且复杂的容器,只需要做简单了解就行了


🌆总结

以上就是本篇关于 C++ STL学习之【容器适配器】的全部内容了,在本文中,我们首先学习了适配器默认,了解它存在的意义及种类;其次学习和模拟实现了两种容器适配器 栈和队列;最后认识了容器适配器的默认底层容器 双端队列,见识了其复杂的结构设计及优缺点。关于适配的下一种形态:迭代器适配器 将在下文中学习,同时 反向迭代器 的神秘面纱也将被揭开

如果你觉得本文写的还不错的话,可以留下一个小小的赞👍,你的支持是我分享的最大动力!

如果本文有不足或错误的地方,随时欢迎指出,我会在第一时间改正


image.png

相关文章推荐


==STL 之 list 类==

C++ STL学习之【list的模拟实现】

C++ STL学习之【list的使用】

===============

==STL 之 vector 类==

C++ STL学习之【vector的模拟实现】

C++ STL学习之【vector的使用】

===============

==STL 之 string 类==

C++ STL学习之【string类的模拟实现】

C++ STL 学习之【string】


承蒙厚爱,感谢支持.gif

目录
相关文章
|
6月前
|
编译器 C++ 容器
【c++丨STL】基于红黑树模拟实现set和map(附源码)
本文基于红黑树的实现,模拟了STL中的`set`和`map`容器。通过封装同一棵红黑树并进行适配修改,实现了两种容器的功能。主要步骤包括:1) 修改红黑树节点结构以支持不同数据类型;2) 使用仿函数适配键值比较逻辑;3) 实现双向迭代器支持遍历操作;4) 封装`insert`、`find`等接口,并为`map`实现`operator[]`。最终,通过测试代码验证了功能的正确性。此实现减少了代码冗余,展示了模板与仿函数的强大灵活性。
160 2
|
6月前
|
存储 算法 C++
【c++丨STL】map/multimap的使用
本文详细介绍了STL关联式容器中的`map`和`multimap`的使用方法。`map`基于红黑树实现,内部元素按键自动升序排列,存储键值对,支持通过键访问或修改值;而`multimap`允许存在重复键。文章从构造函数、迭代器、容量接口、元素访问接口、增删操作到其他操作接口全面解析了`map`的功能,并通过实例演示了如何用`map`统计字符串数组中各元素的出现次数。最后对比了`map`与`set`的区别,强调了`map`在处理键值关系时的优势。
288 73
|
7月前
|
存储 缓存 C++
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
C++ 标准模板库(STL)提供了一组功能强大的容器类,用于存储和操作数据集合。不同的容器具有独特的特性和应用场景,因此选择合适的容器对于程序的性能和代码的可读性至关重要。对于刚接触 C++ 的开发者来说,了解这些容器的基础知识以及它们的特点是迈向高效编程的重要一步。本文将详细介绍 C++ 常用的容器,包括序列容器(`std::vector`、`std::array`、`std::list`、`std::deque`)、关联容器(`std::set`、`std::map`)和无序容器(`std::unordered_set`、`std::unordered_map`),全面解析它们的特点、用法
C++ 容器全面剖析:掌握 STL 的奥秘,从入门到高效编程
|
6月前
|
存储 算法 C++
【c++丨STL】set/multiset的使用
本文深入解析了STL中的`set`和`multiset`容器,二者均为关联式容器,底层基于红黑树实现。`set`支持唯一性元素存储并自动排序,适用于高效查找场景;`multiset`允许重复元素。两者均具备O(logN)的插入、删除与查找复杂度。文章详细介绍了构造函数、迭代器、容量接口、增删操作(如`insert`、`erase`)、查找统计(如`find`、`count`)及`multiset`特有的区间操作(如`lower_bound`、`upper_bound`、`equal_range`)。最后预告了`map`容器的学习,其作为键值对存储的关联式容器,同样基于红黑树,具有高效操作特性。
222 3
|
7月前
|
存储 算法 C++
【c++丨STL】priority_queue(优先级队列)的使用与模拟实现
本文介绍了STL中的容器适配器`priority_queue`(优先级队列)。`priority_queue`根据严格的弱排序标准设计,确保其第一个元素始终是最大元素。它底层使用堆结构实现,支持大堆和小堆,默认为大堆。常用操作包括构造函数、`empty`、`size`、`top`、`push`、`pop`和`swap`等。我们还模拟实现了`priority_queue`,通过仿函数控制堆的类型,并调用封装容器的接口实现功能。最后,感谢大家的支持与关注。
281 1
|
7月前
|
存储 算法 C++
深入浅出 C++ STL:解锁高效编程的秘密武器
C++ 标准模板库(STL)是现代 C++ 的核心部分之一,为开发者提供了丰富的预定义数据结构和算法,极大地提升了编程效率和代码的可读性。理解和掌握 STL 对于 C++ 开发者来说至关重要。以下是对 STL 的详细介绍,涵盖其基础知识、发展历史、核心组件、重要性和学习方法。
|
2月前
|
存储 监控 测试技术
如何将现有的应用程序迁移到Docker容器中?
如何将现有的应用程序迁移到Docker容器中?
187 57
|
2月前
|
存储 监控 Java
如何对迁移到Docker容器中的应用进行性能优化?
如何对迁移到Docker容器中的应用进行性能优化?
198 58
|
2月前
|
NoSQL Redis Docker
使用Docker Compose工具进行容器编排的教程
以上就是使用Docker Compose进行容器编排的基础操作。这能帮你更有效地在本地或者在服务器上部署和管理多容器应用。
249 11
|
2月前
|
缓存 Java Docker
如何对应用代码进行优化以提高在Docker容器中的性能?
如何对应用代码进行优化以提高在Docker容器中的性能?
174 1