【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(下)

简介: 【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(下)

【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(上)https://developer.aliyun.com/article/1514695?spm=a2c6h.13148508.setting.23.4b904f0ejdbHoA

🔺4、仿函数

(1)什么是仿函数

仿函数(Functor)又称为函数对象(Function Object),使一个类的使用看上去像一个函数,其实就是在类中重载了 operator() 运算符,这个类就有了类似函数的行为,就是一个仿函数类了。

仿函数的语法几乎和我们普通的函数调用一样,调用仿函数时,实际上就是通过仿函数类对象调用重载后的 operator() 运算符,这种行为类似函数调用。

// 仿函数(函数对象) --自定义类型
struct Less
{
  bool operator()(const int& x, const int& y) // 重载()运算符
  {
    return x < y;
  }
};
 
void test_functor()
{
  // 方式(1)
  Less less; // 构造函数对象
  cout << less(1, 2) << endl;  // 编译器会解释成:less.operator()(1, 2);
 
  // 方式(2)
  cout << Less()(1, 2) << endl; // 构造一个匿名函数对象
}

cplusplus.com/reference/functional/greater/

cplusplus.com/reference/functional/less/

仿函数类还可以写成类模板,适应更多的类型:

template<class T> // 用于小于(<)不等式比较的函数对象类
struct Less
{
  bool operator()(const T& x, const T& y)
  {
    return x < y;
  }
};
 
template<class T> // 用于大于(>)不等式比较的函数对象类
struct Greater
{
  bool operator()(const T& x, const T& y)
  {
    return x > y;
  }
};
 
void test_functor()
{
  Less<int> less;
  cout << less(1, 2) << endl; // true
  
    Greater<int> greater;
  cout << greater(1, 2) << endl; // false
}

仿函数 less 和 greater 是继承的 binary_function,可以看作是对于一类函数的总体声明,这是函数做不到的。

template <class T> struct greater : binary_function <T, T, bool>
{
    bool operator() (const T& x, const T& y) const
    {
        return x > y;
    }
};
 
template <class T> struct less : binary_function <T, T, bool>
{
    bool operator() (const T& x, const T& y) const
    {
        return x < y;
    }
};

(2)模板实例化时,仿函数的使用

类模板一般是显式实例化的,在 <> 中指定模板参数的实际类型,所以类模板是传类型。比如: priority_queue。

//第1个模板参数是:存储数据的类型
//第2个模板参数是:基础容器的类型
//第3个模板参数是:仿函数的类型
template <class T, class Container = vector<T>,
    class Compare = less<typename Container::value_type>> class priority_queue;
 
void test()
{
    // 建小堆
    priority_queue<int, vector<int>, greater<int>> pq; // 传仿函数greater<int>类型
}

而函数模板一般是隐式实例化,让编译器根据实参推演模板参数的实际类型,所以函数模板是传对象。比如:sort。

// 第1个模板参数:迭代器的类型
// 第2个模板参数是:仿函数的类型
template <class RandomAccessIterator, class Compare>
 
// 函数的第1、2个参数是:迭代器对象
// 函数的第3个参数是:仿函数类的对象
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
void test()
{
    vector<int> v { 5,3,2,4,1 };
    // 排降序(>)
    sort (v.begin(), b.end(), greater<int>()); // 传仿函数类greater<int>的匿名对象
    for (const auto& x : v)
        cout << x << " ";
    cout << endl;
}

四、容器适配器

stack 和 queue 和 priority_queue 往往不被认为是一个容器,而是一个容器适配。

adapter 原意是插座、适配器、接合器的意思。


1、什么是适配器

适配器 是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成客户希望的另外一个接口。


2、STL 标准库中 stack queue 的底层结构

虽然 stack 和 queue 中也可以存放元素,但在 STL 中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为 stack 和 queue 只是对其他容器的接口进行了包装,STL 中 stack 和 queue 默认使用 deque priority_queue 默认使用 vector


3、deque的简单介绍(了解)

cplusplus.com/reference/deque/deque/


(1)deque 的原理介绍

deque( 双端队列 ):是一种双开口的 “连续” 空间的数据结构。

双开口的含义是:可以在头尾两端进行插入和删除操作,且 时间复杂度为 O(1) 与 vector 比较,头插效率高,不需要搬移元素;与 list 比较,空间利用率比较高。

  • vector 是一段连续的物理空间

优点

  1. 支持随机访问
  2. 空间利用率高,底层是连续空间,不容易造成内存碎片。
  3. CPU 高速缓存命中率很高。

缺点

  1. 空间不够时需要增容,增容代价很大(需要经过重新配置空间、元素搬移、释放原空间等),同时还存在一定的空间浪费。
  2. 头部和中间插入删除,效率很低 O(n)。

  • list 不是连续的物理空间,而是由一个个节点 “链接” 起来的

优点

  1. 按需申请释放空间,不会浪费空间
  2. 任意位置插入和删除数据都是 O(1),因为不需要移动数据,插入删除效率高

