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

一、容器适配器 stack queue priority_queue

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

前面或多或少谈到过list/vector的实现,而没提到过deque的实现,可以用以下一句话概括,具体可以看看《stl源码剖析》:

Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.

(一)、stack

首先来看示例代码:

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

using namespace std;

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

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

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

再看stack 的源码:

// TEMPLATE CLASS stack
template < class _Ty,
         class _Container = deque<_Ty> >
class stack
{
    // LIFO queue implemented with a container
public:
    typedef _Container container_type;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;

    stack()
        : c()
    {
        // construct with empty container
    }

    explicit stack(const _Container &_Cont)
        : c(_Cont)
    {
        // construct by copying specified container
    }

    bool empty() const
    {
        // test if stack is empty
        return (c.empty());
    }

    size_type size() const
    {
        // test length of stack
        return (c.size());
    }

    reference top()
    {
        // return last element of mutable stack
        return (c.back());
    }

    const_reference top() const
    {
        // return last element of nonmutable stack
        return (c.back());
    }

    void push(const value_type &_Val)
    {
        // insert element at end
        c.push_back(_Val);
    }

    void pop()
    {
        // erase last element
        c.pop_back();
    }

    const _Container &_Get_container() const
    {
        // get reference to container
        return (c);
    }

protected:
    _Container c;   // the underlying container
};

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

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

(二)、queue

先来看示例代码:

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

using namespace std;

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

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

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

    cout << endl;

    return 0;
}

再来看queue 源码:

// TEMPLATE CLASS queue
template < class _Ty,
         class _Container = deque<_Ty> >
class queue
{
    // FIFO queue implemented with a container
public:
    typedef _Container container_type;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;

    queue()
        : c()
    {
        // construct with empty container
    }

    explicit queue(const _Container &_Cont)
        : c(_Cont)
    {
        // construct by copying specified container
    }

    bool empty() const
    {
        // test if queue is empty
        return (c.empty());
    }

    size_type size() const
    {
        // return length of queue
        return (c.size());
    }

    reference front()
    {
        // return first element of mutable queue
        return (c.front());
    }

    const_reference front() const
    {
        // return first element of nonmutable queue
        return (c.front());
    }

    reference back()
    {
        // return last element of mutable queue
        return (c.back());
    }

    const_reference back() const
    {
        // return last element of nonmutable queue
        return (c.back());
    }

    void push(const value_type &_Val)
    {
        // insert element at beginning
        c.push_back(_Val);
    }

    void pop()
    {
        // erase element at end
        c.pop_front();
    }

    const _Container &_Get_container() const
    {
        // get reference to container
        return (c);
    }

protected:
    _Container c;   // the underlying container
};

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

(三)、priority_queue

先来看示例代码:

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

using namespace std;

