AI 助理
文档备案控制台
开发者社区 开发与运维 文章 正文

【C++要笑着学】Functor 仿函数 | 模拟实现 stack & queue | 模拟实现优先级队列（二）

2022-12-19 251
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
在线体验各类最新模型，更有模型 免费Token 额度领取！
立即体验
简介： 在上一章中，我们讲解了STL的栈和队列，本章我们来模拟实现一下它们。在讲解优先级队列的同时我们顺便把上一章提到的仿函数进行一个讲解，使用仿函数可以有效替换使用难以理解的函数指针的场景。我们通过仿函数 less 和 greater 去控制优先级队列的 Compare，从而能同时适配升序和降序。

Ⅲ. 模拟实现 priority_queue

0x00 基本实现思路

据我所知，在优先级队列中，插入数据和删除数据的时间复杂度为  。


默认情况下的优先级队列是大堆，我们先不考虑用仿函数去实现兼容大堆小队排列问题，


我们先去实现大堆，先把基本的功能实现好，带着讲解完仿函数后再去进行优化实现。


优先级队列相较于普通的队列，其区别主要是在 push 和 pop 上，


即需要在插入 / 删除数据的同时，增添调整的功能，并且 STL 的优先级队列是由堆来维护的：

void push(const T& x) {
    _con.push_back(x);
    AdjustUp(_con.size() - 1);
}

入队时将数据推入后，从最后一个元素开始进行上调。


出队时采用堆的删除手法，将根元素（即队头）和最后一个元素进行交换，并调用尾删掉队头。


既然用了头尾交换法，我们就不得不对队列重新调整，所以从根位置进行下调，即可完成出队。

void pop() {
    assert(!_con.empty());
    swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back();
    AdjustDown(0);
}

既然需要上调和下调操作，我们不可避免地需要实现上调和下调的算法。


我们这里暂时写死，设计成大堆的 AdjustUp 和 AdjustDown：

/* 向上调整算法 */
void AdjustUp(size_t child) {
    size_t father = (child - 1) / 2;
    while (child > 0) {
        if (_con[father] < _con[child]) {
            swap(_con[father], _con[child]);
            child = father;
            father = (child - 1) / 2;
        }
        else {
            break;
        }
    }
}
/* 向下调整算法 */
void AdjustDown(size_t father) {
    size_t child = father * 2 + 1; // 默认认为左孩子大
    while (child < _con.size()) {
        // 判断右孩子是否存在，并且是否比左孩子大？
        if (child + 1 < _con.size() && _con[child] < _con[child + 1]) {
            child += 1;
        }
        if (_con[father] < _con[child]) {
            swap(_con[father], _con[child]);
            father = child;
            child = father * 2 + 1;
        }
        else {
            break;
        }
    }
}


这里我就不重复讲解了，如果你对这一块知识比较生疏，建议复习一下数据结构的堆。


向上调整算法和向下调整算法实现完后，我们把剩下的可以直接用 _con 转换的接口实现一下：

const T& top() {
    return _con[0];
}
size_t size() {
    return _con.size();
}
bool empty() {
    return _con.empty();
}

很简单，不过值得注意的是，返回堆顶数据的 top 接口，我们用了 const 引用返回。

b0c15dfa38a7096121b53f3b0093fc01_2f1178a8b7b84f0788353b85aee10062.png


❓ 思考：为什么这里要用引用？为什么还要加个 const？


① 考虑到如果这里 T 是 string，甚至是更大的对象，传值返回就有一次拷贝构造，代价就大了。


② 如果能让你随随便便修改我堆顶的数据，那岂不是  显得我很随便？   很危险？


0x01 写死了的大堆优先级队列

