3

STLのstd::map実装方法を調べていました。Red Black Trees を使用して実装されていることは知っていました。そのため、実装がどれほど効率的であるかを知るために、STL で Red Black Trees がどのように実装されているかを知りたいと思っていました。

std::map含まれていstl_tree.hます。これは、Red Black Tree が実装されている場所です。

すべての関数 (挿入が行われる場所) は、挿入を抽象化し、_Rb_tree_insert_and_rebalance関数を呼び出します。しかし、私はこれの実装を見つけることができませんでした。

それが実装されているアイデアはありますか？

4

1 に答える 1

8

完全に実装固有ですが、つまりlibstdc++、実現はオープンソースであるため、ソースファイルでこの関数を検索できます。このgcc-4.8関数は in file にありますlibstdc++-v3/src/c++98/tree.cc。たとえば、ここで検索できます: github gcc sources

于 2013-05-31T09:09:31.347 に答える