C++ Compare 学习

基本用法

C++ STL 中许多容器涉及比较，如map,set,priority_queue等，这就需要我们实现元素的比较方法。

以map为例(before c++17)：

template < 
    class Key, 
    class T, 
    class Compare = less<Key>,
    class Allocator = allocator<pair<const Key,T> > 
> class map;

以priority_queue为例：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

二者都有一个名为Compare的class。但是需要注意的是，cppreference在priority_queue中有这样一段话:

Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that “come before” are actually output last. That is, the front of the queue contains the “last” element according to the weak ordering imposed by Compare.

• 也即如果元素 a、b 的弱序为 <a, b>, 那么 a 比 b “小”，b 比 a “大”，a 排在 b 的前面。但是优先队列先输出最“大”的元素，故 Compare 定义了小于关系，实质是输出大顶堆，定义了大于关系，实质是输出小顶堆。这正好对应离散数学的相关概念。
• 此外弱序若还是反对称的，则就是全序。

在map和其他一些 STL 容器中，Compare 定义的顺序就是实际的输出顺序了。

这个优先队列（堆）之所以很特殊，在于其本身的性质及其理解离散数学中偏序概念的角度比较独特。

如果要使用自己定义 Compare 顺序，可以这样定义：

class myCompare {
  bool operator()(const typename & item1, const typename & item2) const {
    //define your order,
  }
};

例如在priority_queue中实现int的less功能：

class myCompare {
public:
  bool operator()(const int & item1, const int & item2) const {
    return item1 < item2;
  }
};

priority_queue<int> queue1;
priority_queue<int, vector<int>, myCompare> queue2;

完整示例:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class myCompare
{
public:
  bool operator()(const int &item1, const int &item2) const
  {
    return item1 < item2;
  }
};

int main()
{
  priority_queue<int, vector<int>, myCompare> queue2;
  for (int i = 1; i < 100; ++i)
  {
    queue2.emplace(i);
  }
  while (!queue2.empty())
  {
    cout << queue2.top() << ' ';
    queue2.pop();
  }
  cout << '\n';
  return 0;
}

注意如果自己指定了Compare，同时需要指定Container，应为第n个参数自定义之后，前面的n-1个参数都不能缺省，都需要手动指定。

拓展

C++ 标准中提供了用于比较的泛型类，即 greater、 less、equal 等。以 less 为例：

A specialization of std::less for any pointer type yields a strict total order, even if the built-in operator< does not. The strict total order is consistent among specializations of std::less, std::greater, std::less_equal, and std::greater_equal for that pointer type, and is also consistent with the partial order imposed by the corresponding built-in operators (<, >, <= and >=).

这段话说 less 是服从严格全序关系的。

其成员函数为 operations()，所以 less<T>() 可以直接用于对应类的比较中，例如：

sort(arr1, arr1 + n, less<int>());

这里就不用自己编写 cmp 函数了。