💬 代码：写死了的大堆优先级队列 demo

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
namespace foxny {
    template<class T, class Container = vector<T>>
    class priority_queue {
    public:
        /* 向上调整算法 */
        void AdjustUp(size_t child) {
            size_t father = (child - 1) / 2;
            while (child > 0) {
                if (_con[father] < _con[child]) {
                    swap(_con[father], _con[child]);
                    child = father;
                    father = (child - 1) / 2;
                }
                else {
                    break;
                }
            }
        }
        /* 向下调整算法 */
        void AdjustDown(size_t father) {
            size_t child = father * 2 + 1; // 默认认为左孩子大
            while (child < _con.size()) {
                // 判断右孩子是否存在，并且是否比左孩子大？
                if (child + 1 < _con.size() && _con[child] < _con[child + 1]) {
                    child += 1;
                }
                if (_con[father] < _con[child]) {
                    swap(_con[father], _con[child]);
                    father = child;
                    child = father * 2 + 1;
                }
                else {
                    break;
                }
            }
        }
        /* 入数据 */
        void push(const T& x) {
            _con.push_back(x);
            AdjustUp(_con.size() - 1);
        }
        /* 出数据 */
        void pop() {
            assert(!_con.empty());
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            AdjustDown(0);
        }
        /* 返回堆顶数据 */
        const T& top() {
            return _con[0];
        }
        /* 返回大小 */
        size_t size() {
            return _con.size();
        }
        /* 判断是否为空 */
        bool empty() {
            return _con.empty();
        }
    private:
        Container _con;
    };
}

💬 测试：目前我们是写死了的大堆，还没有加入仿函数，我们先跑一下看看

void test_priority_queue1() {
    priority_queue<int> pQ;
    pQ.push(2);
    pQ.push(5);
    pQ.push(1);
    pQ.push(6);
    pQ.push(8);
    while (!pQ.empty()) {
        cout << pQ.top() << " ";
        pQ.pop();
    }
    cout << endl;
}

🚩 运行结果：

c3cee3cc0370f68a11afe4a64f6796c8_96a0ccccb2a243a795d4055ed849642e.png

我们写死的最大问题是 —— 如果想按升序排列，就没办法排了。


我们这里写的用来排降序的大堆，如果想排升序我们需要写小堆，


C++ 在这里有一种叫仿函数的东西，可以控制这些东西，我们下面先来介绍一下仿函数。


0x02 仿函数（functor）

📚 概念：使一个类的使用看上去像一个函数。可以像函数一样使用的对象，称为函数对象。


其实现就是在类中重载 operator()，使得该类具备类似函数的行为，就是一个仿函数类了。


C语言优先级，() 圆括号使用形式为 表达式 或 "作为函数形参列表的括号"


我们这里重载的其实就是：函数名(形参表)


💬 代码：我们来写一个最简单的仿函数

namespace foxny {
    struct less {
        // 仿函数（函数对象）———— 对象可以像调用函数一样去使用
        bool operator()(int x, int y) {
            return x < y;
        }
    };
    void test_functor() {
        less lessCmp;   // 定义一个对象（这里我用小驼峰，能看上去更像函数）
        cout << lessCmp(10, 20) << endl;   // 是对象，但是却能像函数一样去使用
    }
}

🚩 运行结果：1


这里定义对象的时候我用的我是小驼峰，这样看上去更像是一个函数了，以假乱真。


我们定义的 lessCmp 是一个对象，但是我们却可以像使用函数一样给它传递参数：

lessCmp(10, 20);

我们还可以使其能够支持泛型，我们加一个 template 模板：

// 支持泛型
template<class T> struct less {
    bool operator()(const T& x, const T& y) const {
        return x < y;
    }
};
void test_functor() {
    less<int> lessCmp;
    cout << lessCmp(10, 20) << endl;
}

less 是用来比较谁小的，对应的，我们再实现一个比较谁大的 greater：

// less: 小于的比较
template<class T> struct less {
    bool operator()(const T& x, const T& y) const {
        return x < y;
    }
};
// greater: 大于的比较
template<class T> struct greater {
    bool operator()(const T& x, const T& y) const {
        return x > y;
    }
};
void test_functor() {
    less<int> lessCmp;
    cout << lessCmp(10, 20) << endl;
    greater<int> GreaterCmp;
    cout << GreaterCmp(10, 20) << endl;
}

🚩 运行结果：1   0


一个对象能像函数一样用，看上去很神奇，实际上调用的只是我们重载的 operator() 而已。


这些操作都是归功于运算符重载功能，这就是仿函数！


❓ 思考：我们在C阶段不是学过函数指针么，用函数指针不香吗？


函数指针确实可以做到这些功能。但是在这里函数指针跟仿函数比，一点都不香。


反而很臭！啊，啊，啊♂ 啊♂ 啊♂ 啊啊啊！！！


在 C++ 里其实是非常鄙夷使用函数指针的，函数的指针在一些地方用起来非常复杂。


