从零开始学C++之STL（十一）：容器适配器（stack、 queue 、priority_queue）源码浅析与使用示例

aspnetwinform

浏览: 84333 次
性别:
来自: 武汉

最近访客更多访客>>

380071587

zc690739629

standalone

wuyue

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

一、容器适配器
stack
queue
priority_queue

stack、queue、priority_queue 都不支持任一种迭代器，它们都是容器适配器类型，stack是用vector/deque/list对象创建了一个先进后出容器；queue是用deque或list对象创建了一个先进先出容器；priority_queue是用vector/deque创建了一个排序队列，内部用二叉堆实现。

（一）、stack

首先来看示例代码：

C++ Code

#include<iostream>
#include<vector>
#include<list>
#include<stack>

usingnamespacestd;

intmain(void)
{
stack<int,list<int>>s;
for(inti=0;i<5;i++)
{
s.push(i);
}

//for(size_ti=0;i<s.size();i++)
//{
//cout<<s.top()<<'';Error:size()一直在变化
//s.pop();
//}

while(!s.empty())
{
cout<<s.top()<<'';
s.pop();
}
cout<<endl;
return0;
}

再看stack 的源码：

C++ Code

//TEMPLATECLASSstack
template<class_Ty,
class_Container=deque<_Ty>>
classstack
{
//LIFOqueueimplementedwithacontainer
public:
typedef_Containercontainer_type;
typedeftypename_Container::value_typevalue_type;
typedeftypename_Container::size_typesize_type;
typedeftypename_Container::referencereference;
typedeftypename_Container::const_referenceconst_reference;

stack()
:c()
{
//constructwithemptycontainer
}

explicitstack(const_Container&_Cont)
:c(_Cont)
{
//constructbycopyingspecifiedcontainer
}

boolempty()const
{
//testifstackisempty
return(c.empty());
}

size_typesize()const
{
//testlengthofstack
return(c.size());
}

referencetop()
{
//returnlastelementofmutablestack
return(c.back());
}

const_referencetop()const
{
//returnlastelementofnonmutablestack
return(c.back());
}

voidpush(constvalue_type&_Val)
{
//insertelementatend
c.push_back(_Val);
}

voidpop()
{
//eraselastelement
c.pop_back();
}

const_Container&_Get_container()const
{
//getreferencetocontainer
return(c);
}

protected:
_Containerc;//theunderlyingcontainer
};

即有一个_Container 成员，默认是deque<_Ty> ，当然也可以传递vector, list 进去，只要支持push_back，pop_back 等接口。内部的函数实现

都借助了容器的函数，跟以前实现过的Stack 很像。

（二）、queue

先来看示例代码：

C++ Code

#include<iostream>
#include<vector>
#include<list>
#include<stack>
#include<queue>

usingnamespacestd;

intmain(void)
{
//inta[]={1,2,3,4,5};
//vector<int>v(a,a+5);

queue<int,list<int>>q;
for(inti=0;i<5;i++)
{
q.push(i);
}

while(!q.empty())
{
cout<<q.front()<<'';
q.pop();
}

cout<<endl;

return0;
}

再来看queue 源码：

C++ Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

//TEMPLATECLASSqueue
template<class_Ty,
class_Container=deque<_Ty>>
classqueue
{
//FIFOqueueimplementedwithacontainer
public:
typedef_Containercontainer_type;
typedeftypename_Container::value_typevalue_type;
typedeftypename_Container::size_typesize_type;
typedeftypename_Container::referencereference;
typedeftypename_Container::const_referenceconst_reference;

queue()
:c()
{
//constructwithemptycontainer
}

explicitqueue(const_Container&_Cont)
:c(_Cont)
{
//constructbycopyingspecifiedcontainer
}

boolempty()const
{
//testifqueueisempty
return(c.empty());
}

size_typesize()const
{
//returnlengthofqueue
return(c.size());
}

referencefront()
{
//returnfirstelementofmutablequeue
return(c.front());
}

const_referencefront()const
{
//returnfirstelementofnonmutablequeue
return(c.front());
}

referenceback()
{
//returnlastelementofmutablequeue
return(c.back());
}

const_referenceback()const
{
//returnlastelementofnonmutablequeue
return(c.back());
}

voidpush(constvalue_type&_Val)
{
//insertelementatbeginning
c.push_back(_Val);
}

voidpop()
{
//eraseelementatend
c.pop_front();
}

const_Container&_Get_container()const
{
//getreferencetocontainer
return(c);
}

protected:
_Containerc;//theunderlyingcontainer
};

实现跟stack 是很类似的，只是queue不能用vector 实现，因为没有pop_front 接口。

（三）、priority_queue

先来看示例代码：

C++ Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include<iostream>
#include<functional>
#include<vector>
#include<list>
#include<stack>
#include<queue>

usingnamespacestd;

