【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

简介: 【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

一、容器适配器

1、什么是容器适配器

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

例如我们常见的充电器就是一种适配器,它将我们常用的220V交流电压转化为4,5V (或者其他更高的电压) 的直流电压来给我们的电子设备进行充电。

2、STL标准库中的容器适配器

虽然stackqueuepriority_queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配

器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stackqueue默认使用dequepriority_queue默认使用了vector

二、stack的模拟实现

1、stack的简单介绍

相关文档

stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,但这些容器类应该支持以下操作:

  • empty:判空操作
  • back:获取尾部元素操作
  • push_back:尾部插入元素操作
  • pop_back:尾部删除元素操作

标准容器vectordequelist均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque

2、栈的模拟实现

为了栈的通用性,这里我们使用模板来进行模拟栈,关于栈的底层容器这里我们选择vector来进行模拟实现。

template<class T, class Container = vector<T>>
class stack
{
public:
  //栈的插入
  void push(const T& val)
  {
    //使用底层容器中尾插函数进行插入,栈只能进行栈顶插入和删除
    _con.push_back(val);
  }
  //栈的删除
  void pop()
  {
    //使用底层容器中尾删函数进行插入,栈只能进行栈顶插入和删除
    _con.pop_back();
  }
  //获取栈顶元素
  T& top()
  {
    //返回底层容器中最后一个数据
    return _con.back();
  }
  //const 版本
  const T& top() const
  {
    return _con.back();
  }
  //获取数据个数
  size_t size() const
  {
    //返回底层容器中数据的个数
    return _con.size();
  }
  //判空函数
  bool empty() const
  {
    //对底层容器进行判空
    return _con.empty();
  }
private:
  //成员变量是一个容器创建的对象
  Container _con;
};

三、queue的模拟实现

1、queue的简单介绍

相关文档

queue底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push_back:在队列尾部入队列
  • pop_front:在队列头部出队列

标准容器类dequelist满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque

2、queue的模拟实现

为了queue的通用性,这里我们使用模板来进行模拟queue,关于queue的底层容器这里我们选择list来进行模拟实现。

template<class T, class Container = list<T>>
class queue
{
public:
  //队列的插入
  void push(const T& val)
  {
    //使用底层容器中尾插函数进行插入,队列只能进行队尾插入
    _com.push_back(val);
  }
  //队列的删除
  void pop()
  {
    //使用底层容器中头删函数进行删除,队列只能进行队头删除
    _com.pop_front();
  }
  //获取队头数据
  T& front()
  {
    //返回底层容器中第一个数据
    return _com.front();
  }
  //const版本
  const T& front() const
  {
    return _com.front();
  }
  //获取队尾数据
  T& back()
  {
    //返回底层容器中最后一个数据
    return _com.back();
  }
  //const版本
  const T& back() const
  {
    return _com.back();
  }
  //获取数据个数
  size_t size() const
  {
    //返回底层容器中数据的个数
    return _com.size();
  }
  //判空函数
  bool empty() const
  {
    //对底层容器进行判空
    return _com.empty();
  }
private:
  //成员变量是一个容器创建的对象
  Container _com;
};

四、priority_queue的模拟实现

1、priority_queue的简单介绍

相关文档

优先队列是一种容器适配器,它其实就是我们数据结构中的,默认情况下priority_queue是大堆。

priority_queue底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:

  • empty:检测容器是否为空
  • size:返回容器中有效元素个数
  • front:返回容器中第一个元素的引用
  • push_back:在容器尾部插入元素
  • pop_back:删除容器尾部元素

标准容器类vectordeque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector

2、priority_queue的模拟实现

与前面的栈与队列一样priority_queue前两个模板参数都类似,但是priority_queue要有第三个模板参数,这个参数表示按照什么方式进行比较,即建立大堆还是小堆。

