文章目录
一. deque简单介绍
1.1 deque的功能介绍
deque(双端队列)：是一种双开口的连续空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要挪动元素；与list比较，空间利用率比较高。
1.2 deque的本体框架
虽说是连续性存储空间，但这种连续性只是表面上的，实际上它在堆上分配了一块一块的动态储存区，叫做缓冲区（buff），每一块缓冲区本身是连续的，deque自身的机制把这一块一块的缓冲区虚拟地连在一起，即把它们的首元素地址存在一个指针数组map里，注意这里的map不是STL里的map容器，而是deque的中控器，是个指针数组。
template<class T>
class deque
{
protected:
iterator start; // 指向指针数组第一个元素的迭代器
iterator finish;// 指向指针数组最后一个元素的迭代器
T** map; // 中控的指针数组
size_t map_size;// 指针数组大小
};
为了满足头尾的插入删除，一开始的buff会放到中间位置，这样如果有需要的话，往前往后都可以存buff。当map指向的这块空间不够存放内存指针的时候，就会另觅一块更大的连续性空间，然后把指针一个一个复制过去，并销毁旧的空间。利用这种数据结构，deque就能方便地模拟自身的存储区是连续性空间的假象，并且可以实现双向插入删除的功能。
1.3 deque的迭代器框架
迭代器就是模拟指针的操作，比如解引用得到具体的数据，箭头访问内部成员变量，自增、自减等等操作。那么deque的迭代器应该具备怎么结构？我们可以考虑以下几点。首先，需要知道该元素位于哪个buff的哪个位置；其次，一旦迭代器前进和后退有可能会跳跃至上一个或下一个缓冲区，为了判断跳跃的条件就需要知道，当前元素所在buff的首尾指针。最后，如果前进或后退必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃，deque必须随时掌握管控中心（map），通过map可以知道跳跃的缓冲区。 所以在迭代器中需要定义如下参数：
template<class T, class Ref, class Ptr, size_t N>
struct _deque_iterator
{
T* cur; //指向buff里面当前数据的位置
T* first;//buff第一个位置指针
T* last; //buff最后一个位置指针
T** node;//map中控中当前buff的地址
}
迭代器和中控器之间的关系如下图所示
1.2 deque的优缺点
优点
- 与vector相比：头部和中间的插入删除不需要大量挪动数据，时间复杂的为O(1)；扩容时也不需要大量挪动数据。
- 与list相比：空间利用率较高，内存碎片少，不是需要一个才开辟一个。
缺点
不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下。
总结
因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
二. 容器适配器
2.1 什么是适配器
适配器是一种设计模式，该种模式是将一个类进行封装，利用原来类的接口转换成客户希望的另外一个接口。
2.2 STL标准库中的stack和queue底层结构
虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为stack和队列只是对其他容器的接口进行了包装，其中STL中stack和queue默认容器使用deque。
2.3 stack和queue的模拟实现
2.3.1 stack容器剖析
两者的实现原理一样，下面我们主要分析stack的实现
stack要做到存储不同类型数据，那就应该是个类模板，模板参数是要存储的数据的类型和底层容器的种类。
注意：容器也是可以作为模板参数的，因为模板作用就是处理不同类型但逻辑相同的问题，我们对传入的不同类型统一管理，像vector，list等容器算自定义类型，我们也可以作为模板参数传入。
stack的框架
成员变量只有一个，就是底层的容器的一个实例化对象
// 这里我们的底层容器默认缺省是deque
template<class T, class Container = deque<T>>
class stack
{
public:
// 构造函数
stack()
// 调用容器的无参的默认构造函数
:_con()
{}
private:
// 底层结构，即容器对象
Container _con;
};
入栈
只能栈顶入数据，就是deque的尾插，对应调用底层容器deque的push_back()
PS:直接调用就行，不用考虑空间不够增容的问题，这些归底层容器deque管
// 入栈
void push(const T& data)
{
_con.push_back(data);
}
出栈
从栈顶出，就是deque的尾删，封装deque的back_pop()
// 出栈
void pop()
{
_con.pop_back();
}
获取栈顶元素
就是获取deque的最后一个元素，这里要注意不同stack对象调用对应的返回值不同，所以有下面两种写法：const的栈对象返回const的值，非const的栈对象返回非const的值。
// 普通对象获取栈顶元素
T& top()
{
return _con.back();
}
// const对象获取栈顶元素
const T& top()const
{
return _con.back();
}
stack的完整模拟实现
template<class T,class Container=deque<T>>
class stack
{
public:
// 构造函数
stack()
:_con()
{}
// 入栈
void push(const T& data)
{
_con.push_back(data);
}
// 出栈
void pop()
{
_con.pop_back();
}
// 判空
bool empty()
{
return _con.empty();
}
// 长度
size_t size()
{
return _con.size();
}
// 普通对象获取栈顶元素
T& top()
{
return _con.back();
}
// const对象获取栈顶元素
const T& top()const
{
return _con.back();
}
private:
// 底层容器
Container _con;
};
2.3.2 queue的完整模拟实现
与stack大同小异，由于两者的特性不同（stack是后进先出，queue是先进先出），对应容器调用的接口也就不一样。
template<class T,class Container=deque<T>>
class queue
{
public:
// 构造函数
queue()
:_con()
{}
// 队列尾部插入元素
void push(const T& data)
{
_con.push_back(data);
}
// 队列头部出元素
void pop()
{
_con.pop_front();
}
// 返回队列当前元素个数
size_t size()
{
return _con.size();
}
// 判断队列是否为空
bool empty()
{
return _con.empty();
}
// 普通对象直接返回对头元素的引用（可修改）
T& front()
{
return _con.front();
}
// const对象返回对偷的元素不能修改
const T& front()const
{
return _con.front();
}
// 普通对象直接返回对尾元素的引用（可修改）
T& back()
{
return _con.back();
}
// const对象返回对尾的元素不能修改
const T& back()const
{
return _con.back();
}
private:
Container _con;
};
三. priority_queue
3.1 priority_queue介绍
- 优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆。所有需要用到堆的场景，都可以考虑使用priority_queue（注意默认情况下priority_queue是大堆）
- 它的接口和栈的接口类似
push()：数据进堆
pop()：删除堆顶数据
top()：拿到堆顶数据
empty()：堆是否为空？为空的话返回true，不空返回false
size()：当前堆元素的数量
3.2 priority_queue的模拟实现
PS：容器vector的数据位置要用到堆结构处理，堆的知识和相关堆算法，这些堆的内容可以参考下面文章：二叉树和堆
仿函数：
定义一个类专门重载operator()，使该类实例化出来的对象可以像调用函数一样的调用，从而实现特定功能，你如比较两个数据的大小。
priority的基本框架
-
模板参数，除了数据类型和容器，还加了仿函数类Compare，为了使用户可以自主选择大堆和小堆才引入的，当然默认情况是大堆，根STL里一致，大堆传less的仿函数，小堆传greater
-
仿函数我们在priority_queue外单独定义
// 仿函数less
template<class T>
struct less
{
bool operator()(const T& x1, const T& x2)
{
return x1 < x2;
}
};
// 仿函数greater
template<class T>
struct greater
{
bool operator()(const T& x1, const T& x2)
{
return x1 > x2;
}
};
// priority_queue
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
// 无参的默认构造函数
priority_queue()
:_con()
{}
private:
Container _con;
};
堆的向上和向下调整算法
我们尾部插入元素要利用向上调整算法调堆，删除堆顶元素要用向下调整算法调堆。只是在插入和删除操作时调用，一般外部不用直接调用（因为没意义），所以我们把这两个算法设置成私有。
但不能把他们设置为内联，因为他们内部有循环操作，且代码较长。
private:
// 向下调整算法
void AdjustDown(int parent)
{
int n = _con.size();
int child = parent * 2 + 1;
while(child < n)
{
if (child + 1 < n&&Compare()(_con[child], _con[child + 1]))
{
++child;
}
if (Compare()(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}
// 向上调整算法
void AdjustUp(int child)
{
int n = _con.size();
while (child > 0)
{
int parent = (child - 1) / 2;
if (Compare()(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
}
else
{
return;
}
}
}
Container _con;
用迭代器区间构造一个priority_queue对象
像下图一样构造一个优先级队列的对象
template<class Iterator>
priority_queue(Iterator first, Iterator last)
// 先把数据存入容器对象
: _con(first, last)
{
// 向下调整法建堆
int n = _con.size();
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
入队列
就是vector的尾插，再把插入的元素向上调整，保持堆的结构
// 入队列
void push(const T& data)
{
_con.push_back(data);
AdjustUp(_con.size()-1);
}
出队列
删除堆顶元素。交换一下堆顶和堆底元素，不用重新建堆，vector尾删，最后在给堆顶元素进行向下调整算法。
// 出队列
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
获取堆顶元素
堆顶元素不允许修改，因为：堆顶元素修改可以会破坏堆的特性。
// 获取栈顶（堆顶）元素
const T& top()const
{
return _con.front();
}
完整代码
#include<iostream>
#include<vector>
using namespace std;
namespace MyPriorityQueue
{
// 仿函数less
template<class T>
struct less
{
bool operator()(const T& x1, const T& x2)
{
return x1 < x2;
}
};
// 仿函数greater
template<class T>
struct greater
{
bool operator()(const T& x1, const T& x2)
{
return x1 > x2;
}
};
// priority_queue
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue
{
public:
// 无参的默认构造函数
priority_queue()
:_con()
{}
// 传迭代对应容器类型对象的迭代器来构造
template<class Iterator>
priority_queue(Iterator first, Iterator last)
: _con(first, last)
{
// 向下调整法建堆
int n = _con.size();
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(i);
}
}
// 入队列
void push(const T& data)
{
_con.push_back(data);
AdjustUp(_con.size()-1);
}
// 出队列
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
// 长度
int size()const
{
return _con.size();
}
// 判空
bool empty()const
{
return _con.empty();
}
// 获取栈顶（堆顶）元素
const T& top()const
{
return _con.front();
}
private:
// 向下调整算法
void AdjustDown(int parent)
{
int n = _con.size();
int child = parent * 2 + 1;
while(child < n)
{
if (child + 1 < n&&Compare()(_con[child], _con[child + 1]))
{
++child;
}
if (Compare()(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}
// 向上调整算法
void AdjustUp(int child)
{
int n = _con.size();
while (child > 0)
{
int parent = (child - 1) / 2;
if (Compare()(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
}
else
{
return;
}
}
}
private:
Container _con;
};
void test()
{
vector<int> v = { 2,1,3,3,2,0,6 };
priority_queue<int> p(v.begin(), v.end());
}
}