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
位置を表す値です。

key
キーを受け取る変数。

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 などのメソッドの前の呼び出しによって返される位置カウンター。

key
ツリーのキーの型を指定するテンプレート パラメーター。

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;

関連項目

クラスの概要