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
,一个需要比较函数对象,一个需要哈希函数对象
文章评论