static void( * set_malloc_handler(void (*f)()))() {
    void (* old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = f;
    return(old);
}

这个函数的参数是什么？函数的返回值是什么？


这就很阴间了，这就是函数指针的杰作…… 所以 C++ 搞出了仿函数，简化了好多点。


📚 仿函数的优势：很多场景，替换了函数指针。


0x03 加了仿函数后的优先级队列

我们现在用仿函数去比较那些数据，这样就不会写死了。


💬 代码：priority_queue

#include <iostream>
#include <vector>
#include <functional>  // 这里放的是一些仿函数
#include <assert.h>
using namespace std;
namespace foxny {
    // less: 小于的比较
    template<class T> 
    struct less {
        bool operator()(const T& x, const T& y) const {
            return x < y;
        }
    };
    // greater: 大于的比较
    template<class T> 
    struct greater {
        bool operator()(const T& x, const T& y) const {
            return x > y;
        }
    };
    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue {
    public:
        /* 向上调整算法 */
        void AdjustUp(size_t child) {
            Compare cmpFunc;
            size_t father = (child - 1) / 2;
            while (child > 0) {
                // if (_con[father] < _con[child]) {
                if (cmpFunc(_con[father], _con[child])) {
                    swap(_con[father], _con[child]);
                    child = father;
                    father = (child - 1) / 2;
                }
                else {
                    break;
                }
            }
        }
        /* 向下调整算法 */
        void AdjustDown(size_t father) {
            Compare cmpFunc;
            size_t child = father * 2 + 1; // 默认认为左孩子大
            while (child < _con.size()) {
                // if (child + 1 < _con.size() && _con[child] < _con[child + 1]) {
                if (child + 1 < _con.size() && cmpFunc(_con[child], _con[child + 1])) {
                    child += 1;
                }
                // if (_con[father] < _con[child]) {
                if (cmpFunc(_con[father], _con[child])) {
                    swap(_con[father], _con[child]);
                    father = child;
                    child = father * 2 + 1;
                }
                else {
                    break;
                }
            }
        }
        /* 入数据 */
        void push(const T& x) {
            _con.push_back(x);
            AdjustUp(_con.size() - 1);
        }
        /* 出数据 */
        void pop() {
            assert(!_con.empty());
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            AdjustDown(0);
        }
        /* 返回堆顶数据 */
        const T& top() {
            return _con[0];
        }
        /* 返回大小 */
        size_t size() {
            return _con.size();
        }
        /* 判断是否为空 */
        bool empty() {
            return _con.empty();
        }
    private:
        Container _con;
    };
}

💭 测试：我们来测试一下效果如何：

// 大于比较，搞小堆
void test_priority_queue2() {
    priority_queue<int, vector<int>, greater<int>> pQ;
    pQ.push(2);
    pQ.push(5);
    pQ.push(1);
    pQ.push(6);
    pQ.push(8);
    while (!pQ.empty()) {
        cout << pQ.top() << " ";
        pQ.pop();
    }
    cout << endl;
}

🚩 运行结果：1 2 4 6 8

// 小于比较，搞大堆
void test_priority_queue1() {
    priority_queue<int> pQ;
    pQ.push(2);
    pQ.push(5);
    pQ.push(1);
    pQ.push(6);
    pQ.push(8);
    while (!pQ.empty()) {
        cout << pQ.top() << " ";
        pQ.pop();
    }
    cout << endl;
}

🚩 运行结果：8 6 5 2 1


这里的仿函数在编译器视角是这样的：

if (cmpFunc(_con[father], _con[child]))
                 👇
if (cmpFunc.operator()(_con[father], _con[child]))
                 👇
    // 以 less 为例
    template<class T> 
    struct less {
        bool operator()(const T& x, const T& y) const {
            return x < y;
        }
    };

最后返回 _con[father] < _con[child] ，true 还是 false

0x04 迭代器的实现

// 创造空的优先级队列
priority_queue()
    : _con()
{}
// 迭代器
template<class InputIterator>
priority_queue (InputIterator first, InputIterator last) 
    : _con(first, last)
{
    while (first != last) {
        _con.push_back(*first++);
    }
    for (int father = (_con.size()-1-1) / 2; father >= 0; father++) {
        AdjustDown(father);
    }
}


我们就可以拿这个来解决一些问题，比如：

void test_priority_queue3() {
        // TOP K
        int arr[] = {1,4,2,7,8,9};
        priority_queue<int> pQ(arr, arr + 6);  // 传一个迭代器区间
    }

Ⅳ. 完整代码

0x00 stack

#include <iostream>
#include <deque>   // 做Container
#include <vector>  // 测试用
#include <list>    // 测试用
using namespace std;
namespace foxny {
    template<class T, class Container = deque<T>> 
    class stack {
        public:
            void push(const T& x) {
                _con.push_back(x);    // 对于栈而言，入栈就是尾插
            }
            void pop() {
                _con.pop_back();     // 对于栈而言，出栈就是尾删
            }
            const T& top() {
                return _con.back();  // 返回尾上数据
            }
            size_t size() {
                return _con.size();  // 返回大小
            }
            bool empty() {
                return _con.empty(); // 返回是否为空
            }
        private:
            Container _con;
    };
    void test_stack1() {
        stack<int> st;
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        while (!st.empty()) {
            cout << st.top() << " ";
            st.pop();   
        }
        cout << endl;
    }
    void test_stack2() {
        stack<int, vector<int>> st;  // 我想默认用 vector
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        while (!st.empty()) {
            cout << st.top() << " ";
            st.pop();   
        }
        cout << endl;
    }
    void test_stack3() {
        stack<int, list<int>> st;  // 我想默认用 list
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        while (!st.empty()) {
            cout << st.top() << " ";
            st.pop();   
        }
        cout << endl;
    }
}
int main(void)
{
    foxny::test_stack1();
    foxny::test_stack2();
    foxny::test_stack3();
    return 0;
}
0x01 queue
#include <iostream>
#include <deque>  // 做Container
#include <list>   // 测试用
using namespace std;
namespace foxny {
    template<class T, class Container = deque<T>> 
    class queue {
        public:
            void push(const T& x) { 
                _con.push_back(x); 
            }
            void pop() { 
                _con.pop_front(); 
            }
            const T& front() { 
                return _con.front(); 
            }
            const T& back() {
                return _con.back();
            }
            size_t size() { 
                return _con.size(); 
            }
            bool empty() { 
                return _con.empty(); 
            }
        private:
            Container _con;
    };
    void test_queue1() {
        queue<int> q;
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);
        while (!q.empty()) {
            cout << q.front() << " ";
            q.pop();
        }
        cout << endl;
    }
    void test_queue2() {
        queue<int, list<int>> q;
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);
        while (!q.empty()) {
            cout << q.front() << " ";
            q.pop();
        }
        cout << endl;
    }
}
int main(void)
{
    foxny::test_queue1();
    foxny::test_queue2();
    return 0;
}
0x02 priority_queue
#include <iostream>
#include <vector>
#include <functional>  // 这里放的是一些仿函数
#include <assert.h>
using namespace std;
namespace foxny {
    // less: 小于的比较
    template<class T> 
    struct less {
        bool operator()(const T& x, const T& y) const {
            return x < y;
        }
    };
    // greater: 大于的比较
    template<class T> 
    struct greater {
        bool operator()(const T& x, const T& y) const {
            return x > y;
        }
    };
    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue {
        Compare _cmpFunc;
    public:
        // 创造空的优先级队列
        priority_queue()
            : _con()
        {}
        // 迭代器
        template<class InputIterator>
        priority_queue (InputIterator first, InputIterator last) 
            : _con(first, last)
        {
            int count = _con.size();
            int root = ((count - 2) >> 1);
            for (; root >= 0; root--) {
                AdjustDown(root);
            }
        }
        /* 向上调整算法 */
        void AdjustUp(size_t child) {
            Compare cmpFunc;
            size_t father = (child - 1) / 2;
            while (child > 0) {
                // if (_con[father] < _con[child]) {
                if (cmpFunc(_con[father], _con[child])) {
                    swap(_con[father], _con[child]);
                    child = father;
                    father = (child - 1) / 2;
                }
                else {
                    break;
                }
            }
        }
        /* 向下调整算法 */
        void AdjustDown(size_t father) {
            Compare cmpFunc;
            size_t child = father * 2 + 1; // 默认认为左孩子大
            while (child < _con.size()) {
                // if (child + 1 < _con.size() && _con[child] < _con[child + 1]) {
                if (child + 1 < _con.size() && cmpFunc(_con[child], _con[child + 1])) {
                    child += 1;
                }
                // if (_con[father] < _con[child]) {
                if (cmpFunc(_con[father], _con[child])) {
                    swap(_con[father], _con[child]);
                    father = child;
                    child = father * 2 + 1;
                }
                else {
                    break;
                }
            }
        }
        /* 入数据 */
        void push(const T& x) {
            _con.push_back(x);
            AdjustUp(_con.size() - 1);
        }
        /* 出数据 */
        void pop() {
            assert(!_con.empty());
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            AdjustDown(0);
        }
        /* 返回堆顶数据 */
        const T& top() {
            return _con[0];
        }
        /* 返回大小 */
        size_t size() {
            return _con.size();
        }
        /* 判断是否为空 */
        bool empty() {
            return _con.empty();
        }
    private:
        Container _con;
    };
    // 小于比较，搞大堆
    void test_priority_queue1() {
        priority_queue<int> pQ;
        pQ.push(2);
        pQ.push(5);
        pQ.push(1);
        pQ.push(6);
        pQ.push(8);
        while (!pQ.empty()) {
            cout << pQ.top() << " ";
            pQ.pop();
        }
        cout << endl;
    }
    // 大于比较，搞小堆
    void test_priority_queue2() {
        priority_queue<int, vector<int>, greater<int>> pQ;
        pQ.push(2);
        pQ.push(5);
        pQ.push(1);
        pQ.push(6);
        pQ.push(8);
        while (!pQ.empty()) {
            cout << pQ.top() << " ";
            pQ.pop();
        }
        cout << endl;
    }
}
int main(void)
{
    foxny::test_priority_queue1();
    foxny::test_priority_queue2();
    return 0;
}


