STL Map实现了_Rb_tree_insert_and_rebalance的地图？

2013-05-31 36 views 1 likes

我正在查看STL std::map的实现方式。我知道它是用红黑树实现的。所以，我只是很好奇知道如何在STL中实现红黑树，因为知道实现的效率如何。STL Map实现了_Rb_tree_insert_and_rebalance的地图？

std::map包括stl_tree.h。这是实施红黑树的地方。

所有功能（插入发生）抽象插入并调用_Rb_tree_insert_and_rebalance函数。但是我找不到这个的实现。

任何想法，它的实施？

如果通过STL指的是C++标准库（由'std'命名空间建议），那么它完全依赖于实现。所以你应该明确你的意思是哪个标准库的实现。如果你真的指的是STL，那么它就没有'std :: map'（只是'map'）。 – juanchopanza

回答

这是完全实现特定的，但是，我认为你的意思是libstdc++，所以，因为实现是开源的 - 你可以在源文件中搜索这个函数。在gcc-4.8这个函数在文件libstdc++-v3/src/c++98/tree.cc。例如，您可以在这里搜索：github gcc sources

2013-05-31 09:09:31 ForEveR

谢谢。我正在浏览安装目录中提供的gcc includes，但无法找到它。 –

只是一个简单的提示：在形式上，它不是实现定义的，因为语言定义说“实现定义”意味着符合实现必须记录它的功能。但是，这是具体实施。 –

@PeteBecker谢谢，更新。 – ForEveR