0

有问题在 stdmap中使用 char 作为键，建议使用自定义比较函数/函子：

struct cmp_str
{
   bool operator()(char const *a, char const *b)
   {
      return std::strcmp(a, b) < 0;
   }
};

map<char *, int, cmp_str> BlahBlah;

这允许 map 检测 key A 是否小于key B。但是例如 map<>::find()如果未找到元素则返回end，如果找到则返回它的迭代器。所以 map 知道等价，而不仅仅是小于。如何？

4

3 回答 3

7

两个键的相等条件aand bare that a<bandb<a都是假的。map 本身通常实现为平衡二叉树*，因此使用小于比较从根节点遍历 map 直到找到匹配元素。搜索 keyk时，将使用小于比较，直到找到比较为假的第一个元素。如果逆比较也是假的，k已经找到了。否则，k不在地图中。该地图仅使用小于比较来达到此目的。

另请注意，它std::set使用完全相同的机制，唯一的区别是每个元素都是它自己的键。

*严格来说，C++ 标准没有指定它std::map是平衡二叉树，但它对插入和查找等操作的复杂性限制意味着实现选择了红黑树等结构。

于 2012-09-08T14:43:31.760 回答
3

等价/operator==可以表示为 的函数operator<：

bool operator==(T left, T right) {
  return !(left < right) && !(right < left);
}
于 2012-09-08T14:44:33.830 回答
3

这是因为 map 的比较器必须实现严格的弱排序，例如<.

这种关系的数学属性之一是反对称，它表明对于任何xand y，然后not (x < y)andnot (y < x)意味着x == y。

因此，在找到第一个不比较小于您正在搜索的键的元素后，实现只是检查该元素是否比较大，并且它既不小也不大于，那么它必须相等。

于 2012-09-08T15:00:41.313 回答