c++ - std::map イテレータはどのように機能しますか?

Question

C++ STL クラス std::map は、バイナリ ツリーを使用して O(log(n)) ルックアップを実装します。しかし、ツリーでは、反復子がどのように機能するかはすぐにはわかりません。++演算子は、ツリー構造で実際に何を意味しますか? 「次の要素」の概念は、配列では明らかな実装がありますが、私にとっては、ツリーではそれほど明白ではありません。ツリー反復子をどのように実装しますか?

Answer 1

順不同のトラバーサル (おそらく他のものでも機能します) の場合、ノードに親ポインターがある場合は、非再帰的なトラバーサルを実行できます。イテレータに 2 つのポインタを格納するだけでよいはずです。現在の場所を示す必要があり、おそらく (私は現在調査を行っていません) 把握できるように「前の」ポインタのようなものが必要になるでしょう。現在の移動方向 (つまり、左のサブツリーに移動する必要があるのか​​、それともそこから戻ってきたのか)。

ノードに入ったばかりの場合、 「前」はおそらく「親」のようなものになります。左のサブツリーから戻る場合は「左」、右のサブツリーから戻る場合は「右」、返された最後のノードが自分のものである場合は「自己」。

Answer 2

現在の要素よりも小さくなく、現在の要素でもないマップ内のすべての要素のセットを検討してください。「次の要素」は、そのセット内の他のすべての要素よりも少ない要素のセットからの要素です。

マップを使用するには、キーが必要です。そして、そのキーは「より小さい」操作を実装する必要があります。これにより、検索、追加、削除、増分、および減分操作が効率的になるように、マップが形成される方法が決まります。

通常、マップは何らかのツリーを内部的に使用します。