STRING（到整数或任何其他值）的映射如何在内部存储？它们是如何排序/平衡的？
我知道STL中的Map容器内部是一棵红黑树，是一棵自平衡树。
在Map中，最低的元素位于树的顶部。因此，对于整数到“任何东西”的映射，最小的整数将位于顶部，依此类推。它总是自我平衡。这就是为什么我们在搜索整数及其关联值时会得到 log n 复杂度。
但是，如果字符串映射到“任何东西”，它如何平衡和排序自身（如果可以的话）？哪根绳子位于树的顶部？它与 ASCII 值匹配吗？
这可能很蹩脚，但我需要知道这一点，因为我必须确保我的代码中遵循 log n 的复杂性。
I know that the Map container in STL is internally a Red-Black Tree, which is a self-balancing tree.
In Map, the lowest element is at the top of the tree. So, for a map of integer to 'anything', the lowest integer will be at the top and so on. It always balances itself. That's why we get a log n complexity while searching for an integer and its associated value.
But in case of map of string to 'anything', how does it balances and orders itself, if it does? Which string would be at the top of the tree? Does it matches the ASCII values or something?
This might be lame, but I need to know this as I have to ensure that I am adhering to the complexity of log n in my code.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
不，最小的元素位于最左边的节点，您可以通过跟随左子指针直到它为空来到达该节点。对于字符串，最小元素是始终与您插入到映射中的所有其他字符串进行比较“小于”的元素。默认比较是按字典顺序比较。
平衡过程照常，通过一堆指针交换进行。无论如何，从根到任何叶子的路径都保证长度为 θ(lg n)。
（这是假设
map的原始 STL 实现，尽管符合标准的 C++ 库可能使用不同的结构，但它仍然很常见。）No, the least element is at the left-most node, the one you reach by following the left child pointer until it's null. In the case of strings, the least element is the one that always compared "less than" all the other strings you've inserted into the map. The default comparison is lexicographic.
The balancing proceeds as usual, by a bunch of pointer swaps. The path from the root to any leaf is guaranteed to have length Θ(lg n), no matter what.
(This is assuming the original STL implementation of
map, which is still common, though a conforming C++ library might use a different structure.)