STLはどのようにコンテナの終わりを知っていますか？

Question

私は、標準ではSTLコンテナを実装する必要があるとは言いませんが、むしろSTLコンテナがそれぞれの要件を満たすことを要求しています。

しかし、STLオーダーコンテナは、通常、red–black treesとして実装されていることが広く知られています。

std::setまたはstd::mapの要素を、それぞれのイテレータを使用して、またはC++ 11以降では巡回ループを使用して繰り返し処理できます。

しかし私が困惑しているのは、STLの注文したコンテナが「終了」を "知っている"ということです。または、別の言い方をすると、それらはツリーとして実装されているので、 コンテナの最後がどのように実装されているのか、それとも が実装できますか？

私は標準が§23.2.1/ C一般的なコンテナの要件を規定することを知っている（強調鉱山）：

）は（開始 コンテナ内の最初の要素を参照する反復子を返します。 end（）は、コンテナの終わりの値 であるイテレータを返します。コンテナが空の場合、begin（）== end（）;

OK、連続したコンテナの場合、これは簡単ですが、この「過去の終わり」をツリーでどのように実現できるのでしょうか？

Answer 1

ユーザーがend()を得ることができますので、終了をセンチネルノードのいくつかの種類を持っている容器の中に何かを挿入し、イテレータをデクリメントするには、この必要性のような「リストのような」コンテナのすべて、および減算end()必見ポイントその挿入された要素に追加します。私の理解は、いくつかの実装がこれに動的に割り当て、いくつかは動的なセンチネルノードをコンテナ自体の中に置くことです。

Answer 2

Visual Studio 2013 STLでmapコンテナの実装を検査しましたが、ここにはendが実装されています。 mapが構築されると、RBツリーの先頭要素が割り当てられ、この要素はコンテナの終わりと宣言される。

有効なイテレータを使用してコンテナをトラバースすると、operator++とoperator--は単にhead要素をスキップします。ツリーの最後の要素に到達し、イテレータをインクリメントすると、それは上向きに移動し（右のサブツリーを探して）、最終的にツリーの先頭に到達します。これはendです。