intmain(void)
{
inta[]={5,1,2,4,3};
priority_queue<int,vector<int>,greater<int>>q(a,a+5);

while(!q.empty())
{
cout<<q.top()<<'';
q.pop();
}

cout<<endl;

return0;
}

再来看priority_queue 的源码：

C++ Code

//TEMPLATECLASSpriority_queue
template<class_Ty,
class_Container=vector<_Ty>,
class_Pr=less<typename_Container::value_type>>
classpriority_queue
{
//priorityqueueimplementedwitha_Container
public:
typedef_Containercontainer_type;
typedeftypename_Container::value_typevalue_type;
typedeftypename_Container::size_typesize_type;
typedeftypename_Container::referencereference;
typedeftypename_Container::const_referenceconst_reference;

priority_queue()
:c(),comp()
{
//constructwithemptycontainer,defaultcomparator
}

explicitpriority_queue(const_Pr&_Pred)
:c(),comp(_Pred)
{
//constructwithemptycontainer,specifiedcomparator
}

priority_queue(const_Pr&_Pred,const_Container&_Cont)
:c(_Cont),comp(_Pred)
{
//constructbycopyingspecifiedcontainer,comparator
make_heap(c.begin(),c.end(),comp);
}

template<class_Iter>
priority_queue(_Iter_First,_Iter_Last)
:c(_First,_Last),comp()
{
//constructbycopying[_First,_Last),defaultcomparator
make_heap(c.begin(),c.end(),comp);
}

template<class_Iter>
priority_queue(_Iter_First,_Iter_Last,const_Pr&_Pred)
:c(_First,_Last),comp(_Pred)
{
//constructbycopying[_First,_Last),specifiedcomparator
make_heap(c.begin(),c.end(),comp);
}

template<class_Iter>
priority_queue(_Iter_First,_Iter_Last,const_Pr&_Pred,
const_Container&_Cont)
:c(_Cont),comp(_Pred)
{
//constructbycopying[_First,_Last),container,andcomparator
c.insert(c.end(),_First,_Last);
make_heap(c.begin(),c.end(),comp);
}

boolempty()const
{
//testifqueueisempty
return(c.empty());
}

size_typesize()const
{
//returnlengthofqueue
return(c.size());
}

const_referencetop()const
{
//returnhighest-priorityelement
return(c.front());
}

referencetop()
{
//returnmutablehighest-priorityelement(retained)
return(c.front());
}

voidpush(constvalue_type&_Pred)
{
//insertvalueinpriorityorder
c.push_back(_Pred);
push_heap(c.begin(),c.end(),comp);
}

voidpop()
{
//erasehighest-priorityelement
pop_heap(c.begin(),c.end(),comp);
c.pop_back();
}

protected:
_Containerc;//theunderlyingcontainer
_Prcomp;//thecomparatorfunctor
};

priority_queue 的实现稍微复杂一点，可以传递3个参数，而且有两个成员，comp 即自定义比较逻辑，默认是less<value_type>，在构造函数中

调用make_heap函数构造二叉堆，comp 主要是用于构造二叉堆时的判别，如果是less 则构造大堆，如果传递greater 则构造小堆.

注意，priority_queue 不能用list 实现，因为list 只支持双向迭代器，而不支持随机迭代器。

下面举个例子说明make_heap 函数的用法：

C++ Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include<iostream>
#include<functional>
#include<vector>
#include<list>
#include<stack>
#include<queue>

usingnamespacestd;

intmain(void)
{
inta[]={5,1,2,4,3};
make_heap(a,a+5,less<int>());

copy(a,a+5,ostream_iterator<int>(cout,""));
cout<<endl;

sort(a,a+5);
//sort_heap(a,a+5,less<int>());
copy(a,a+5,ostream_iterator<int>(cout,""));
cout<<endl;

return0;
}

输出：

5 4 2 1 3

1 2 3 4 5

make_heap() 将容器的元素构造成二叉堆，传递的是less，即构造的是大堆，把大堆层序遍历的结果存入数组，再调用sort() 进行排序，内部调用

的实际算法不一定，可以是堆排序、插入排序、选择排序等等，跟踪进去发现调用的是插入排序；当然也可以直接指定使用堆排序 sort_heap（调用

者必须已经是堆了，也就是前面已经先调用了make_heap，而且大小堆类型得匹配），与make_heap 一样，第三个参数传递的都是函数对象的用

法。sort 和 sort_heap 默认都是从小到大排序，除非重载的版本传递了第三个参数，如下，第三个参数可以是函数指针，也可以是函数对象：

C++ Code

1 2 3 4 5 6 7 8

//orderheapbyrepeatedlypopping,usingoperator<
template<class_RanIt>inline
voidsort_heap(_RanIt_First,_RanIt_Last);

//orderheapbyrepeatedlypopping,using_Pred
template<class_RanIt,
class_Pr>inline
voidsort_heap(_RanIt_First,_RanIt_Last,_Pr_Pred);

传递greater 构造的是小堆，如下图所示：