-
STL之stack等容器适配器
写在前面
这个应该是我们STL最后一个博客了,今天是三个数据结构,分别是stack,queue和优先级队列,从某种意义上来说,他们不叫容器,叫做容器适配器.我们先来认识一下就可以了.
容器适配器
我们看一下他们的模板参数你就会明白了,第二个参数是一个Container.所谓的容器适配器就是我们不是自己实现的,而是借助另外一个数据结构来实现的.
这里我想和大家初步的解释一下什么适配器.在我们的日常生活中,我们知道大陆的民用电压是220v,但是你给手机充电的时候,可不是200v,这是由于你的手机充电器变压了.这个充电器就是一个适配器.也就是说一个东西能用,但是它的功能可能有点多,我们只需要拿出一小部分就可以了.
在计算机中也是如此,我们可以使用一种类来封装另外的一种类,我们直接复用他们的原本的方法,就不自己写了.
stack
这里我们不演示栈是如何使用的了,这个都是很简单的.主要看一下他们是如何实现的.
这里我们直接借助一个数据结构来模拟实现栈,至于下面的deque就暂时放一段落.
template <class T, class Container = std::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(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
这里我们测试一下,我们用标准库的来测试.
#includeint main() { stack<int,vector<int>> s; s.push(1); s.push(2); s.push(3); s.push(4); while (!s.empty()) { cout << s.top() << endl; s.pop(); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
是的,你没有看错,如果你不想用deque作容器,我们也是可以选择其他的,不过你选择的数据结构要有与之对应的函数,这也是STL中数据结构的函数名大多一样的好处.
queue
这个和stack是一样的,都是使用的另一个数据结构,没什么好谈的.
template<class T, class Container = std::deque<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.popfront(); } const T& top() { return _con.front(); } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } T& back() { return _con.back(); } const T& back()const { return _con.back(); } T& front() { return _con.front(); } const T& front()const { return _con.front(); } private: Container _con; };- 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
priority_queue 使用
这个叫做优先级队列,本质上的底层是一个堆.我们今天的重点就是这个内容.
我们可以先来看一下他们的接口,都是比较简单的
我们先来简单的用一下,这个默认的好象是大的优先级高,也就是建立大堆.
#include#include using namespace std; int main() { priority_queue<int> p; p.push(1); p.push(2); p.push(0); p.push(-1); p.push(1100); while (!p.empty()) { cout << p.top() << " "; p.pop(); } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
我们在想看,是不是可以建立一个小堆,标准库里面提供一个仿函数greater,这个可以帮助我们建立小堆.关于仿函数,这里大家先知道用法就可以了.后面我会分享到的.
int main() { priority_queue<int,vector<int>, greater<int>> p; p.push(1); p.push(2); p.push(0); p.push(-1); p.push(1100); while (!p.empty()) { cout << p.top() << " "; p.pop(); } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
priority_queue 模拟
现在我们也可以模拟一下priority_queue是如何被实现的了,它的本质是一个数组,也就是一个堆.这里面我们不谈如何向上调整或者是向下调整了,在数据结构那里都和大家分享过了,这里就不罗嗦了.主要是看看仿函数的使用.
优先级队列也是一个容器适配器.
template<class T> struct less { bool operator()(const T& t1, const T& t2) const { return t1 < t2; } }; template<class T> struct greater { bool operator()(const T& x, const T& y) const { return x > y; } }; template<class T, class Container = std::vector<T>, class Compare = bit::less<T>> class priority_queue { public: priority_queue() { } private: Container _con; };- 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
push
入堆
void push(const T& x) { _con.push_back(x); adjustUp(_con.size() - 1); }- 1
- 2
- 3
- 4
- 5
pop()
出堆
void pop() { assert(!_con.empty()); std::swap(_con[0], _con[size() - 1]); _con.pop_back(); adjustDwon(0); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
top()
查看堆定的元素
const T& top() { return _con[0]; }- 1
- 2
- 3
- 4
调整
我们数据入堆或者出堆都是需要完成调整的,而且如果我们把堆中元素的优先级写死的话,代码的灵活性就不行了,比如我们想要的是小堆,你给我是现成大堆.这就是一个问题,我们在像,不是可以控制一下,早期的可能是使用函数指针来实现的,但是函数指针的阅读性实在是太不好了,我们逐渐改成了仿函数.
仿函数
我们先来认识一下仿函数,大家看一下这样的一个结构体.
struct MyStruct { bool operator()(const int x, const int y) { return x > y; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
我们重载了()运算符,这个使我们的调用看着和函数的调用很像,所以我们称为仿函数.
int main() { MyStruct comfunc; cout << comfunc(1, 2) << endl; return 0; }- 1
- 2
- 3
- 4
- 5
- 6
void adjustDwon(size_t parent) { Compare comFunc; size_t child = 2 * parent + 1; while (child < size()) { if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1])) { child++; } if (comFunc(_con[parent], _con[child])) { std::swap(_con[parent], _con[child]); parent = child; child = 2 * child + 1; } else { break; } } } void adjustUp(int child) { // 先 建大堆 Compare comFunc; size_t parent = (child - 1) / 2; while (child > 0) { if (comFunc(_con[parent], _con[child])) { std::swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } }- 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
仿函数最大的优势就是替代函数指针,对于自定类型,我们也可以单独的写出他们的仿函数,不过要求自定类型重载了>等运算符.但是我们也是知道C++是支持C语言的,我们在前面学习qsort的时候使用过函数指指针的,那么我们是不是也可以在这里传入函数指针.可以的,但是需要些方法.
我们先来假设一下我们可以原来qsort那样来用一下.
bool comFare(int x, int y) { return x > y; } int main() { bit::priority_queue<int, vector<int>, bool(*)(int, int)> p; p.push(1); p.push(3); p.push(2); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
现在我们就要疑惑一下了,我们第三个模板参数传入的是一个函数指针类型,这可以看作是一个内置类型,编译器对自动调用它的构造函数,给他初始化nullptr.所以编译器会报错.这里我们就开始为难,我们该和把自己想要的比较函数传进去呢?这里我们模板参数不行,但是构造函数是可以的.
我们把模板参数可以实例化的对象当作类里面的一个成员变量,这样的话我们就是在构造函数的时候给他初始化了.我们需要改造一下构造函数.’
这样的话我们就可以这样的使用优先级队列了.
bool comFare(int x, int y) { return x > y; } int main() { bit::priority_queue<int, vector<int>, bool(*)(int, int)> p(comFare); //bit::priority_queuep(comFare); p.push(1); p.push(3); p.push(2); p.push(0); p.push(-1); while (!p.empty()) { cout << p.top() << " "; p.pop(); } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
我们试试之前的用法可以使用吗?我们发现是可以的,后面我们就需要解释一下原理.
int main() { //bit::priority_queue- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
我先来解释一下传入的是函数指针类型.我们知道,实例化对象会调用默认构造函数,也就是下面的.而且我们在实例化对象的时候传入了参数,第三个模板参数的类型变成了函数指针类型.这里的类型是相互匹配的.
这样我们就可以理解如果我们不传入函数指针类型,那么第三个模板参数默认是它的默认值,也就是仿函数类型西,编译器自动调用构造函数,又给仿函数类型实例化对象了,这就是能够使用的原因.我们这就知道我们可以使用函数指针,但是有简单的为何要用麻烦的呢!
sort
这里我们还要看一下仿函数的应用,最好的体现就是这个sort函数,这是STL算法库里面提供的一个函数，我们在看迭代器类型的时候就让大家见识过了．这里不做详细简绍，只谈和仿函数相关的知识．
int main() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(13); v.push_back(-1); sort(v.begin(), v.end()); for (int val : v) { cout << val << " "; } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
我们注意到这默认的是升序,我们是不是可以让他们降序呢?可以的,这就要借助仿函数.
int main() { vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(13); v.push_back(-1); sort(v.begin(), v.end(),greater<int>()); for (int val : v) { cout << val << " "; } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
注意看上面的sort里面的参数,我们发现自己传入的是一个仿函数的匿名对象,这一点和前面的有点不同.倒着里我们就可以明白仿函数的具体用途了,就是作为判断是升序还是降序的条件.
为何传入对象
这里我们需要解释一下为何要传入对象,而不是简单的传入类型.首先一点就是我们可能要自己来定义变量,这就是意味着如果我们传入的是类型,那么我们需要在类型里面重载一些操作符.而且我们比较的方法就固定了.
struct Goods { string _name; double _price; size_t _saleNum; //... bool operator<(const Goods& g) const { return _price < g._price; } bool operator>(const Goods& g) const { return _price > g._price; } }; int main() { Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} }; sort(gds, gds + 4,greater<Goods>()); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
但是这里的比较规则已经确定了,我们只能通过价格来比较,那么如果我们想通过销量比较呢.这就是一个问题.所以这里面我们传入对象,我们可以每一个比较规则封装成一个类,把它实例化出来就可以了.一般而言less里面是小于,对应的是升序.
struct Goods { string _name; double _price; size_t _saleNum; //... }; struct LessPrice { bool operator()(const Goods& g1, const Goods& g2) const { return g1._price < g2._price; } }; struct GreaterPrice { bool operator()(const Goods& g1, const Goods& g2) const { return g1._price > g2._price; } }; struct LessSaleNum { bool operator()(const Goods& g1, const Goods& g2) const { return g1._saleNum < g2._saleNum; } }; struct GreaterSaleNum { bool operator()(const Goods& g1, const Goods& g2) const { return g1._saleNum > g2._saleNum; } }; int main() { Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} }; cout << "=======================" << endl; for (int i = 0; i < 4; i++) { cout << gds[i]._name << " price : " << gds[i]._price << " saleNum: " << gds[i]._saleNum << endl; } cout << "=======================" << endl; sort(gds, gds + 4, LessSaleNum()); cout << "=======================" << endl; for (int i = 0; i < 4; i++) { cout << gds[i]._name << " price : " << gds[i]._price << " saleNum: " << gds[i]._saleNum << endl; } cout << "=======================" << endl; sort(gds, gds + 4, GreaterSaleNum()); cout << "=======================" << endl; for (int i = 0; i < 4; i++) { cout << gds[i]._name << " price : " << gds[i]._price << " saleNum: " << gds[i]._saleNum << endl; } cout << "=======================" << endl; return 0; }- 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
了解 deque
到这里我们需要了解一下deque.这个也是一个数据结构,他倒是没有什么可以谈的,我们今天只是看看他的底层结构
我们知道如果物理内存是连续的,那么CPU访问的速度是很快的,对于list,这是一个节点.我们是不不是可以这么想,假设我们把一小段碎片化空间看作vector,几个小空间连在一起,看作list.这样的话可以在一定的程度上提高效率.
这里我们还需要一个数组记录每个碎片化空间的地址.
首先我先说的是,这种想法是很不错的,但是它的实际效率可是低得很,一般我们是不这么做的.
反向迭代器
我们前面的list只是实现了正向迭代器,这里我们已经见过适配器,这里就可以看看我们的反向迭代器了,这是由正向迭代器适配出来的.
我们先来看一下源码就明白了.
我们就明白了方向迭代器的++或者–的方向不一样,其他的都一样,所以C++就站在了顶层的模式来看看它们.我们这里就要实现一下反向的迭代器,我们先实现一个比较挫的版本,后面在和大家谈上面的版本是如何是是实现的.
反向迭代器
我们重点谈一下解引用,这个涉及到我们之前的一个list设计原理.
template<class Iterator, class Ref, class Ptr> struct Reverse_iterator { Iterator _it; typedef Reverse_iterator<Iterator, Ref, Ptr> Self; Reverse_iterator(Iterator it) :_it(it) {} Ref operator*() { Iterator tmp = _it; return *(--tmp); } Ptr operator->() { return &(operator*()); } Self& operator++() { --_it; return *this; } Self& operator--() { ++_it; return *this; } bool operator!=(const Self& s) { return _it != s._it; } };- 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
我们前面谈过,list的迭代器这样把end和begin设计的.
那么同样,我们这里需要进行对称设计,那么对称出来的结果应该就是这样的.我们解引用的时候去解引用前面的一个节点的值就可以了
reverse_iterator rbegin() { return iterator(end()); } reverse_iterator rend() { return iterator(begin()); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
再析反向迭代器
我们还是需要再谈谈反向迭代器的,虽然上面我们已经实现出来了,但是这里仍旧存在一个小问题,我们传入的模板参数是三个,但是我看到标准库里面只有一个.我想和它一样.我们下来看一下标准的迭代器是如何实现的.
正向迭代器里面需要存在某些东西,这样我们才能完成迭代器萃取,
template<class Iterator> struct Reverse_iterator { Iterator _it; typedef Reverse_iterator<Iterator> Self; Reverse_iterator(Iterator it) :_it(it) {} Iterator::reference operator*() { Iterator tmp = _it; return *(--tmp); } Iterator::pointer operator->() { return &(operator*()); } Self& operator++() { --_it; return *this; } Self& operator--() { ++_it; return *this; } bool operator!=(const Self& s) { return _it != s._it; } };- 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
要知道正向的迭代器本质就是一个模板,我们在模板里面寻找具体的参数,这是编译器是不允许的,这里我们就需要一个关键字了.
typename
这个关键字我们之前是见过的，我们先不谈原来的功能。这里直接解释一下为何要这么做以及这么做能解决问题的原因？首先我们知道正向迭代器本来就是一个模板类，我们在模板类里面寻找模板里面的类型，那么只能得到一个虚拟类型，typename这个关键字可以告诉编译器我们这个是模板类里面的类型，你需要等一会，等到这个类型实例化之后再来取这个类型。
typename Iterator::reference operator*() { Iterator tmp = _it; return *(--tmp); } typename Iterator::pointer operator->() { return &(operator*()); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
我们还可以在反向类里面重新重命名,这样的话可以更见简便一点.
typedef typename Iterator::reference Ref; typedef typename Iterator::pointer Ptr; Reverse_iterator(Iterator it) :_it(it) {} Ref operator*() { Iterator tmp = _it; return *(--tmp); } Ptr operator->() { return &(operator*()); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
这里我们还要谈一下这个关键字,主要是为了让大家更好的理解一下,至于迭代器这里我们就谈到这了,再往后面谈就到迭代器萃取的原理了,那个更加痛苦.
大家先来看一下下面的代码,
#include#include - 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
这里面就是因为list一个模板,我们去模板里面去他们的类型是不被编译器允许的,这里需要加上一个typename.
template<class T> void list_print(list<T>& l) { typename list<T>::const_iterator cit = l.cbegin(); while (cit != l.cend()) { cout << *cit << " "; ++cit; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
-
相关阅读:
【机器学习】基于多元时间序列对高考预测分析案例
Splunk UBA 导入Asset 设备
十三、函数式编程（1）
T225362 《山茶文具店》
Chrome 插件推荐
LeetCode //C - 17. Letter Combinations of a Phone Number
汇编：寄存器/register，基础概念
Python if-for-while使用
Amazon Linux 2022 来袭，AWS 承诺后续每两年更新一次
java-反射
- 原文地址：https://blog.csdn.net/m0_61334618/article/details/126490805
