为什么我们没有 map 的 hash 和 pred 仿函数？

Question

在 unordered_map 的情况下，我们在使用 user-defined 键时定义 hash 和 pred 函子。

地图的模板语法如下：

template < class Key,                                     // map::key_type
       class T,                                           // map::mapped_type
       class Compare = less<Key>,                         // map::key_compare
       class Alloc = allocator<pair<const Key,T> >       // map::allocator_type
       > class map;

在 map 的情况下，没有 hash 和 pred 函子选项。在 map 的情况下我们永远不会发生碰撞吗？如果发生冲突，那么为什么我们不像 unordered_map 那样使用 hash 和 pred 函子？我在这里遗漏了什么吗？

Answer 1

std::map 不是散列 table 因此不使用散列函数。相反，它需要 operator< 来对地图中包含的值进行排序。

Answer 2

std::map 和 std::unordered_map 是两种不同类型的容器，都提供键值对映射。他们的做法完全不同。

std::map 使用树结构来实现。通常这是一个 RBTree，但任何可以保证最坏情况 O(logN) 操作的树都可以工作。这意味着它只需要有一个用于键类型的比较运算符，因为您可以获得总排序并使用实现严格弱排序的比较器检查是否相等。这意味着您永远不会发生哈希冲突，因为您没有使用哈希。

std::unordered_map 基于散列 table 实现。由于它对密钥进行哈希处理，因此您需要一个哈希运算符。您还需要一个比较运算符，因为两个值可能散列为相同的值（散列冲突）。如果没有比较运算符，您将无法判断重复散列是否真的是重复项。

为什么我们没有 map 的 hash 和 pred 仿函数？

Why do we don't have hash and pred functors for a map?

c++

unordered-map

ordered-map