网站首页导航代码,it网站设计培训,电脑怎样做幻灯片的网站,互联网排名前十的公司2021STL容器适配器之stack、queue剖析 一、stack、queue的接口#xff08;一#xff09;stack 接口说明#xff08;二#xff09;queue 接口说明 二、stack、queue的模拟实现#xff08;一#xff09;stack、queue是容器适配器stack、queue底层默认容器--deque1、deque概念及… STL容器适配器之stack、queue剖析 一、stack、queue的接口一stack 接口说明二queue 接口说明 二、stack、queue的模拟实现一stack、queue是容器适配器stack、queue底层默认容器--deque1、deque概念及原理2、stl中deque迭代器的实现部分 二stack的模拟实现三queue的模拟实现 三、优先队列一优先队列的概念二优先队列的接口说明三优先队列的模拟实现 四、结束语 一、stack、queue的接口
一stack 接口说明
stack() 构造空的栈 empty() 检测stack是否为空 size() 返回stack中元素的个数 top() 返回栈顶元素的引用 push() 将元素val压入stack中 pop() 将stack中尾部的元素弹出
二queue 接口说明
empty 检测队列是否为空 size 返回队列中有效元素的个数 front 返回队头元素的引用 back 返回队尾元素的引用 push_back 在队列尾部入队列 pop_front 在队列头部出队列
二、stack、queue的模拟实现
一stack、queue是容器适配器 虽然stack和queue中也可以存放元素但在STL中并没有将其划分在容器的行列而是将其称为容器适配器这是因为stack和queue只是对其他容器的接口进行了包装STL中stack和queue默认使用deque. stack、queue底层默认容器–deque
1、deque概念及原理
deque(双端队列)可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个 动态的二维数组其底层结构如下图所示 双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问 的假象落在了deque的迭代器身上
2、stl中deque迭代器的实现部分 在stl源码实现中下面截取了迭代器的部分有很多知识值得学习。 1、普通迭代器和const迭代器实现技巧 我们知道const对象的实现就是不能修改值因此只需要在实现迭代器时针对一下-和*的返回值即可源码库中使用两个模板参数巧妙的解决这个问题。 2、非类型模板参数 在模板进阶中我们会讲到非类型模板参数的使用使用size_t作为参数相当于一个宏的使用。 template class T, class Ref, class Ptr, size_t BufSiz 3、重载的复用 先实现重载符号 接着的 、-、-都采用了复用的方式使得代码更简洁。 在实现、–时先实现前置前置–再实现后置后置–这里也可以复用 #pragma once
template class T, class Ref, class Ptr, size_t BufSiz
struct __deque_iterator {typedef __deque_iteratorT, T, T*, BufSiz iterator;typedef __deque_iteratorT, const T, const T*, BufSiz const_iterator;typedef T value_type;typedef Ptr pointer;typedef Ref reference;typedef T** map_pointer;typedef ptrdiff_t difference_type;typedef __deque_iterator self;//构造函数//有参构造__deque_iterator(T* x, map_pointer y): cur(x), first(*y), last(*y buffer_size()), node(y) {}//默认构造__deque_iterator() : cur(0), first(0), last(0), node(0) {}//拷贝构造__deque_iterator(const iterator x): cur(x.cur), first(x.first), last(x.last), node(x.node) {}//更新结点信息void set_node(map_pointer new_node) {node new_node;first *new_node;last first difference_type(buffer_size());}//运算符重载reference operator*() const { return *cur; }pointer operator-() const { return (operator*()); }self operator() {cur;if (cur last) {set_node(node 1);cur first;}return *this;}self operator(int) {self tmp *this;*this;return tmp;}self operator--() {if (cur first) {set_node(node - 1);cur last;}--cur;return *this;}self operator--(int) {self tmp *this;--*this;return tmp;}self operator(difference_type n) {difference_type offset n (cur - first);if (offset 0 offset difference_type(buffer_size()))cur n;else {difference_type node_offset offset 0 ? offset / difference_type(buffer_size()): -difference_type((-offset - 1) / buffer_size()) - 1;set_node(node node_offset);cur first (offset - node_offset * difference_type(buffer_size()));}return *this;}self operator(difference_type n) const {self tmp *this;return tmp n;}self operator-(difference_type n) { return *this -n; }self operator-(difference_type n) const {self tmp *this;return tmp - n;}reference operator[](difference_type n) const { return *(*this n); }bool operator(const self x) const { return cur x.cur; }bool operator!(const self x) const { return !(*this x); }bool operator(const self x) const {return (node x.node) ? (cur x.cur) : (node x.node);}//成员变量
private:T* cur;T* first;T* last;map_pointer node;
};二stack的模拟实现 通过stack的实现可以看出stack的实现是基于deque。栈的实现就是将双端队列进行包装这个过程就像是deque是交流电而stack就是这个插头为用户提供需要的接口。 #pragma once
#includevector
#includelist
#includedeque
using namespace std;namespace wgm {templateclass T, class Container dequeTclass stack {public:void push(const T val) {_con.push_back(val);}void pop() {_con.pop_back();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}const T top() const{return _con.back();}private:Container _con;};
}三queue的模拟实现 和stack类似在它的参数列表中也有一个参数类型Container(容器它也存在默认参数deque。这里的参数不能传入vector,因为vector不支持头部出元素的pop_front操作。 #pragma once
#includevector
#includelist
#includedeque
using namespace std;namespace wgm {templateclass T, class Container dequeTclass queue {public:void push(const T val) {_con.push_back(val);}void pop() {_con.pop_front();}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}const T front() const{return _con.front();}const T back() const{return _con.back();}private:Container _con;};
}三、优先队列
一优先队列的概念
优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大小的。实际上这就和之前学过的数据结构堆的性质一样。
二优先队列的接口说明
empty() 检测容器是否为空 size() 返回容器中有效元素个数 front() 返回容器中第一个元素的引用 push_back() 在容器尾部插入元素 pop_back() 删除容器尾部元素
三优先队列的模拟实现
#pragma once
#includevector
#includeiostream
using namespace std;namespace wgm {template class Tstruct less{bool operator() (const T x, const T y) const{return x y;}};template class Tstruct greater{bool operator() (const T x, const T y) const{return x y;}};templateclass T , class Container vectorT, class Compare lessTclass priority_queue {public:
#define FATHER(i) (((i) - 1) / 2)
#define LEFT(i) (((i) * 2) 1)
#define RIGHT(i) (((i) * 2) 2)void AdjustUp(int i){Compare cmp;while (FATHER(i) 0 Compare()(_con[FATHER(i)], _con[i])) {swap(_con[i], _con[FATHER(i)]);i FATHER(i);}}void AdjustDown(int i){while (LEFT(i) _con.size()) {int l LEFT(i), r RIGHT(i), ind i;Compare cmp;if (cmp(_con[ind], _con[LEFT(i)])) ind LEFT(i);if (RIGHT(i) _con.size() cmp(_con[ind], _con[RIGHT(i)])) ind RIGHT(i);if (ind i) break;swap(_con[i], _con[ind]);i ind;}}void push(const T val){_con.push_back(val);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);}bool empty(){return _con.empty();}const T top(){return _con[0];}size_t size(){return _con.size();}private:Container _con;};
}四、结束语
这个部分相对于之前学的容器要简单只不过这个双端队列的实现源码还是挺有意思的可以尝时着实现实现。
