Spa*_*dan 4 c++ algorithm implementation stl map
我想知道,如何MAP在C++中使用,而不是在内部实现的MultiMap简单Map.
我最能想到的是:
对于整数映射:A Balanced Binary Search Tree could be used .
对于字符串映射:Compressed Trie or something similar could be used .
我真的很好奇,它是如何在STL Map中真正实现的.是否使用了一些散列函数,或者它是否与此完全不同.
在有序的容器,包括std::map被实现为平衡二叉树(通常RB树,但其他任何平衡树将符合要求).
对于这类问题,您需要的最重要的信息是容器中每个操作的复杂性要求,这是标准要求的.这也是最重要的答案,也就是说,只要满足复杂性要求,实际实施并不重要.