65,171
社区成员
发帖
与我相关
我的任务
分享
- 全部
- 博文收录
- Ada助手
- 问答
stack vector queue 在stl实现 简要说明
我知道 stl源码分析 详细说明了三者的实现。
但是最近复习，希望找到要点。//后来空暇来，当然读侯捷老师的书。
能不能用简要的2-3句话对 每种类型说明实现。
但是最近复习，希望找到要点。//后来空暇来，当然读侯捷老师的书。
能不能用简要的2-3句话对 每种类型说明实现。
...全文
给本帖投票
请发表友善的回复…
发表回复
titer1 2012-09-20
- 打赏
- 举报
今天就给个 小结吧。
要理解 ，都已 dqueue为原型扩展。
对于map,set都是以红黑树为基础。。呵呵。。
要理解 ，都已 dqueue为原型扩展。
对于map,set都是以红黑树为基础。。呵呵。。
titer1 2012-09-19
- 打赏
- 举报
大家有补充，请继续哈
titer1 2012-09-19
- 打赏
- 举报
看来还是自己动动手。
我想说说自己寻找的结果吧。
文章先对STL中的stack,queue,priority_queue的异同点进行解析，接着分别解析了stack,queue,priority_queue的源码结构实现方式。
stack,queue,priority_queue的相同点
之所以把stack,queue,priority_queue三者放在一起，是因为这三种容器再STL中均属于特殊容器。他们都具有如下特征：
它们均是为满足特定需求而建立的容器。stack是为了满足FILO，queue是为了满足FIFO，priority_queue则是为了满足优先级高的元素先出队列。
它们均具有一组含义非常明确的函数接口，比如stack的top,pop, push分别表示获取栈顶元素，出栈和入栈，queue的front,back, pop, push分别表示获取队列首元素，队列尾元素,出队列和入队列。
它们均不是标准的STL容器，却都是以标准STL容器为基础。stack和queue默认是在deque的基础上封装的，priority_queue默认是在vector的基础上封装出来的。stack和queue的基础容器之所以选择deque而不选择vector等容器，是因为deque在删除元素的时候可以释放空间，同时在重新申请空间的时候无需拷贝所有元素。
它们均对基础容器有一定的要求，这个要求是由他们满足的需求确定的。比如stack需要从栈顶进出元素和获取栈顶元素，它的基础容器则需要提供back(), push_back(), pop_back()的函数。同理queue的基础容器需要能够提供back(), push_back(), pop_front(), priority_queue的基础容器需要提供back(), push_back(), pop_back()的函数。
你可以你的需要，通过参数传递修改它们的基础容器。比如
?
stack<int, vector<int=""> > st</int,>
对于stack和queue还有一个共同点，他们均有重载比较运算符，也就是说你可以对二个stack或者二个queue进行字典许的比较和排序。
源：http://www.zhongsisi.com/stl-source-structure-of-stack-queue-priority_queue/
我想说说自己寻找的结果吧。
文章先对STL中的stack,queue,priority_queue的异同点进行解析，接着分别解析了stack,queue,priority_queue的源码结构实现方式。
stack,queue,priority_queue的相同点
之所以把stack,queue,priority_queue三者放在一起，是因为这三种容器再STL中均属于特殊容器。他们都具有如下特征：
它们均是为满足特定需求而建立的容器。stack是为了满足FILO，queue是为了满足FIFO，priority_queue则是为了满足优先级高的元素先出队列。
它们均具有一组含义非常明确的函数接口，比如stack的top,pop, push分别表示获取栈顶元素，出栈和入栈，queue的front,back, pop, push分别表示获取队列首元素，队列尾元素,出队列和入队列。
它们均不是标准的STL容器，却都是以标准STL容器为基础。stack和queue默认是在deque的基础上封装的，priority_queue默认是在vector的基础上封装出来的。stack和queue的基础容器之所以选择deque而不选择vector等容器，是因为deque在删除元素的时候可以释放空间，同时在重新申请空间的时候无需拷贝所有元素。
它们均对基础容器有一定的要求，这个要求是由他们满足的需求确定的。比如stack需要从栈顶进出元素和获取栈顶元素，它的基础容器则需要提供back(), push_back(), pop_back()的函数。同理queue的基础容器需要能够提供back(), push_back(), pop_front(), priority_queue的基础容器需要提供back(), push_back(), pop_back()的函数。
你可以你的需要，通过参数传递修改它们的基础容器。比如
?
stack<int, vector<int=""> > st</int,>
对于stack和queue还有一个共同点，他们均有重载比较运算符，也就是说你可以对二个stack或者二个queue进行字典许的比较和排序。
源：http://www.zhongsisi.com/stl-source-structure-of-stack-queue-priority_queue/
翅膀又硬了 2012-09-18
- 打赏
- 举报
只用过后两个vector是数组，内存连续。queue不连续
murataht 2012-09-18
- 打赏
- 举报
首先这个应该从数据结构角度来理解，他们的共同点，区别，分别使用的问题，等等。
然后再讨论他们的实现，但是用2，3句话概括，我觉得有点难。
然后再讨论他们的实现，但是用2，3句话概括，我觉得有点难。
SKATE11 2012-09-18
- 打赏
- 举报
你是要源代码吗还是 它们的结构 这个网上和书上都很多嘛
