目录
- 适配器：
- 适配器的应用：
- 1. 优先级队列：
- 仿函数：
- 更深入的了解仿函数：
- 一个关于不容易被注意的知识点：
- 2. 反向迭代器：list && vector：
适配器：
我们先来谈来一下容器适配器的概念：
适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。
适配器的应用：
1. 优先级队列：
仿函数我们暂时不提。
优先级队列其实就是我们的常说的堆。
那我们直接按照堆的方式进行创建一个优先级队列的类即可。
可以参考堆的博客
另外由于我们是采取适配器模式，于是可以直接在模版列表多加一个vector<T>的缺省,
可以理解为对已有的容器进行封装形成我们需要的容器。
注意：我们此时的代码实现的是大堆。
template<class T, class Container = vector<T>>
class priority_queue
{
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator end)
:con(first, end)
{
for (int i = (con.size() - 2) / 2; i >= 0; i--)
{
adjust_down(i);
}
}
void adjust_up(int child)
{
while (child > 0)
{
int parent = (child - 1) / 2;
if (con[parent] < con[child])
{
swap(con[parent], con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& val)
{
con.push_back(val);
adjust_up(con.size() - 1);
}
void adjust_down(int parent)
{
int child = parent * 2 + 1;
while (child < con.size())
{
if (child + 1 < con.size() && con[child]< con[child + 1])
{
child++;
}
if (con[parent]< con[child])
{
swap(con[parent], con[child]);
}
parent = child;
child = child * 2 + 1;
}
}
void pop()
{
swap(con[0], con[con.size() - 1]);
con.pop_back();
adjust_down(0);
}
const T& top()
{
return con[0];
}
size_t size()
{
return con.size();
}
bool empty()
{
return con.size() == 0;
}
private:
Container con;
};
在另外说一下，对于迭代器区间构造我们选择使用向上调整算法，这是因为向上调整算法建堆是要优于向下建堆的
仿函数：
但是我们在这里还有一个问题，每次我们想改变大堆或者小堆时，都要进行对代码的修改，再C语言中我们可以使用函数指针来解决，qsort就是一个很好的例子。
使用函数指针进行升序还是降序的选择，我们的C++当然也可以选择这样做，但是C++并不喜欢指针，于是应时而生一个仿函数
什么是仿函数？
通过上图我们就可以得出一个结论：
当类中重载()操作符时即可称之为仿函数。
那我们现在就可以使用仿函数随心所欲的更改大堆还是小堆了
template<class T>
struct Less
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
template<class T>
struct Greater
{
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
template<class T, class Container = vector<T>, class Compare = Less<T>>
class priority_queue
{
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator end)
:con(first, end)
{
for (int i = (con.size() - 2) / 2; i >= 0; i--)
{
adjust_down(i);
}
}
void adjust_up(int child)
{
while (child > 0)
{
Compare com;
int parent = (child - 1) / 2;
if (com(con[parent], con[child]))
{
swap(con[parent], con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& val)
{
con.push_back(val);
adjust_up(con.size() - 1);
}
void adjust_down(int parent)
{
int child = parent * 2 + 1;
Compare com;
while (child < con.size())
{
if (child + 1 < con.size() && com(con[child], con[child + 1]))
{
child++;
}
if (com(con[parent], con[child]))
{
swap(con[parent], con[child]);
}
parent = child;
child = child * 2 + 1;
}
}
void pop()
{
swap(con[0], con[con.size() - 1]);
con.pop_back();
adjust_down(0);
}
const T& top()
{
return con[0];
}
size_t size()
{
return con.size();
}
bool empty()
{
return con.size() == 0;
}
private:
Container con;
};
到这也就实现了与库中类似的优先级队列。
库中less实现的是小堆，greater是大堆，我们这的实现与库中保持一致。
更深入的了解仿函数：
我们已经掌握了仿函数的初阶用法
假设我们现在有一个Date类
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d)const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
我们使用优先级队列对3个日期对象进行排序：
int main()
{
cyc::priority_queue<Date> pq;
Date d1(2000, 2, 20);
pq.push(d1);
pq.push(Date(2000, 2, 21));
pq.push({2000, 2, 22});
while (!pq.empty())
{
cout << pq.top() << endl;
pq.pop();
}
cout << endl;
return 0;
}
我们在这里使用了3中传参方式，有名对象，匿名对象，初始化列表传参。
一个关于不容易被注意的知识点：
匿名对象其实是具有const属性哦！
class A
{
private:
int a;
int b;
};
int main()
{
const A& ref = A();
//匿名对象是const对象。
return 0;
}
不加const会报错。
但是我们const自定义类型对象也可以调用非const成员函数
class A
{
public:
void print()
{}
private:
int a;
int b;
};
int main()
{
const A& ref = A();
//匿名对象是const对象。
A().print();
return 0;
}
这是经常不被注意的一个点，也算是编译器对于某些场景的特殊处理。
不过到现在这也仅仅是我们已经掌握的知识，如果我们传入的是Date类型的指针呢？
答案依旧如我们所料，传入指针，那么指针是内置类型，肯定就直接对只怎的大小进行比较，那我们如何解决这个问题？
操作符重载可以吗？
答案是不可以的，不可重载内置类型，故排除此方案。
那么仿函数？
答案是肯定可以的。
如何使用仿函数进行解决？
struct PDateLess
{
bool operator()(const Date* left, const Date* right)
{
return *left < *right;
}
};
给模版类型时我们给自己实现的仿函数即可！
cyc::priority_queue<Date*, vector<Date*>, PDateLess> pq;
Date* pd1 = new Date(2000, 2, 20);
Date* pd2 = new Date(2000, 2, 21);
Date* pd3 = new Date(2000, 2, 22);
pq.push(pd1);
pq.push(pd2);
pq.push(pd3);
while (!pq.empty())
{
cout << *pq.top() << endl;
pq.pop();
}
所以，我们可以自定义仿函数行为！
到这里不知道有没有细心的小伙伴发现，我们有时候模版给的是类型，有时给的是对象
就像优先级队列与sort库函数。
本质的区别是因为一个是类模版，一个是函数模版！
2. 反向迭代器：list && vector：
我们在来进阶的看一下适配器，
适配器是将一个容器封装成我们需要的容器
stl库实现反向迭代器的思路是不是在重新写一个反向迭代器类，而是利用普通迭代器封装为反向迭代器！
他们之间是一个上下层的关系！
而const迭代器与普通迭代器是一个平行的关系！
首先如果我们自己利用如上思路进行实现的话。
大概率如下图代码一样，这样写的话，注意我们的重载*的返回值应该怎么写？
template<class Iterator>
struct ReverseIterator
{
typedef ReverseIterator<Iterator> self;
Iterator rit;
ReverseIterator(Iterator it)
{
rit(it);
}
self& operator++()
{
rit--;
return *this;
}
self& operator--()
{
rit++;
return *this;
}
//返回值怎么写？
operator*()
{
return *rit;
}
};
为了解决这一问题我们入
持续更新…
