网站建设在线商城,设置个网站要多少钱,沈阳seo排名优化软件,做网站培训班南京目录
1. stack的介绍和使用
1.1 stack的介绍 1.2 stack的使用
2 栈的模拟实现
3 queue的介绍和使用
3.1 queue的介绍 3.2 queue的使用
4 queue的模拟实现
5 deque的介绍
5.1deque的原理介绍
5.2 deque的缺陷
5.3 为什么选择deque作为stack和queue的底层默认容器
6 p…目录
1. stack的介绍和使用
1.1 stack的介绍 1.2 stack的使用
2 栈的模拟实现
3 queue的介绍和使用
3.1 queue的介绍 3.2 queue的使用
4 queue的模拟实现
5 deque的介绍
5.1deque的原理介绍
5.2 deque的缺陷
5.3 为什么选择deque作为stack和queue的底层默认容器
6 priority_queue的介绍和使用
6.1 priority_queue的介绍
6.2 priority_queue的使用
7 priority_queue的模拟实现 1. stack的介绍和使用
1.1 stack的介绍
栈的文档介绍 1. stack是一种容器适配器专门用在具有后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入与提取操作。 2. stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器的尾部(即栈顶)被压入和弹出。 3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类这些容器类应该支持以下操作 empty判空操作 back获取尾部元素操作 push_back尾部插入元素操作 pop_back尾部删除元素操作 4. 标准容器vector、deque、list均符合这些需求默认情况下如果没有为stack指定特定的底层容器默认情况下使用deque。1.2 stack的使用
这些使用我们C语言时学习栈和队列就已经很熟悉了 函数说明 接口说明 stack() 构造空的栈 empty() 检测stack是否为空 size() 返回stack中元素的个数 top() 返回栈顶元素的引用 push() 将元素val压入stack中 pop() 将stack中尾部的元素弹出2 栈的模拟实现
这儿与之前list的反向迭代器一样用的时一种适配器模式并不需要自己再造一遍轮子我们打开stack官网看看官方对栈的介绍 大家或许就有了疑问这个dequeT是个什么鬼呀这个我们在下面会详细介绍至于这里为啥会用dequeT来作为缺省参数我们在下面讲解duque会给出详细解释。
接下来就给出stack的模拟实现
namespace grm
{templateclass T,class ContainerdequeTclass stack{private:Container _con;public:bool empty(){return _con.empty();}const T top(){return _con.back();}void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}size_t size(){return _con.size();}};
}
用了适配器的原理写栈会轻松很多。 3 queue的介绍和使用
3.1 queue的介绍
队列的文档介绍 1. 队列是一种容器适配器专门用于在FIFO上下文(先进先出)中操作其中从容器一端插入元素另一端提取元素。 2. 队列作为容器适配器实现容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从队尾入队列从队头出队列。 3. 底层容器可以是标准容器类模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty检测队列是否为空 size返回队列中有效元素的个数 front返回队头元素的引用 back返回队尾元素的引用 push_back在队列尾部入队列 pop_front在队列头部出队列 4. 标准容器类deque和list满足了这些要求。默认情况下如果没有为queue实例化指定容器类则使用标准容器deque。 3.2 queue的使用 函数声明 接口说明 queue() 构造空的队列 empty() 检测队列是否为空是返回true否则返回false size() 返回队列中有效元素的个数 front() 返回队头元素的引用 back() 返回队尾元素的引用 push() 在队尾将元素val入队列 pop() 将队头元素出队列 4 queue的模拟实现
namespace grm
{templateclass T, class Container dequeTclass queue{private:Container _con;public:bool empty(){return _con.empty();}const T front(){return _con.front();}const T back(){return _con.back();}void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}};
} 5 deque的介绍
5.1deque的原理介绍 deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较cpu高速缓存命中高不会频繁申请释放空间。 起初deque设计出来是想要融合vector和list的优点想要代替他们但是结果却差强人意。尽管deque与vector比较头插效率高与list比较cpu高速缓存命中高。但是却比不了vector的O(1)的任意位置随机访问list的任意位置O(1)插入删除。
所以deque是代替不了vector和list的我们只需要大概了解一下原理并不需要去模拟实现一下
deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示上面的中控器用的是一个指针数组维护的用数组中的指针指向每一个bufferbuffer的具体大小是由编译器所决定的。
5.2 deque的缺陷 与vector比较deque的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此在这方面的效率是比vector高的。 与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。 但是deque有一个致命缺陷不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和listdeque的应用并不多而目前能看到的一个应用就是STL用其作为stack和queue的底层数据结构。 5.3 为什么选择deque作为stack和queue的底层默认容器 stack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器比如vector和list都可以queue是先进先出的特殊线性数据结构只要具有push_back和pop_front操作的线性结构都可以作为queue的底层容器比如list。但是STL中对stack和queue默认选择deque作为其底层容器主要是因为 1. stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。 2. 在stack中元素增长时deque比vector的效率高(扩容时不需要搬移大量数据)queue中的元素增长时deque不仅效率高而且内存使用率高。 结合了deque的优点而完美的避开了其缺陷。 6 priority_queue的介绍和使用
6.1 priority_queue的介绍
priority_queue的介绍 1. 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的默认情况。 2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素(优先队列中位于顶部的元素)。 3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先队列的顶部。 4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty()检测容器是否为空 size()返回容器中有效元素个数 front()返回容器中第一个元素的引用 push_back()在容器尾部插入元素 5. 标准容器类vector和deque满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。 6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。 6.2 priority_queue的使用 优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意 默认情况下priority_queue是大堆。 忘记了堆的老铁可以去看看博主讲解的这篇文章http://http://t.csdn.cn/Buh2Qhttp://xn--http-u76a//t.csdn.cn/Buh2Q%E2%80%8B 函数声明 接口说明 priority_queue() priority_queue(first, last) 构造一个空的优先级队列 empty( ) 检测优先级队列是否为空是返回true否则返回false top( ) 返回优先级队列中最大(最小元素)即堆顶元素 push(x) 在优先级队列中插入元素x pop( ) 删除优先级队列中最大(最小)元素即堆顶元素我们可以来试试 priority_queueint pq;//仿函数为less,默认建立大堆pq.push(10);pq.push(1);pq.push(8);pq.push(3);pq.push(15);pq.push(16);while (!pq.empty()){cout pq.top() ;pq.pop();} 至于为啥仿函数为less但是建立的确是大堆这个是大佬们硬性规定的大家也不要太过于较真。
要实现建立小堆我们调用一下greater仿函数即可。 priority_queueint,vectorint,greaterint pq;//显示调用仿函数为greater,建立小堆pq.push(10);pq.push(1);pq.push(8);pq.push(3);pq.push(15);pq.push(16);while (!pq.empty()){cout pq.top() ;pq.pop();}
运行结果 假如我们想比较自定义类型的大小应该咋办直接用STL自带的仿函数好像并不能够完成所以我们还得自己再实现一下仿函数。
先把日期类给整出来
class Date
{friend ostream operator(ostream out, const Date d);//友元声明
private:int _year;int _month;int _day;public:Date(int year 1, int month 1, int day 1):_year(year), _month(month), _day(day){}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}bool operator(const Date d)const{return (_year d._year) ||(_year d._year _month d._month) ||(_year d._year _month d._month _day d._day);}
};ostream operator(ostream out, const Date d)
{out d._year / d._month / d._day endl;return out;
}
大家这时心里可能会想重载还好理解因为要输出结果嘛为啥你要重载和运算符呀
不知道大家忘记了没当我们建堆时有两种调整方式向上调整和向下调整时都会设计数据的比较内置类型没事自定义类型就得我们重载比较运算符了所以我们要想实现自定义类型的比较这个是必不可少的。
然后我们就可以实现日期类的比较了 priority_queueDate, vectorDate pq;pq.push(Date(2023, 2, 7));pq.push(Date(2021, 2, 9));pq.push(Date(2023, 2, 8));pq.push(Date(2024, 2, 6));while(!pq.empty()){cout pq.top() ;pq.pop();}运行结果 但是假如我们push的是日期类的地址用系统自带的仿函数能够完成吗
大家想想由于push的是地址所以比较的是地址的大小而不是地址指向的内容的大小所以这种方法肯定是不合理的。
我们可以来试试 很明显结果是不对的尽管有时候碰巧结果恰好对的也只是运气而已。
即我们还得自己写仿函数
仿函数 struct p_date_less{bool operator()(Date* pd1, Date* pd2){return *pd1 *pd2;}};struct p_date_greater{bool operator()(Date* pd1, Date* pd2){return *pd1 *pd2;}};
这样就能够正确比较了 7 priority_queue的模拟实现 templateclass T, class Container vectorT, class Compare lessTclass priority_queue{private:Container _con;void adjust_up(size_t child)//假设这里要建立大堆默认仿函数是less{size_t parent child - 1 1;while (child 0){//if (_con[child] _con[parent])Compare cmp;//实例化出一个Cmpare的对象if (cmp(_con[parent],_con[child]))//由于仿函数中实现的是xy{swap(_con[child], _con[parent]);child parent;parent child - 1 1;}elsebreak;}}void adjust_down(size_t parent){size_t child parent * 2 1;while (child _con.size()){Compare cmp;//实例化出一个Cmpare的对象if (child 1 _con.size() cmp(_con[child],_con[child1]))//假如建立大堆默认仿函数为less,就得满足_con[child]_con[child1]child 1;//if (_con[child] _con[parent])if (cmp(_con[parent],_con[child]))//由于仿函数中实现的是xy{swap(_con[child], _con[parent]);parent child;child parent * 2 1;}elsebreak;}}public:priority_queue(){}templateclass InputIteratorpriority_queue(InputIterator first, InputIterator last):_con(){for (int i _con.size() - 2 1; i 0; i--)//向下建堆时间复杂度为O(N)adjust_down(i);}void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[size() - 1]);_con.pop_back();adjust_down(0);}const T top(){return _con.front();}bool empty(){return _con.empty();}size_t size(){return _con.size();}};
这个之前在堆那一部分做了较为详细的讲解这里就不在多说了。