int main(void)
{
    int a[] = {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;

    return 0;
}

再来看priority_queue 的源码:

// TEMPLATE CLASS priority_queue
template < class _Ty,
         class _Container = vector<_Ty>,
         class _Pr = less<typename _Container::value_type> >
class priority_queue
{
    // priority queue implemented with a _Container
public:
    typedef _Container container_type;
    typedef typename _Container::value_type value_type;
    typedef typename _Container::size_type size_type;
    typedef typename _Container::reference reference;
    typedef typename _Container::const_reference const_reference;

    priority_queue()
        : c(), comp()
    {
        // construct with empty container, default comparator
    }

    explicit priority_queue(const _Pr &_Pred)
        : c(), comp(_Pred)
    {
        // construct with empty container, specified comparator
    }

    priority_queue(const _Pr &_Pred, const _Container &_Cont)
        : c(_Cont), comp(_Pred)
    {
        // construct by copying specified container, comparator
        make_heap(c.begin(), c.end(), comp);
    }

    template<class _Iter>
    priority_queue(_Iter _First, _Iter _Last)
        : c(_First, _Last), comp()
    {
        // construct by copying [_First, _Last), default comparator
        make_heap(c.begin(), c.end(), comp);
    }

    template<class _Iter>
    priority_queue(_Iter _First, _Iter _Last, const _Pr &_Pred)
        : c(_First, _Last), comp(_Pred)
    {
        // construct by copying [_First, _Last), specified comparator
        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)
    {
        // construct by copying [_First, _Last), container, and comparator
        c.insert(c.end(), _First, _Last);
        make_heap(c.begin(), c.end(), comp);
    }

    bool empty() const
    {
        // test if queue is empty
        return (c.empty());
    }

    size_type size() const
    {
        // return length of queue
        return (c.size());
    }

    const_reference top() const
    {
        // return highest-priority element
        return (c.front());
    }

    reference top()
    {
        // return mutable highest-priority element (retained)
        return (c.front());
    }

    void push(const value_type &_Pred)
    {
        // insert value in priority order
        c.push_back(_Pred);
        push_heap(c.begin(), c.end(), comp);
    }

    void pop()
    {
        // erase highest-priority element
        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }

protected:
    _Container c;   // the underlying container
    _Pr comp;   // the comparator functor
};

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

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

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

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

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

using namespace std;

int main(void)
{
    int a[] = {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;

    return 0;
}

输出:

5 4 2 1 3

1 2 3 4 5

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

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

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

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

// order heap by repeatedly popping, using operator<
template<class _RanIt> inline
void sort_heap(_RanIt _First, _RanIt _Last);

// order heap by repeatedly popping, using _Pred
template < class _RanIt,
         class _Pr > inline
void sort_heap(_RanIt _First, _RanIt _Last, _Pr _Pred);

传递greater 构造的是小堆,如下图所示:

参考:

C++ primer 第四版 Effective C++ 3rd C++编程规范

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏天天P图攻城狮

RecyclerView 必知必会

回顾整篇文章,发现我们已经实现了RecyclerView的很多扩展功能,包括:打造万能适配器、添加Item事件、添加头视图和尾视图、设置空布局、侧滑拖拽。

1.1K8
来自专栏DOTNET

ASP.NET MVC编程——单元测试

1自动化测试基本概念 自动化测试分为:单元测试,集成测试,验收测试。 单元测试 检验被测单元的功能,被测单元一般为低级别的组件,如一个类或类方法。 单元测试要满...

4095
来自专栏hightopo

基于 HTML5 Canvas 的 3D 模型贴图问题

732
来自专栏Google Dart

Flutter 构建完整应用手册-列表 顶

显示数据列表是移动应用程序的基本模式。 Flutter包含ListView部件,使列表变得轻而易举!

1182
来自专栏腾讯Bugly的专栏

RecyclerView 必知必会

导语 RecyclerView是Android 5.0提出的新UI控件,可以用来代替传统的ListView。 Bugly之前也发过一篇相关文章,讲解了 Recy...

3737
来自专栏HT

基于 HTML5 Canvas 的 3D 模型列表贴图

少量图片对于我们赋值是没有什么难度,但是如果图片的量大的话,我们肯定希望能很直接地显示在界面上供我们使用,再就是排放的位置等等,这些都需要比较直观的操作,在实际...

22510
来自专栏Jimoer

Java设计模式学习记录-外观模式

这次要介绍的是外观模式(也称为门面模式),外观模式也属于结构型模式,其实外观模式还是非常好理解的,简单的来讲就是将多个复杂的业务封装成一个方法,在调用此方法时可...

541
来自专栏WindCoder

Struts2表单验证xml后台提示“严重: Validation error for….”

按实验楼中的代码敲得,对了好几遍都是一样的,但一直无法达到在前台提示错误信息的效果,仅能在后台的控制台找到如下类似的信息:

381
来自专栏何俊林

一种视频录制时,类似监控视频中加入动态时间标记的装置

我们经常在使用视频录制时,动态添加像监控画面一样的精确到秒的时间信息,需要记录当前时间到视频中去,这样的需求很常见。今天使用Java代码来实现,通常来说这种用C...

5735
来自专栏阿北的知识分享

Yii2的GridView使用大全 --- 18个问答

GridView主要是为了实现表格复用,尤其我们做后台的时候,你发现表单和表格占据了大部分页面,而表格的样式又是高度的统一,那么如果有这样一个挂件,传入数据集自...

2728

扫码关注云+社区