【C++】stack && queue && priority_queue的模拟实现

目录

一、容器适配器

二、deque的基本介绍

1、简介

2、deque的底层

3、对比

三、stack的模拟实现

四、queue的模拟实现

五、priority_queue的模拟实现

总结

---

前言

以上三个STL中的组件，并不是像vector，list，string一样，它们不是容器，而是容器适配器。

---

一、容器适配器

容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。

其实，容器适配器中的“适配器”，和生活中常见的电源适配器中“适配器”的含义非常接近。我们知道，无论是电脑、手机还是其它电器，充电时都无法直接使用 220V 的交流电，为了方便用户使用，各个电器厂商都会提供一个适用于自己产品的电源线，它可以将 220V 的交流电转换成适合电器使用的低压直流电。从用户的角度看，电源线扮演的角色就是将原本不适用的交流电变得适用，因此其又被称为电源适配器。
 

容器适配器本质上还是容器，只不过此容器模板类的实现，利用了大量其它基础容器模板类中已经写好的成员函数。当然，如果必要的话，容器适配器中也可以自创新的成员函数。

C++中一共有三个容器适配器，分别是stack，queue和priority_queue

stack和queue默认使用的容器是deque，priority_queue默认使用的是vector

二、deque的基本介绍

1、简介

deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和 删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的。

2、deque的底层

deque也有节点，但是它的节点与list的不同，deque的一个节点具有很多个value，并不像list一样一个节点具有一个value。

图片里面的map是一个二级指针它指向中控数组，该数组是一个指针数组，里面存放的是每个节点的地址。换句话说deque是由一个一个小buffer数组组成的，例如它现在有三个小数组

其中一个数组存放的是头插的数据，另一个数组存放的是尾插的数据，另外存放的是中间的数据，如果deque满了，它不会扩容，然后挪动数据，而是会再次开辟一个新的buffer数组。

它的方括号的实现思路是，假如访问的是下标为i的元素

首先：i - 第一个buffer的元素个数 / 每个buffer数组能够存放元素的个数，确定出该元素存储在第几个buffer。

然后：i- 第一个buffer的元素个数 % 每个buffer数组能够存放的元素个数，确定是那个buffer的第几个。 

3、对比

它就好像是vector和list的结合版，它既有vector的所有接口，同时还拥有list的全部接口，看样子他十分的NB，但实际上却不然，因为如果他这么NB，我们直接学习它不就行吗，为什么还要学习这个？

与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不 需要搬移大量的元素，因此其效率比vector高。

与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段，并且支持随机访问，具有[ ]

但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构 时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作 为stack和queue的底层数据结构。

 

由此可得：deque非常适合头尾的插入和删除，这与栈和队列的特性一致，所以采用deque来作为栈和队列的默认容器

三、stack的模拟实现

stack的C语言版本的模拟实现，我们在前面的博客中已经完成了，所以在这里的实现我们只说明C++不同的地方

#include 
#include 
 
using namespace std;
 
namespace ww
{
    template<class T, class Container = deque>
    class stack 
    {
    public:
        void push(const T& x)
        {
            _con.push_back(x);
        }
 
        void pop()
        {
            _con.pop_back();
        }
 
        T& top()
        {
            return _con.back();
        }
 
        const T& top()const 
        {
            return _con.back();
        }
 
        bool empty()const 
        {
            return _con.empty();
        }
 
        size_t size()const 
        {
            return _con.size();
        }
 
    private:
        Container _con;
    };

四、queue的模拟实现

#include 
#include 
 
using namespace std;
 
namespace ww
{
    template<class T, class Container = deque>
    class queue 
    {
    public:
        void push(const T& x)
        {
            _con.push_back(x);
        }
 
        void pop()
        {
            _con.pop_front();
        }
 
        T& back()
        {
            return _con.back();
        }
 
        const T& back()const 
        {
            return _con.back();
        }
 
        T& front()
        {
            return _con.front();
        }
 
        const T& front()const 
        {
            return _con.front();
        }
 
        bool empty()const 
        {
            return _con.empty();
        }
 
        size_t size()const 
        {
            return _con.size();
        }
 
    private:
        Container _con;
    };

五、priority_queue的模拟实现

我们重点说明priority_queue，它的本质就是堆，而堆我再以前的博客中也实现了，感兴趣的同学可以翻看我以前的博客，来查看C语言版本的堆。

这里与C语言不同的地方在于，它多了一个仿函数的概念

而什么是仿函数呢？

仿函数(functor)，就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了。

仿函数又叫做函数对象，使类对象可以像函数一样去使用

我们手动实现一个简单的仿函数

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

这就是两个简单的仿函数

#include
 
using namespace std;
 
namespace ww
{
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y)const
		{
			return x < y;
		}
	};
 
	template<class T>
	struct biger
	{
		bool operator()(const T& x, const T& y)const
		{
			return x > y;
		}
	};
 
}
 
 
int main()
{
	ww::less<int> ls;
	ww::biger<int> bg;
	cout << ls(2, 3) << endl;
	cout << bg(5, 7) << endl;
	return 0;
}

结果正确，与我们的设想的一致，并且我们使用这个类就如同函数调用一样。

有了以上的铺垫，我们也就明白了仿函数

priority_queue就是利用仿函数来控制，实例化的对象是大根堆还是小根堆

除此之外，就与普通的堆没有什么差别了，堆的基本实现方法也已在前面的博客中涉及，不在此赘述

#include 
#include 
 
using namespace std;
 
namespace ww
{
    //默认大堆
    template<class T, class Container = vector, class Compare = std::less>
    class priority_queue
    {
    public:
 
        priority_queue()
        {
 
        }
 
        
        template<class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
        {
            while(first != last)
            {
                _con.push_back(*first);
                first++;
            }
 
            for(int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
            {
                adjust_down(i);
            }
        }
 
        void adjust_down(size_t parent)
        {
            Compare com;
            size_t child = parent * 2 + 1;
            while(child < _con.size())
            {
                //if(child + 1 < _con.size() && _con[child+1] > _con[child])
                //if(child + 1 < _con.size() && _con[child] < _con[child+1])
                if(child + 1 < _con.size() && com(_con[child], _con[child+1]))
                {
                    child++;
                }
 
                //if(_con[child] > _con[parent])
                //if(_con[parent] < _con[child])
                if(com(_con[parent], _con[child]))
                {
                    std::swap(_con[child], _con[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else 
                {
                    break;
                }
            }
        }
 
        void adjust_up(size_t child)
        {
            Compare com;
            size_t parent = (child - 1) / 2;
            while(child > 0)
            {
                //if(_con[child] > _con[parent])
                //if(_con[parent] < _con[child])
                if(com(_con[parent], _con[child]))
                {
                    std::swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else 
                {
                    break;
                }
            }
        }
 
        void push(const T& x)
        {
            _con.push_back(x);
            adjust_up(_con.size() - 1);
        }
 
        void pop()
        {
            std::swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
 
            adjust_down(0);
        }
 
        const T& top()
        {
            return _con[0];
        }
 
        bool empty()const 
        {
            return _con.empty();
        }
 
        size_t size()const 
        {
            return _con.size();
        }
 
    private:
        Container _con;
    };
}

 

在这里说明一下为什么要显式的写构造函数，因为我们已经实现了用迭代器区间的构造函数，而只要显式的写了构造函数编译器就不会自动生成，默认构造函数了，这会在某些的场景出错。

---

总结

以上就是今天要讲的内容，我们会发现STL已经过半了，并且他们的实现接口类似，实现的手段也类似。