Daily C/C++ 函数对象与容器

今天来讲两个比较重要的函数对象less和hash

首先对于函数对象，理解成重载了operator()的一个类型即可

对于less，就是一个二元函数对象，用来执行任意类型元素值的比较，并且缺省行为是进行小于的比较操作

在cppreference中，有提到在特化为指针类型时候要满足全序关系，这个大家可以去自己查看

从C++14起，默认的特化类型就是void

可能的实现如下

constexpr bool operator()(const T &lhs, const T &rhs) const 
{
    return lhs < rhs; // 假定实现使用平坦地址空间
}

再给出现代C++30讲中的一个实现，这个我觉得比较容易理解

template <class T>
struct less
  : binary_function<T, T, bool> {
  bool operator()(const T& x,
                  const T& y) const
  {
    return x < y;
  }
};

同样的，与之相对的还有其他的用以比较的二元函数，比如greater,less_equal等

而对于hash来说，就是用来计算某一个元素的hash value

返回的是size_t类型的哈希值

template <class T> struct hash;

template <>
struct hash<int>
  : public unary_function<int, size_t> {
  size_t operator()(int v) const
    noexcept
  {
    return static_cast<size_t>(v);
  }
};

其实我们并不是很关系这个函数对象本身的值，我们更关心的是他特化的类型，因为相同类型的不同的函数对象其实是可以被看作是相同的

所以我们一般是通过这种方式来使用函数对象的

result = hash<int>{}(val);
result = less<int>{}(lhs, rhs);

实例化出来的对象对我们来说只是用于调用函数

我们也可以实现自己的函数对象，这里给出cppreference的一个例子

struct MyHash
{
    std::size_t operator()(S const& s) const 
    {
        std::size_t h1 = std::hash<std::string>{}(s.first_name);
        std::size_t h2 = std::hash<std::string>{}(s.last_name);
        return h1 ^ (h2 << 1); // 或使用 boost::hash_combine 
    }
};

对于我们平常使用的priority_queue的默认比较对象就是less，所以我们可以通过传入greater来改变他的优先级

即priority_queue<int, vector<int>, greater<int>> pq

那么对于平常有使用到比较函数对象的容器，就是有序的关联容器了，比如map, set, multimap, multiset

而对于哈希函数对象，就是无序的关联容器，比如unordered_map, unordered_set, unordered_multimap, unordered_multiset

并且关联容器的键是需要满足弱序关系的，即weak ordering，即反自反，反对称，传递，以及不可比的传递性。这里大家只要考虑<的表现就好

而对于这个的具体要求，参见这里链接，这里讲述了比较器Compare的具体要求

最后一个小问题，就是为什么C++中容器有这么多相似的地方，为什么不继承一个通用的基类？

因为C++的容器大多使用的是值语义，把接口抽象出来用指针或引用还不方便。同时各个容器的模板参数也不相同，比如同为关联容器的map和hash_map，一个需要比较函数对象，一个需要哈希函数对象

Daily C/C++ 函数对象与容器

Daily C/C++ 函数对象与容器

文章评论