缺点

  1. 不支持随机访问
  2. 空间利用率低,底层不是连续的空间,小节点容易造成内存碎片。
  3. CPU 高速缓存命中率很低。

  • deque 并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际 deque 类似于一个动态的二维数组。
  1. deque 支持很多操作,比如 vector 不支持头插头删(因为效率太低),而 deque 支持。
  2. list 不支持随机访问,而 deque 支持。

起来就像完美融合了 vector 和 list 的操作。

当需要增容时,只需要经过重新配置空间、元素搬移、释放原空间等过程,而是新增一个 buffer,存入数据,然后让中控数组指向新增的 buffer,将其管理起来。

deque 底层是一段假象的连续空间,实际是分段连续的,为了维护其 “整体连续” 以及随机访问的假象,落在了 deque 的迭代器身上,因此 deque 的迭代器设计就比较复杂(包含4个指针) ,如下图所示:(deque 的中控器、缓冲区、迭代器的相互关系:


(2)deque 的优点和缺陷

与 vector 比较,deque 的 优势 是:

  • 头部插入和删除时,不需要搬移元素,效率特别高。
  • 扩容时,也不需要搬移大量的元素,因此其效率是比 vector 高的。

与 list 比较,其底层是连续空间空间利用率比较高,不需要存储额外字段。

但是, deque 有一个 致命缺陷

  • 不适合遍历,因为在遍历时,deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑 vector 和 list,deque 的应用并不多,而目前能看到的一个应用就是,STL 用其作为 stack 和 queue 的底层数据结构
  • 同时,deque 在中间插入删除数据,非常麻烦,效率很低。
deque 是一种折中方案的(妥协)设计,不够极致,随机访问效率不及 vector,任意位置插入删除不及 list,所以它能替代 vector 和 list 吗?

不能。


4、为什么选择deque作为stackqueue的底层默认容器

  • stack 是一种后进先出的特殊线性数据结构,因此只要具有 push_back() 和 pop_back() 操作的线性结构,都可以作为 stack 的底层容器,比如 vector 和 list 都可以;
  • queue 是先进先出的特殊线性数据结构,只要具有 push_back() 和 pop_front() 操作的线性结构,都可以作为 queue 的底层容器,比如 list。

但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器,主要是因为:
  1. stack 和 queue 不需要遍历(因此 stack 和 queue 没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在 stack 中元素增长时,deque 比 vector 的效率高(扩容时不需要搬移大量数据)。
  3. queue 中的元素增长时,deque 不仅效率高,而且内存使用率高。


相关文章
|
5天前
|
算法 前端开发 Linux
【常用技巧】C++ STL容器操作:6种常用场景算法
STL在Linux C++中使用的非常普遍,掌握并合适的使用各种容器至关重要!
32 10
|
2天前
|
存储 编译器 C++
|
7天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
16 4
|
5天前
|
NoSQL 关系型数据库 Redis
Docker的通俗理解和通过宿主机端口访问Redis容器的实例
本文目标:引导初学者入门Docker,理解镜像、容器和宿主机概念,学习常用Docker命令,特别是如何创建并从Redis容器通过宿主机端口访问。 关键点: - Docker核心:镜像(类)、容器(实例)、宿主机(运行环境)。 - `docker pull` 拉取镜像,如 `redis:3.0`。 - `docker run -d --name` 后台运行容器,如 `my-redis`。 - `-p` 参数做端口映射,如 `6379:6379`。 - `docker exec -it` 交互式进入容器,如 `bash` 或执行命令。
|
2天前
|
Cloud Native 安全 Docker
云上攻防-云原生篇&Docker安全&系统内核&版本&CDK自动利用&容器逃逸
云上攻防-云原生篇&Docker安全&系统内核&版本&CDK自动利用&容器逃逸
|
2天前
|
Linux Docker 容器
蓝易云 - net.ipv4.ip_forward=0导致docker容器无法与外部通信
完成以上步骤后,Docker容器应该能够正常与外部通信了。
8 2
|
2天前
|
Docker 容器
蓝易云 - Docker中容器的随机命名方式
例如,一个自动生成的容器名称可能是"happy_einstein"。这种随机命名方式既保证了容器名称的唯一性,又增加了一些趣味性。
7 2
|
2天前
|
前端开发 安全 数据库
Web架构&前后端分离站&Docker容器站&集成软件站&建站分配
Web架构&前后端分离站&Docker容器站&集成软件站&建站分配
|
5天前
|
监控 Java 数据安全/隐私保护
性能监控之 JMX 监控 Docker 容器中的 Java 应用
【6月更文挑战9天】性能监控之 JMX 监控 Docker 容器中的 Java 应用
25 1
|
9天前
|
运维 Ubuntu Docker
深入理解容器化技术:Docker的应用与实践
在这个数字化转型迅速推进的时代,容器化技术为软件开发和部署提供了新的路径。本文将深入探讨Docker技术的基本原理、应用场景以及实际操作,旨在帮助读者全面理解并掌握这一关键技术。
65 2