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

简介: 在上一章中,我们讲解了STL的栈和队列,本章我们来模拟实现一下它们。在讲解优先级队列的同时我们顺便把上一章提到的仿函数进行一个讲解,使用仿函数可以有效替换使用难以理解的函数指针的场景。我们通过仿函数 less 和 greater 去控制优先级队列的 Compare,从而能同时适配升序和降序。

💭 写在前面


在上一章中,我们讲解了STL的栈和队列,本章我们来模拟实现一下它们。在讲解优先级队列的同时我们顺便把上一章提到的仿函数进行一个讲解,使用仿函数可以有效替换使用难以理解的函数指针的场景。我们通过仿函数 less 和 greater 去控制优先级队列的 Compare,从而能同时适配升序和降序。


Ⅰ. 模拟实现 stack


0x00 实现思路

be5d1ddf84672f3a38ec21f132ba924b_6664c380fe1c442ca05ca15aa498af05.png

插入数据删除数据这些逻辑其实没有必要自己实现,而是采用转换的方式。


两章前我们讲解了适配器的知识,这里采用的就是一些其它的适配的容器去实现。


至于这里转换什么,我们可以进一步思考,似乎有很多容器都适合去转换,


所以 STL 增加了一个模板参数 Container,利用 Container 来进行转换。


在上一章的末尾,我们讲述了利用 deque 去实现栈和队列是最合适不过的了:


template<class T, class Container = deque<T>>

(至于 deque 的底层我们放到后面去说,我们先学会如何用 deque 去实现栈和队列)


对于栈而言,push 插入数据就是尾插 push_back,pop 删除数据就是尾删 pop_back,

void push(const T& x) {
    _con.push_back(x);    // 对于栈而言,入栈就是尾插
}
void pop() {
    _con.pop_back();      // 对于栈而言,出栈就是尾删
}

返回堆顶数据我们可以用 back(),即可达到返回尾上数据的效果,本质上是一种封装。

const T& top() {
    return _con.back();  // 返回尾上数据
}

这里甚至都不需要考虑断言,因为那是下层需要做的事情,这里我们要做的只是 "转换" 。


💬 代码:stack

#include <iostream>
#include <deque>
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;
    };
}


0x01 代码测试

先默认用 deque 去存储:

#include <iostream>
#include <deque>
using namespace std;
namespace foxny {
    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;
    }
}

🚩 运行结果:

b8a1bff7ff33187ea355708b26f83fd9_bf50ef3781e74d5b958e2c7f0efa44df.png

默认传 deque,如果不想用 deque,你可以自由的去传。

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
namespace foxny {
    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;
    }
}


🚩 运行结果:

d5d034d3e84d6fc80f6435f1a05853cb_e2c9f4a1c1ff49bdb86ca22ce406c278.png


我们再试试默认用 list 可不可以:

#include <iostream>
#include <deque>
#include <list>
using namespace std;
namespace foxny {
    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;
    }
}


🚩 运行结果:

cab7a88c63f2e4fd8173b615e7b90618_46cfd7aae5e7404b9faf457789f955fa.png


❓ 思考:可否用 string?


勉强可以,只要你是顺序容器都可以。但是用 string 是有风险的,可能会出现溢出和截断。


#include <iostream>
#include <deque>
#include <string>
using namespace std;
namespace foxny {
    void test_stack4() {
        stack<int, string> st;  // 我想默认用 string
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(400);   // 这里推一个400看看
        while (!st.empty()) {
            cout << st.top() << " ";
            st.pop();   
        }
        cout << endl;
    }
}


🚩 运行结果:

984b5a2b69a03c5b065622f843d2b5a1_6fa35ea4ab7b46eda826d83cf356a20f.png

🔺 总结:从上层角度来看,其默认是一个双端队列,我底层用什么存,去实现这个栈并不重要,只要其符合要求就行。它保存的是栈的性质,复用的是容器的代码。


Ⅱ. 模拟实现 queue


0x00 实现思路

一回生二回熟,其默认容器也是 deque,直接照着 stack 的基础去修改成 queue 即可。

template<class T, class Container = deque<T>>

queue 是先进先出的,queue 的 push 仍然是尾部的插入,而 pop 需要支持头部的删除。

void push(const T& x) { 
    _con.push_back(x);  // 进队
}
void pop() { 
    _con.pop_front();   // 出队
}

值得注意的是,queue 不能用 vector 去适配,因为 vector 压根就没有 pop_front 这个接口。


(我看你是在刁难我胖虎.jpg)


queue 的 front 和 back 我们直接调 front 和 back 去取队列头尾的数据即可:


const T& front() { 
    return _con.front(); 
}
const T& back() {
    return _con.back();
}

剩下的 size 和 empty 都不用变。


💬 代码实现:queue

#include <iostream>
#include <deque>
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;
    };
}

0x01 代码测试

先测试默认用 deque 去存储:

#include <iostream>
#include <deque>
using namespace std;
namespace foxny {
    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;
    }
}


🚩 运行结果:

c4c727084748592c3d9abb68674e18b4_704bb57181c14d7b88cffe04b38d4a57.png


指定用 list 去存:

#include <iostream>
#include <deque>
#include <list>
using namespace std;
namespace foxny {
    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;
    }
}

🚩 运行结果:

31030fa52c1e7d7141c7c1d86556a492_773b7595dbc1444c9c7560075801fca6.png


我们来试一下指定用 vector 会怎么样:

#include <iostream>
#include <deque>
#include <vector>
using namespace std;
namespace foxny {
    void test_queue3() {
        queue<int, vector<int>> q;
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);
        while (!q.empty()) {
            cout << q.front() << " ";
            q.pop();
        }
        cout << endl;
    }
}


🚩 运行结果:

error C2039: "pop_front": 不是 "std::vector<int,std::allocator<T>>" 的成员
1>        with
1>        [
1>            T=int
1>        ]
1>D:\360MoveData\Users\Chaos\Desktop\code2022\2022_7_17\2022_7_17\test.cpp(62): message : 参见“std::vector<int,std::allocator<T>>”的声明
1>        with
1>        [
1>            T=int
1>        ]
1>D:\360MoveData\Users\Chaos\Desktop\code2022\2022_7_17\2022_7_17\test.cpp(14): message : 在编译 类 模板 成员函数“void foxny::queue<int,std::vector<int,std::allocator<T>>>::pop(void)”时……


正所谓 —— 明知山有虎,别去明知山。明知 vector 无头删,队列就别用 vector!


用其他东西转换搞出来的栈和队列,只要符合要求就可以。实际上也不一定真的是直接转换。


我们下面还要学一个更复杂的

相关文章
|
4天前
|
设计模式 C++ 容器
c++中的Stack与Queue
c++中的Stack与Queue
|
26天前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
56 21
|
4月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
62 1
|
1天前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
1天前
|
安全 编译器 C语言
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
|
1天前
|
存储 程序员 C语言
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。
|
4天前
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
70 19
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
51 13
|
1月前
|
编译器 数据安全/隐私保护 C++
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
53 5