STL地图如何知道，该地图包含给定的元素？ [英] How does STL map know, that map contains a given element?

问题描述

有问题的在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; 
  

这允许地图检测密钥A是否<<>小于密钥B.但是，例如 map<> :: find（）返回结束如果没有找到元素，并且如果找到它，则迭代它。所以地图知道等价，不仅少于。如何？

解决方案

两个密钥的等价条件 a 和 b 是 a< b 和 b 都是假的。地图本身通常被实现为一个平衡二叉树 * ，所以比较比较用于从根节点遍历地图直到找到匹配元素。当搜索密钥 k 时，使用比比较少，直到找到比较为false的第一个元素。如果逆比较也是假的，则已经找到 k 。否则， k 不在地图上。该地图仅使用与此目的的比较。

另请注意， std :: set 正好使用同样的机制，唯一的区别是每个元素都是自己的密钥。严格来说，C ++标准没有指定

code> std :: map 是一个平衡的二叉树，但它对诸如插入和查找等操作的复杂性约束意味着实现选择结构，如红黑树。 / p>

In question Using char as key in stdmap there is advised to use custom compare function/functor:

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

map<char *, int, cmp_str> BlahBlah;

This allows map to detect if key A is less than key B. But for example map<>::find() returns end if element is not found, and iterator to it if it is found. So map knows about equivalence, not only less-than. How?

解决方案

The equality condition for two keys a and b are that a<b and b<a are both false. The map itself is commonly implemented as a balanced binary tree^*, so the less-than comparison is used to traverse the map from the root node until the matching element is found. When searching for a key k, less-than comparison is used until the first element for which the comparison is false is found. If the inverse comparison is also false, k has been found. Otherwise, k is not in the map. The map only uses the less-than comparison to this purpose.

Note also that std::set uses exactly the same mechanism, the only difference being that each element is it's own key.

^* strictly speaking, the C++ standard does not specify that std::map be a balanced binary tree, but the complexity constraints it places on operations such as insertion and look-up mean that implementations chose structures such as red-black tree.

这篇关于STL地图如何知道，该地图包含给定的元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！