c++ - set データ構造の end() イテレータは何を返すはずですか?

Question

これは確かにハードウェアのプログラミングですが、コードを求めているのではなく、イテレータ関数 end() を呼び出したときに何が返されると思いますか? 最大値/右端のセット ノード?

begin() については、最初に入力したものなので、ルートのイテレータを取得するだけだと思います。

また、この Set Data Structure イテレータの operator++ については、ルートから始まるツリーのトラバーサルに応じてイテレータをインクリメントするだけですか?

助けてくれてありがとう。

Answer 1

伝統的end()に、構造体の終わりの 1 つ後ろを返します。そうしないと、構造全体をcurrent != end()ループでトラバースできなくなります。これは std::vector の場合ですが、反復子はより複雑なデータ構造ではより複雑になります。ただし、反復可能な構造の最後の要素を指す反復子をend()使用することで、常に到達できるはずです。operator++

要素を逆参照することはできませんend()。これは通常、未定義の動作です。

Answer 2

データ構造を自分で実装している場合は、何end()を意味するかを決めることができます。正しい型の反復子であり、セット内の最後の要素を超えて通常の反復子をインクリメントした結果と一致する値である必要があります。セットへの反復子は双方向であるため、返される特定の値は、セット内の前の値に移動できる必要があります。

一般的なアプローチは、データ構造の最初と最後の要素へのポインターを保持するコンテナー内の監視ノードを使用し、そのノード (適切な値を保持していない) へのend()イテレーターをイテレーターとして使用することです。

の場合begin()、ツリーのルートの値ではなく最小値を表すため、ツリーの一番左のノードになります。