文章标签：
C++
C语言
算法
编译器
关键词：
C++ stack queue
C++ queue
C++ stack
C++ stack queue优先级队列
C++ queue优先级队列
柠檬叶子C
目录
相关文章
ephemerals__
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器：栈（stack）和队列（queue）。容器适配器是在已有容器基础上添加新特性或功能的结构，如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数（empty、size、top/front/back、push/pop、swap），并提供了使用示例和模拟实现代码。通过这些内容，读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后，作者鼓励读者点赞支持。 总结：本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现，帮助读者掌握这两种容器适配器的特性和应用场景。
ephemerals__
447 21
羑悻的小杀马特
|
设计模式 C++ 容器
c++中的Stack与Queue
c++中的Stack与Queue
羑悻的小杀马特
305 12
白子寰
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
白子寰
273 1
平凡程序猿~
|
编译器 C++ 开发者
【C++篇】深度解析类与对象（下）
在上一篇博客中，我们学习了C++的基础类与对象概念，包括类的定义、对象的使用和构造函数的作用。在这一篇，我们将深入探讨C++类的一些重要特性，如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象，以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念，提升代码的健壮性、灵活性和可维护性。
平凡程序猿~
440 0
ephemerals__
|
编译器 C++ 容器
【c++11】c++11新特性（上）（列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式）
C++11为C++带来了革命性变化，引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式，initializer_list简化了容器多元素初始化；右值引用和移动语义优化了资源管理，减少拷贝开销；类新增移动构造和移动赋值函数提升性能；lambda表达式提供匿名函数对象，增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展，提升了开发效率与程序性能。
ephemerals__
555 12
hahaha无
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果：注意：类模板中的成员函数若是放在类外定义时，需要加模板参数列表。return 0;
hahaha无
292 0
hahaha无
|
存储 编译器 程序员
c++的类（附含explicit关键字，友元，内部类）
本文介绍了C++中类的核心概念与用法，涵盖封装、继承、多态三大特性。重点讲解了类的定义（`class`与`struct`）、访问限定符（`private`、`public`、`protected`）、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数（构造函数、析构函数、拷贝构造、赋值重载）以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员（变量与函数）、友元（友元函数与友元类）的概念及其使用场景，并简要介绍了内部类的特性。
hahaha无
471 0
羑悻的小杀马特
|
编译器 C语言 C++
类和对象的简述（c++篇）
类和对象的简述（c++篇）
羑悻的小杀马特
377 28
蓝易云
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨，我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性，而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧，对于提升C++编程水平至关重要。
蓝易云
292 16
预备女程序员a
|
编译器 C++
类和对象（中 ）C++
本文详细讲解了C++中的默认成员函数，包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系，如构造函数的主要任务是初始化对象，而非创建空间；析构函数用于清理资源；拷贝构造与赋值运算符的区别在于前者用于创建新对象，后者用于已存在的对象赋值。同时，文章还探讨了运算符重载的规则及其应用场景，并通过实例加深理解。最后强调，若类中存在资源管理，需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。
预备女程序员a
400 1