写在前面
这个应该是我们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;
}; 这里我们测试一下,我们用标准库的来测试.
#include <stack>
int 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;
} 是的,你没有看错,如果你不想用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;
}; priority_queue 使用
这个叫做优先级队列,本质上的底层是一个堆.我们今天的重点就是这个内容.
我们可以先来看一下他们的接口,都是比较简单的
我们先来简单的用一下,这个默认的好象是大的优先级高,也就是建立大堆.
#include <iostream>
#include <queue>
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;
} 我们在想看,是不是可以建立一个小堆,标准库里面提供一个仿函数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;
} 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;
}; push
入堆
void push(const T& x)
{
_con.push_back(x);
adjustUp(_con.size() - 1);
} pop()
出堆
void pop()
{
assert(!_con.empty());
std::swap(_con[0], _con[size() - 1]);
_con.pop_back();
adjustDwon(0);
} top()
查看堆定的元素
const T& top()
{
return _con[0];
} 调整
我们数据入堆或者出堆都是需要完成调整的,而且如果我们把堆中元素的优先级写死的话,代码的灵活性就不行了,比如我们想要的是小堆,你给我是现成大堆.这就是一个问题,我们在像,不是可以控制一下,早期的可能是使用函数指针来实现的,但是函数指针的阅读性实在是太不好了,我们逐渐改成了仿函数.
仿函数
我们先来认识一下仿函数,大家看一下这样的一个结构体.
struct MyStruct
{
bool operator()(const int x, const int y)
{
return x > y;
}
}; 我们重载了()运算符,这个使我们的调用看着和函数的调用很像,所以我们称为仿函数.
int main()
{
MyStruct comfunc;
cout << comfunc(1, 2) << endl;
return 0;
} 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;
}
}
} 仿函数最大的优势就是替代函数指针,对于自定类型,我们也可以单独的写出他们的仿函数,不过要求自定类型重载了>等运算符.但是我们也是知道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;
} 现在我们就要疑惑一下了,我们第三个模板参数传入的是一个函数指针类型,这可以看作是一个内置类型,编译器对自动调用它的构造函数,给他初始化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_queue<int> p(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;
} 我们试试之前的用法可以使用吗?我们发现是可以的,后面我们就需要解释一下原理.
int main()
{
//bit::priority_queue<int, vector<int>, bool(*)(int, int)> p(comFare);
bit::priority_queue<int> p;
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;
} 我先来解释一下传入的是函数指针类型.我们知道,实例化对象会调用默认构造函数,也就是下面的.而且我们在实例化对象的时候传入了参数,第三个模板参数的类型变成了函数指针类型.这里的类型是相互匹配的.
这样我们就可以理解如果我们不传入函数指针类型,那么第三个模板参数默认是它的默认值,也就是仿函数类型西,编译器自动调用构造函数,又给仿函数类型实例化对象了,这就是能够使用的原因.我们这就知道我们可以使用函数指针,但是有简单的为何要用麻烦的呢!
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;
} 我们注意到这默认的是升序,我们是不是可以让他们降序呢?可以的,这就要借助仿函数.
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;
} 注意看上面的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;
} 但是这里的比较规则已经确定了,我们只能通过价格来比较,那么如果我们想通过销量比较呢.这就是一个问题.所以这里面我们传入对象,我们可以每一个比较规则封装成一个类,把它实例化出来就可以了.一般而言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;
} 了解 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;
}
}; 我们前面谈过,list的迭代器这样把end和begin设计的.
那么同样,我们这里需要进行对称设计,那么对称出来的结果应该就是这样的.我们解引用的时候去解引用前面的一个节点的值就可以了
reverse_iterator rbegin()
{
return iterator(end());
}
reverse_iterator rend()
{
return iterator(begin());
} 再析反向迭代器
我们还是需要再谈谈反向迭代器的,虽然上面我们已经实现出来了,但是这里仍旧存在一个小问题,我们传入的模板参数是三个,但是我看到标准库里面只有一个.我想和它一样.我们下来看一下标准的迭代器是如何实现的.
正向迭代器里面需要存在某些东西,这样我们才能完成迭代器萃取,
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;
}
}; 要知道正向的迭代器本质就是一个模板,我们在模板里面寻找具体的参数,这是编译器是不允许的,这里我们就需要一个关键字了.
typename
这个关键字我们之前是见过的，我们先不谈原来的功能。这里直接解释一下为何要这么做以及这么做能解决问题的原因？首先我们知道正向迭代器本来就是一个模板类，我们在模板类里面寻找模板里面的类型，那么只能得到一个虚拟类型，typename这个关键字可以告诉编译器我们这个是模板类里面的类型，你需要等一会，等到这个类型实例化之后再来取这个类型。
typename Iterator::reference operator*()
{
Iterator tmp = _it;
return *(--tmp);
}
typename Iterator::pointer operator->()
{
return &(operator*());
} 我们还可以在反向类里面重新重命名,这样的话可以更见简便一点.
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*());
} 这里我们还要谈一下这个关键字,主要是为了让大家更好的理解一下,至于迭代器这里我们就谈到这了,再往后面谈就到迭代器萃取的原理了,那个更加痛苦.
大家先来看一下下面的代码,
#include <iostream>
#include <list>
using namespace std;
template<class T>
void list_print(list<T>& l)
{
list<T>::const_iterator cit = l.cbegin();
while (cit != l.cend())
{
cout << *cit << " ";
++cit;
}
}
int main()
{
list<int> l;
l.push_back(1);
l.push_back(1);
l.push_back(1);
l.push_back(1);
l.push_back(1);
l.push_back(1);
list_print(l);
list<string> lstr;
lstr.push_back("qqqq");
lstr.push_back("qqqq");
lstr.push_back("qqqq");
lstr.push_back("qqqq");
lstr.push_back("qqqq");
list_print(lstr);
return 0;
} template<class T>
void list_print(list<T>& l)
{
typename list<T>::const_iterator cit = l.cbegin();
while (cit != l.cend())
{
cout << *cit << " ";
++cit;
}
}