STL地图如何知道,该地图包含给定元素？

Question

问题在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检测键A是否小于键B.但是例如 map <> :: find()如果找不到元素则返回end,如果找到则返回iterator.因此,地图知道等价,而不仅仅是低于.怎么样？

Answer 1

对于两个键的平等条件a和b是a<b和b<a都是假的.地图本身通常实现为平衡二叉树^*,因此使用小于比较来从根节点遍历地图,直到找到匹配元素.在搜索密钥时k,使用小于比较,直到找到比较为假的第一个元素.如果反比较也是假的,k则已找到.否则,k不在地图中.地图仅使用与此目的相比较小的比较.

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

^*严格地说,C++标准没有指定它std::map是一个平衡的二叉树,但它对插入和查找等操作的复杂性限制意味着实现选择了诸如红黑树之类的结构.