//第三个参数是比较方式,需要传递一个仿函数来确定比较方式,默认传递的是less<T>,表示建大堆
template<class T, class Container = vector<T>, class Comper = less<T>>
class priority_queue
{
public:
  //获取堆顶数据
  const T& top() const
  {
    //返回底层容器的第一个数据
    return _con.front();
  }
  //获取数据个数
  size_t size() const
  {
    //返回底层容器的数据个数
    return _con.size();
  }
  //判空函数
  bool empty() const
  {
    //判断底层容器是否为空
    return _con.empty();
  }
  //堆的插入
  void push(const T& val)
  {
    //从尾部插入
    _con.push_back(val);
    int child = _con.size() - 1;
    //向上调整重新建堆
    AdjustUp(child);
  }
  //堆的删除
  void pop()
  {
    //检查堆是否为空
    assert(!_con.empty());
    //交换堆顶与最后一个数据
    swap(_con.front(), _con.back());
    //删除最后一个数据
    _con.pop_back();
    //从堆顶进行向下调整,重新建堆
    AdjustDown(0);
  }
private:
  //向上调整算法
  void AdjustUp(int child)
  {
    Comper com;
    int parent = (child - 1) / 2;
    while (child > 0)
    {
      //这里使用了仿函数来判断建立什么堆
      //比较的位置(_con[parent], _con[child])是不能换的!!!
      if (com(_con[parent], _con[child]))
      {
        swap(_con[parent], _con[child]);
        child = parent;
        parent = (child - 1) / 2;
      }
      else
      {
        break;
      }
    }
  }
  //向下调整算法
  void AdjustDown(int parent)
  {
    Comper com;
    //默认左孩子更符合建堆的要求
    int child = parent *2 + 1;
    while (child < _con.size())
    {
      if (child + 1 < _con.size() && Comper()(_con[child], _con[child + 1]))
      {
        ++child;
      }
      if (com(_con[parent], _con[child]))
      {
        swap(_con[parent], _con[child]);
        parent = child;
        child = parent * 2 + 1;
      }
      else
      {
        break;
      }
    }
  }
  //成员变量是一个容器创建的对象
  Container _con;
};
相关文章
|
20天前
|
设计模式 程序员 C++
【C++ 泛型编程 高级篇】C++模板元编程:使用模板特化 灵活提取嵌套类型与多容器兼容性
【C++ 泛型编程 高级篇】C++模板元编程:使用模板特化 灵活提取嵌套类型与多容器兼容性
193 2
|
算法 程序员 C语言
【C++ 迭代器】深入探讨 C++ 迭代器:标准与自定义容器中的 begin() 和 cbegin()
【C++ 迭代器】深入探讨 C++ 迭代器:标准与自定义容器中的 begin() 和 cbegin()
46 0
|
20天前
|
存储 安全 编译器
【C++ 17 泛型容器对比】C++ 深度解析:std::any 与 std::variant 的细微差别
【C++ 17 泛型容器对比】C++ 深度解析:std::any 与 std::variant 的细微差别
44 1
|
21天前
|
存储 安全 算法
【C++ 17 包裹类 泛型容器 std::any】深入理解与应用C++ std::any:从泛型编程到多态设计
【C++ 17 包裹类 泛型容器 std::any】深入理解与应用C++ std::any:从泛型编程到多态设计
46 1
|
1月前
|
Java Go 开发者
Docker容器技术简介及其与Go语言的结合点
【2月更文挑战第23天】本文首先概述了Docker容器技术的核心概念和优势,接着探讨了Go语言与Docker容器技术的结合点。通过阐述Docker的轻量级、可移植性和版本控制等特性,以及Go语言在容器化应用中的优势,本文旨在说明两者结合能够实现更高效、灵活的应用开发和部署。
|
1月前
|
Oracle 关系型数据库 数据库
|
5天前
|
Linux Docker 容器
docker 容器常用命令
docker 容器常用命令
10 0
|
14天前
|
Kubernetes 网络协议 Docker
Docker 容器的DNS
Docker 容器的DNS
22 1
|
17天前
|
关系型数据库 MySQL Nacos
【深入浅出Nacos原理及调优】「实战开发专题」采用Docker容器进行部署和搭建Nacos服务以及“坑点”
【深入浅出Nacos原理及调优】「实战开发专题」采用Docker容器进行部署和搭建Nacos服务以及“坑点”
41 1
|
21天前
|
监控 数据可视化 虚拟化
Docker容器常用命令笔记分享
Docker容器常用命令笔记分享
49 2