文章目录

1、容器适配器
- 1.1 什么是适配器
- 1.2 STL标准库中stack和queue的底层结构
- 1.3 deque的简单介绍
2、stack的介绍和使用
- 2.1 stack的介绍
- 2.2 stack的使用
- 2.3 stack的模拟实现
3、queue的介绍和使用
- 3.1 queue的介绍
- 3.2 queue的使用
- 3.3 queue的模拟实现
4、priority_queue的介绍和使用
- 4.1 priority_queue的介绍
- 4.2 priority_queue的使用
- 4.3 priority_queue的模拟实现

1、容器适配器

1.1 什么是适配器

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

1.2 STL标准库中stack和queue的底层结构

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

在这里插入图片描述

1.3 deque的简单介绍

deque(双端队列)：是一种双开口的”连续”空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
在这里插入图片描述
deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

详细过程：

deque的优缺点：
1、与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
2、与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
3、deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。

2、stack的介绍和使用

2.1 stack的介绍

stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
在这里插入图片描述

2.2 stack的使用

在这里插入图片描述

2.3 stack的模拟实现

#pragma once
#include <vector>
namespace bite
{
    template<class T>
    class stack
    {
    public:
        stack()
        {
    }
        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();
        }
        int size()const
        {
            return _con.size();
        }
        bool empty()const
        {
            return _con.empty();
        }
    private:
        std::vector<T> _con
    };
}

3、queue的介绍和使用

3.1 queue的介绍

队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
在这里插入图片描述

3.2 queue的使用

在这里插入图片描述

3.3 queue的模拟实现

#pragma once
#include <list>
namespace bite
{
    template<class T>
    class queue
    {
    public:
        queue()
        {
    }
        void push(const T& x)
        {
            q.push_back(x);
        }
        void pop()
        {
            q.pop_front();
        }
        T& front()
        {
            return q.front();
        }
        const T& front()const
        {
            return q.front();
        }
        T& back()
        {
            return q.back();
        }
        const T& back()const
        {
            return q.back();
        }
        size_t size()const
        {
            return q.size();
        }
        bool empty()const
        {
            return q.empty();
        }
    private:
        std::list<T> q;
    };
}

4、priority_queue的介绍和使用

4.1 priority_queue的介绍

优先级队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

4.2 priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

4.3 priority_queue的模拟实现

#pragma once
#include <vector>
namespace bite
{
    template<class T,class Con=vector<T>,class CMP=less<T>>
    class priority_queue
    {
    public:
        priority_queue()
        {
    }
        template<class Iterator>
        priority_queue(Iterator first, Iterator last)
            : _con(first, last)
        {
            int root = ((_con.size() - 2) >> 1);
            while (root >= 0)
            {
                _AdjustDown(root);
                root--;
            }
        }
        void push(const T& x)
        {
            _con.push_back(x);
            _AdjustUp();
        }
        void pop()
        {
            if (empty())
                return;
            swap(_con.front(), _con.back());
            _con.pop_back();
            _AdjustDown(0);
        }
        const T& top()const
        {
            return _con.front();
        }
        size_t size()const
        {
            return _con.size();
        }
        bool empty()const
        {
            return _con.empty();
        }
    private:
        //´´½¨Ð¡¶Ñ
        void _AdjustDown(size_t parent)
        {
            size_t child = parent * 2 + 1;
            size_t size = _con.size();
            CMP cmp;
            while (child < size)
            {
                if (child + 1 < size&&cmp(_con[child], _con[child + 1]))
                    child += 1;
                if (CMP()(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                    break;
            }
        }
        void _AdjustUp()
        {
            size_t child = _con.size() - 1;
            size_t parent = ((child - 1) >> 1);
            while (child)
            {
                if (CMP()(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    child = parent;
                    parent = ((child - 1) >> 1);
                }
                else
                    break;
            }
        }
    private:
        Con _con;
    };
}