@TOC
优先级队列 priority_queue 与 仿函数 greater / less
仿函数
定义及优点
定义：定义一个类，类里面重载函数运算符()，将该类的对象作为函数的入参，那么在函数中同样能调用重载符()里面的方法。
优点：相比于普通函数，仿函数的声明更为简单。
例如：用普通函数，仿函数写一个swap函数，并将其以参数的形式，如下：
//普通函数
template<class T>
void _swap(T& a, T& b)
{ T c = a; a = b; b = c; }
//声明参数
void(*p)(int&, int&) = _swap;
再来看看仿函数写法：
```cpp
//仿函数
template<class T>
struct _swap
{
void operator()(T& a, T& b)
{ T c = a; a = b; b = c; }
};
//声明参数
_swap<int> p;
我们可以看到函数指针，在面向对象开发的过程中编写有点繁琐，所以C++的仿函数借此代替了函数指针。
有了上面理解的铺垫就可以，很轻松的理解下面两个仿函数了。
greater
template<class T>
class greater
{
public:
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
less
template<class T>
class less
{
public:
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
优先级队列
priority_queue
定义：优先级队列的本质其实是一个堆，插入数据时内部按照所给的仿函数为参考进行（堆）排序，确保第一个元素为最值，存在默认的缺省值，一般采用vector为适配器，Less为仿函数.
如下：
template <class T, class Container = vector<T>, class Compare = less<T>>
构造/类的成员
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 last)
{
InputIterator it = first;
while (it != last)
{
push(*it);
it++;
}
//循环遍历插入即可
}
private:
Container c;
Compare comp;
);
Compare是仿函数的类型，Container是适配器的类型 。
这里我们采用的是适配器模式，在对象生命周期结束时，会自动调用默认的构析函数。因为适配器为自定义类型，所以又会自动调用适配器的构析函数，所以我们不需要写构析函数，同理拷贝构造也可以不写。
这里我们写了一个以迭代器为参数的构造函数，所以还是要写一个无参的默认构造函数，什么事都不用做，因为适配器会自动调用它的构造函数。
插入函数 push(const T& x)
插入函数的实现就是利用适配器的插入，再将其插入的数进行向上调整即可。
再向上调整的过程中利用反函数的返回结果作为参考。
void AdjustUp(int child)
{
int father = (child - 1) / 2;
while (father >= 0)
{
if (comp(c[father], c[child]))
{
swap(c[father], c[child]);
child = father;
father = (child - 1) / 2;
}
else break;
}
}
void push(const T& x)
{
c.push_back(x);
AdjustUp(c.size() - 1);
}
删除函数 pop()
删除函数和堆的删除相同。
void AdjustDown(int father)
{
int child = father * 2 + 1, n = c.size();
while (child < n)
{
if (child + 1 < n && comp(c[child], c[child + 1])) child++;
if (comp(c[father], c[child]))
{
swap(c[father], c[child]);
father = child;
child = father * 2 + 1;
}
else break;
}
}
void pop()
{
swap(c[0], c[c.size() - 1]);
c.pop_back();
AdjustDown(0);
}
其他接口
其他功能可以直接通过适配器的调用即可.
bool empty() const
{
return c.empty();
}
size_t size() const
{
return c.size();
}
const T& top() const
{
return c[0];
}
源代码
源代码如下:
template<class T>
class less
{
public:
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
template<class T>
class greater
{
public:
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 last)
{
InputIterator it = first;
while (it != last)
{
push(*it);
it++;
}
}
bool empty() const
{
return c.empty();
}
size_t size() const
{
return c.size();
}
const T& top() const
{
return c[0];
}
void AdjustUp(int child)
{
int father = (child - 1) / 2;
while (father >= 0)
{
if (comp(c[father], c[child]))
{
swap(c[father], c[child]);
child = father;
father = (child - 1) / 2;
}
else break;
}
}
void push(const T& x)
{
c.push_back(x);
AdjustUp(c.size() - 1);
}
void AdjustDown(int father)
{
int child = father * 2 + 1, n = c.size();
while (child < n)
{
if (child + 1 < n && comp(c[child], c[child + 1])) child++;
if (comp(c[father], c[child]))
{
swap(c[father], c[child]);
father = child;
child = father * 2 + 1;
}
else break;
}
}
void pop()
{
swap(c[0], c[c.size() - 1]);
c.pop_back();
AdjustDown(0);
}
private:
Container c;
Compare comp;
};
结语
以上就是本期的全部内容了，喜欢就多多关注吧！！！
