我想知道为什么STL的地图是基于rb树的？我的意思是,基于散列的映射似乎在插入/删除甚至获取值方面更有效.有什么具体考虑吗？
jal*_*alf 12
STL 最初选择了两者.它有一个哈希表和基于树的地图.
然而,当它被采用到标准中时,许多部分被剥离以简化任务(更容易让委员会讨论包括一个较小的库,并且在实际指定其行为方面需要较少的工作).
因此跳过了哈希表.
但是,这两种数据结构都有其优点.特别是,二叉树允许对地图的内容进行排序(您可以按排序顺序迭代地图的内容,或者您可以要求所有小于特定元素的元素),我只能猜测这个属性被认为比哈希映射的性能优势更重要.
但是,在C++ 11 std::unordered_map中添加了一个长丢失的哈希表.最初的遗漏仅仅是由于时间压力,而且很可能是委员会政治(保持图书馆小,以尽量减少对它的抵制)