ʕ • ᴥ • ʔ
づ♡ど
🎉 欢迎点赞支持🎉
个人主页：励志不掉头发的内向程序员；
专栏主页：C++语言；
文章目录
前言
我们从上一章节学习的 stack/queue 中我们知道了什么是容器适配器，但是我们对于它们的默认容器 deque 还是比较陌生，我们本章节就是来了解这个容器的作用以及完善我们 stack/queue 的内容的，我们一起来看看吧。
一、deque 的简单介绍（了解）
我们对于 deque 的学习不会像前面的那些容器一样要实现，因为它的实现很复杂，而且也没有什么必要，我们能够简单了解即可。
deque 叫做双端队列，虽然是这么叫的，但是其实和我们的队列没有什么关系，队列要求先进先出，但是 deque 无所谓。它本质是一个缝合怪，它缝合了 vector、list。我们简单看看它在标准库的各种成员函数就能看出来。
我们 deque 既有头插头删，又有尾插尾删，还有 [ ] 符重载。既包含了 list，又包含了 vector。
deque 产生的原因是因为我们 vector 和 list 的优缺点太过于明显。
vector优点：
- 尾插尾删效率不错，支持高效下标随机访问。
- 物理空间连续，所以高速缓存利用率高。
vector缺点：
- 空间需要扩容，扩容有一些代价（效率和空间浪费）。
- 头部和中间的插入删除效率低。
list优点：
- 按需申请释放空间，不需要扩容。
- 支持任意位置的插入删除。
list缺点：
- 不支持下标随机访问。
所以我们为了融合它们的优点，就有人想出用 deque 这个缝合怪。
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。
但是这个设计其实也不是特别的成功，所以我们才不得不继续使用 vector 和 list。
1.1、deque 的原理介绍
我们 vector 是一个数组，它具有天然的优势，那就是下标的随机访问以及高速缓存的利用率等，但是缺点也就展露无遗。所以链表就搞出我们一块一块的独立的空间，这样我们想要插入数据就十分的方便，空间和空间是靠指针联系起来的。但是我们的物理空间不连续，我们的下标访问也就不支持了。
于是 deque 就决定搞出一段一段的数组，在这不同的小数组用一个叫做中控数组的数组相连，如果我们数据存满了也不用像 vector 一样全部扩容，而是直接开辟一个新数组出来，再用中控数组把它们连接在一起。
我们中控数组是一个指针数组。当我们中控数组满了就得扩容，然后把这些小数组拷贝到新的空间中去。
我们数据位置是这么计算的：
假设每个 buffer 数组大小是 N，求第 i 个数据
x = i / N // 算出是第几个 buffer 数组
y = i % N // 算出在 buffer 的第几个位置
ptr[ x ][ y ] // *(*(ptr + x) + y)
此时我们就可以通过下标快速的去访问 deque 的任意一个位置，虽然可能比 vector 慢一点，但是比起 list 来说就快多了。
我们想要了解明白它的结构，我们得理解清楚它的迭代器，它的迭代器有 4 个结构，也是 4 个指针。
first 和 last 分别指向 buffer 数组的开始和结束，cur 则代表我们在访问 buffer 数组的第几个数据，还有一个 node 的二级指针，这个指针是反过来指向我们中控数组上 buffer 数组存在的位置的。
它具体的结构是张这样的。
deque 中的主要成员变量就两个，是 start，finish。start 就 begin 返回的迭代器，finish就是 end 返回的迭代器。
它的迭代器遍历的执行流程。
我们一般在我们 cur 指向我们的末端之前，我们 ++ 都只要 cur++ 即可，当我们的 cur 指向我们数组末尾了，此时我们可以通过我们迭代器的二级指针 node 找到我们 buffer 数组在中控数组的位置，然后加到下一个数组。此时让我们的把迭代器更新，让我们的 first 和 cur 指向新数组的开始，而 last 指向我们这个数组的末尾，node 指向我们我们中控数组指向的位置，即可实现迭代器也就指向下一个位置了。
而 deque 的尾插就直接找到 finish 即可，如果我们 cur != last 就是还没满，我们直接让 cur++ 即可。如果满了就创建一个新的数组，然后用我们 finish 迭代器中的 node 找到我们中控数组的下一个数组位置，然后把新开辟的数组地址给我们中控数组，然后再更新 finish 指针即可。
我们 deque 的中控数组一般是不会把我们第一个 buffer 数组存到我们的第一个位置的，而是一般会存到中间位置，这样我们的前面可以给我们进行头插操作，我们头插和尾插没有什么区别，如果我们的start迭代器中 cur == first，此时我们依旧会开辟一个 buffer 数组，然后通过 start 的 node 去找到 start 在中控数组的位置（因为是存在中间，所以前面才有位置）。然后找到其前一个位置后将 buffer 数组的地址记录到中控数组上，然后更新我们的 start 迭代器即可。
deque头插尾插效率十分高，它既没有 vector 那么高代价的扩容，也没有那么 list 细碎的开空间。deque 下标随机访问效率也不错，但是比不上 vector。
它也支持 insert 和 erase，但是它的效率会非常低，因为它也要移动数据。所以说如果有一个只需要头插头删和尾插尾删的结构去使用它，这样就可以充分利用 deque 容器的优势了。这就是为什么我们 stack/queue 要使用我们 deque 做默认容器的原因。
1.2、deque 的设计缺陷
与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
二、priority_queue 的介绍和使用
2.1、priority_queue 的介绍
我们在看库中的 queue 时，可能就在下面看到它的身影了。
它也是是一个容器适配器，叫做优先级队列。它的成员函数和我们的 stack 非常像。
它的重点是它的 top 和 pop 不是取最后进入或者最先进入的数据，而是取优先级最高的数据。它这里默认是取数值越大的优先级越高。我们堆的底层是一个数组，所以我们默认适配容器就是我们的 vector。
2.2、priority_queue 的使用
它可以使用默认构造和迭代器构造。
int main()
{
// 默认构造
priority_queue<int> pq1;
// 迭代器构造
vector<int> a({ 1, 2, 3, 4, 5, 6, 7, 8, 9 });
priority_queue<int> pq2(a.begin(), a.end());
return 0;
}同时它的特点就是先从优先级最高的取用。然后就是第二高的以此类推。
int main()
{
priority_queue<int> pq;
pq.push(3);
pq.push(4);
pq.push(1);
pq.push(5);
pq.push(0);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
我想让他改变我们的优先级就得靠我们第三个参数了。
我们可以看到我们第三个参数默认是 less，如果想变成小堆就得传一个叫 greater<T> 在第三个参数。
int main()
{
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(3);
pq.push(4);
pq.push(1);
pq.push(5);
pq.push(0);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
2.3、priority_queue 的实现
我们依旧先来看看它的基本框架。
namespace zxl
{
template<class T, class Container = std::vector<T>>
class priority_queue
{
public:
private:
Container _con;
};
}再来实现它的各项接口。
namespace zxl
{
template<class T, class Container = std::vector<T>>
class priority_queue
{
public:
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (_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);
AdjustUp(_con.size() - 1);
}
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child] < _con[child + 1])
{
++child;
}
if (_con[parent] < _con[child])
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0);
}
T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
}主要就是用到了我们的堆，其他的很简单，如果有小伙伴看不懂我们可以去看看数据结构的堆。这就是简单的优先级队列。
我们大家可能有的时候有想要改变我们优先级的比较方式，我们这里是写死的，但是库里面却不是这样的，我们想要完成库里面的功能，得用到一个叫仿函数的东西。
首先我们得知道，其实我们的仿函数就是一个类，我们这里写一个 Less 的类。在这个类里面我们得重载一个（）。这个（）是在函数后面的（）。
class Less
{
public:
bool operator()(int x, int y)
{
return x < y;
}
};我们的仿函数一般就是空类，类的大小就是1。我们再改造改造就可以改造成模板。
template <class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};我们可以这样调用我们的仿函数。
int main()
{
Less<int> LessFunc;
cout << LessFunc(1, 2) << endl;
return 0;
}如果我不说，我们肯定很多人就认为这里的 LessFunc 是一个函数，这就是仿函数名字的由来，它本质是一个类，但是这个对象可以像函数一样使用。它本质其实是这样的。
int main()
{
Less<int> LessFunc;
cout << LessFunc.operator()(1, 2) << endl;
return 0;
}我们除了写 Less 外还可以写一个 Greater。
template <class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};和 Less 一样，不过一个大于一个小于。它的作用主要就是改变我们的比较方式，我们通过仿函数来修改我们的优先级队列。
我们的基本框架就变成这样了。
namespace zxl
{
template<class T, class Container = std::vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
private:
Container _con;
};
}而我们只需要修改我们有比较逻辑的两个成员函数即可。
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
//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 AdjustDown(int parent)
{
Compare com;
int child = parent * 2 + 1;
while (child < _con.size())
{
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
++child;
}
//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;
}
}
}这样我们就实现了我们库中一样的效果了。
int main()
{
zxl::priority_queue<int> pq;
pq.push(4);
pq.push(5);
pq.push(1);
pq.push(8);
pq.push(0);
while (!pq.empty())
{
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << std::endl;
return 0;
}
int main()
{
zxl::priority_queue<int, vector<int>, Greater<int>> pq;
pq.push(4);
pq.push(5);
pq.push(1);
pq.push(8);
pq.push(0);
while (!pq.empty())
{
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << std::endl;
return 0;
}
这就是仿函数的作用。
总结
以上便是我们 stack/queue 的全部内容了，其实我们学习各种容器是没有必要都去实现，我们前面去实现的原因是为了让我们的代码功底能够更加的强劲，等到了后期，我们只需要能够用它们的成员函数即可，实在不清楚的才需要看看源码。所以现在的努力是为了以后的轻松。大家加油。
🎇坚持到这里已经很厉害啦，辛苦啦🎇
ʕ • ᴥ • ʔ
づ♡ど
