CRBTree クラス
このクラスは、赤黒ツリーを作成および利用するためのメソッドを提供します。
構文
template <typename K,
typename V,
class KTraits = CElementTraits<K>,
class VTraits = CElementTraits<V>>
class CRBTree
パラメーター
K
キー要素の型。
V
値要素の型。
KTraits
キー要素をコピーまたは移動するために使用されるコード。 詳細については、「CElementTraits クラス」を参照してください。
VTraits
値要素をコピーまたは移動するために使用されるコード。
メンバー
パブリック typedef
| 名前 | 説明 |
|---|---|
| CRBTree::KINARGTYPE | キーが入力引数として渡されるときに使用される型。 |
| CRBTree::KOUTARGTYPE | キーが出力引数として返される場合に使用される型。 |
| CRBTree::VINARGTYPE | 値が入力引数として渡されるときに使用される型。 |
| CRBTree::VOUTARGTYPE | 値が出力引数として渡されるときに使用される型。 |
パブリック クラス
| 名前 | 説明 |
|---|---|
| CRBTree::CPair クラス | キーと値の要素を含むクラス。 |
パブリック コンストラクター
| 名前 | 説明 |
|---|---|
| CRBTree::~CRBTree | デストラクター。 |
パブリック メソッド
| 名前 | 説明 |
|---|---|
| CRBTree::FindFirstKeyAfter | 次に使用可能なキーを使用する要素の位置を見つけるには、このメソッドを呼び出します。 |
| CRBTree::GetAt | ツリー内の特定の位置にある要素を取得するには、このメソッドを呼び出します。 |
| CRBTree::GetCount | ツリー内の要素の数を取得するには、このメソッドを呼び出します。 |
| CRBTree::GetHeadPosition | ツリーの先頭にある要素の位置の値を取得するには、このメソッドを呼び出します。 |
| CRBTree::GetKeyAt | ツリー内の特定の位置からキーを取得するには、このメソッドを呼び出します。 |
| CRBTree::GetNext | CRBTree オブジェクトに格納されている要素へのポインターを取得し、その位置を次の要素に進めるには、このメソッドを呼び出します。 |
| CRBTree::GetNextAssoc | マップに格納されている要素のキーと値を取得し、その位置を次の要素に進めるには、このメソッドを呼び出します。 |
| CRBTree::GetNextKey | ツリーに格納されている要素のキーを取得し、その位置を次の要素に進めるには、このメソッドを呼び出します。 |
| CRBTree::GetNextValue | ツリーに格納されている要素の値を取得し、その位置を次の要素に進めるには、このメソッドを呼び出します。 |
| CRBTree::GetPrev | CRBTree オブジェクトに格納されている要素へのポインターを取得してから、その位置を前の要素に更新するには、このメソッドを呼び出します。 |
| CRBTree::GetTailPosition | ツリーの末尾にある要素の位置の値を取得するには、このメソッドを呼び出します。 |
| CRBTree::GetValueAt | このメソッドを呼び出すと、CRBTree オブジェクト内の指定した位置に格納されている値を取得できます。 |
| CRBTree::IsEmpty | 空のツリー オブジェクトがないかどうかをテストするには、このメソッドを呼び出します。 |
| CRBTree::RemoveAll | CRBTree オブジェクトからすべての要素を削除するには、このメソッドを呼び出します。 |
| CRBTree::RemoveAt | このメソッドを呼び出すと、CRBTree オブジェクト内の指定した位置にある要素が削除されます。 |
| CRBTree::SetValueAt | このメソッドを呼び出すと、CRBTree オブジェクト内の指定した位置に格納されている値を変更することができます。 |
解説
Red-Black ツリーは、ノードごとに追加の情報を使用して確実に "均衡" を保つようにするバイナリ検索ツリーです。つまり、ツリーの高さが過度に大きくなり、パフォーマンスに影響を与えないようにします。
このテンプレート クラスは、CRBMap と CRBMultiMap によって使用されるように設計されています。 これらの派生クラスを構成するメソッドの大部分は、CRBTree によって提供されます。
さまざまなコレクション クラスとその機能およびパフォーマンス特性の詳細については、「ATL コレクション クラス」を参照してください。
要件
ヘッダー: atlcoll.h
CRBTree::CPair クラス
キーと値の要素を含むクラス。
class CPair : public __POSITION
解説
このクラスは、ツリー構造体に格納されているキーと値の要素にアクセスするために、CRBTree::GetAt、CRBTree::GetNext、および CRBTree::GetPrev メソッドによって使用されます。
メンバーは次のとおりです。
| データ メンバー | 説明 |
|---|---|
m_key |
キー要素を格納するデータ メンバー。 |
m_value |
値要素を格納するデータ メンバー。 |
CRBTree::~CRBTree
デストラクター。
~CRBTree() throw();
解説
割り当てられたすべてのリソースを解放します。 CRBTree:: RemoveAll を呼び出して、すべての要素を削除します。
CRBTree::FindFirstKeyAfter
次に使用可能なキーを使用する要素の位置を見つけるには、このメソッドを呼び出します。
POSITION FindFirstKeyAfter(KINARGTYPE key) const throw();
パラメーター
key
キー値。
戻り値
次に使用可能なキーを使用する要素の位置の値を返します。 要素がこれ以上ない場合は、NULL が返されます。
解説
このメソッドを使用すると、事前に位置の値を計算することなく、ツリーを簡単に走査できます。
CRBTree::GetAt
ツリー内の特定の位置にある要素を取得するには、このメソッドを呼び出します。
CPair* GetAt(POSITION pos) throw();
const CPair* GetAt(POSITION pos) const throw();
void GetAt(POSITION pos, KOUTARGTYPE key, VOUTARGTYPE value) const;
パラメーター
pos
位置を表す値です。
キー
キーを受け取る変数。
value
値を受け取る変数。
戻り値
最初の 2 つのフォームでは、CPair へのポインターを返します。 3 番目のフォームでは、特定の位置のキーと値を取得します。
解説
位置の値は、CRBTree::GetHeadPosition や CRBTree::GetTailPosition などのメソッドの呼び出しで事前に判断できます。
デバッグ ビルドでは、pos が NULL に等しい場合、アサーション エラーが発生します。
CRBTree::GetCount
ツリー内の要素の数を取得するには、このメソッドを呼び出します。
size_t GetCount() const throw();
戻り値
ツリーに格納されている要素の数 (各キーと値のペアは 1 つの要素) を返します。
CRBTree::GetHeadPosition
ツリーの先頭にある要素の位置の値を取得するには、このメソッドを呼び出します。
POSITION GetHeadPosition() const throw();
戻り値
ツリーの先頭にある要素の位置の値を返します。
解説
GetHeadPosition によって返される値は、CRBTree::GetKeyAt や CRBTree::GetNext などのメソッドで使用して、ツリーを走査し、値を取得できます。
CRBTree::GetKeyAt
ツリー内の特定の位置からキーを取得するには、このメソッドを呼び出します。
const K& GetKeyAt(POSITION pos) const throw();
パラメーター
pos
位置を表す値です。
戻り値
ツリー内の位置 pos に格納されているキーを返します。
解説
pos が有効な位置の値でない場合、結果は予測できません。 デバッグ ビルドでは、pos が NULL に等しい場合、アサーション エラーが発生します。
CRBTree::GetNext
CRBTree オブジェクトに格納されている要素へのポインターを取得し、その位置を次の要素に進めるには、このメソッドを呼び出します。
const CPair* GetNext(POSITION& pos) const throw();
CPair* GetNext(POSITION& pos) throw();
パラメーター
pos
CRBTree::GetHeadPosition や CRBTree::FindFirstKeyAfter などのメソッドの前の呼び出しによって返される位置カウンター。
戻り値
ツリー内の次の CPair 値へのポインターを返します。
解説
pos 位置カウンターは、各呼び出しの後に更新されます。 取得された要素がツリーの最後のものである場合、pos は NULL に設定されます。
CRBTree::GetNextAssoc
マップに格納されている要素のキーと値を取得し、その位置を次の要素に進めるには、このメソッドを呼び出します。
void GetNextAssoc(
POSITION& pos,
KOUTARGTYPE key,
VOUTARGTYPE value) const;
パラメーター
pos
CRBTree::GetHeadPosition や CRBTree::FindFirstKeyAfter などのメソッドの前の呼び出しによって返される位置カウンター。
キー
ツリーのキーの型を指定するテンプレート パラメーター。
value
ツリーの値の型を指定するテンプレート パラメーター。
解説
pos 位置カウンターは、各呼び出しの後に更新されます。 取得された要素がツリーの最後のものである場合、pos は NULL に設定されます。
CRBTree::GetNextKey
ツリーに格納されている要素のキーを取得し、その位置を次の要素に進めるには、このメソッドを呼び出します。
const K& GetNextKey(POSITION& pos) const throw();
パラメーター
pos
CRBTree::GetHeadPosition や CRBTree::FindFirstKeyAfter などのメソッドの前の呼び出しによって返される位置カウンター。
戻り値
ツリー内の次のキーへの参照を返します。
解説
現在の位置カウンター pos を更新します。ツリーにエントリがこれ以上ない場合、位置カウンターは NULL に設定されます。
CRBTree::GetNextValue
ツリーに格納されている要素の値を取得し、その位置を次の要素に進めるには、このメソッドを呼び出します。
const V& GetNextValue(POSITION& pos) const throw();
V& GetNextValue(POSITION& pos) throw();
パラメーター
pos
CRBTree::GetHeadPosition や CRBTree::FindFirstKeyAfter などのメソッドの前の呼び出しによって返される位置カウンター。
戻り値
ツリー内の次の値への参照を返します。
解説
現在の位置カウンター pos を更新します。ツリーにエントリがこれ以上ない場合、位置カウンターは NULL に設定されます。
CRBTree::GetPrev
CRBTree オブジェクトに格納されている要素へのポインターを取得してから、その位置を前の要素に更新するには、このメソッドを呼び出します。
const CPair* GetPrev(POSITION& pos) const throw();
CPair* GetPrev(POSITION& pos) throw();
パラメーター
pos
CRBTree::GetHeadPosition や CRBTree::FindFirstKeyAfter などのメソッドの前の呼び出しによって返される位置カウンター。
戻り値
ツリーに格納されている前の CPair 値へのポインターを返します。
解説
現在の位置カウンター pos を更新します。ツリーにエントリがこれ以上ない場合、位置カウンターは NULL に設定されます。
CRBTree::GetTailPosition
ツリーの末尾にある要素の位置の値を取得するには、このメソッドを呼び出します。
POSITION GetTailPosition() const throw();
戻り値
ツリーの末尾にある要素の位置の値を返します。
解説
GetTailPosition によって返される値は、CRBTree::GetKeyAt や CRBTree::GetPrev などのメソッドで使用して、ツリーを走査し、値を取得できます。
CRBTree::GetValueAt
このメソッドを呼び出すと、CRBTree オブジェクト内の指定した位置に格納されている値を取得できます。
const V& GetValueAt(POSITION pos) const throw();
V& GetValueAt(POSITION pos) throw();
パラメーター
pos
CRBTree::GetHeadPosition や CRBTree::FindFirstKeyAfter などのメソッドの前の呼び出しによって返される位置カウンター。
戻り値
CRBTree オブジェクト内の特定の位置に格納されている値への参照を返します。
CRBTree::IsEmpty
空のツリー オブジェクトがないかどうかをテストするには、このメソッドを呼び出します。
bool IsEmpty() const throw();
戻り値
ツリーが空の場合は TRUE、それ以外の場合は FALSE を返します。
CRBTree::KINARGTYPE
キーが入力引数として渡されるときに使用される型。
typedef KTraits::INARGTYPE KINARGTYPE;
CRBTree::KOUTARGTYPE
キーが出力引数として返される場合に使用される型。
typedef KTraits::OUTARGTYPE KOUTARGTYPE;
CRBTree::RemoveAll
CRBTree オブジェクトからすべての要素を削除するには、このメソッドを呼び出します。
void RemoveAll() throw();
解説
CRBTree オブジェクトをクリアします。これにより、要素の格納に使用されるメモリが解放されます。
CRBTree::RemoveAt
このメソッドを呼び出すと、CRBTree オブジェクト内の指定した位置にある要素が削除されます。
void RemoveAt(POSITION pos) throw();
パラメーター
pos
CRBTree::GetHeadPosition や CRBTree::FindFirstKeyAfter などのメソッドの前の呼び出しによって返される位置カウンター。
解説
指定された位置に格納されているキーと値のペアを削除します。 要素を格納するのに使用されるメモリが解放されます。 pos によって参照される POSITION が無効になります。ツリー内の他の要素の POSITION が有効なままでも、それらは必ずしも同じ順序で保持されるわけではありません。
CRBTree::SetValueAt
このメソッドを呼び出すと、CRBTree オブジェクト内の指定した位置に格納されている値を変更することができます。
void SetValueAt(POSITION pos, VINARGTYPE value);
パラメーター
pos
CRBTree::GetHeadPosition や CRBTree::FindFirstKeyAfter などのメソッドの前の呼び出しによって返される位置カウンター。
value
CRBTree オブジェクトに追加する値。
解説
CRBTree オブジェクト内の特定の位置に格納されている値の要素を変更します。
CRBTree::VINARGTYPE
値が入力引数として渡されるときに使用される型。
typedef VTraits::INARGTYPE VINARGTYPE;
CRBTree::VOUTARGTYPE
値が出力引数として渡されるときに使用される型。
typedef VTraits::OUTARGTYPE VOUTARGTYPE;