TSet

TSets は、順序が重要ではない(通常)ユニークなエレメントを格納する高速のコンテナ クラスです。

TSetTMap および TMultiMap と似ています。ただし、重要な相違点があります。データ値を独立したキーに関連づけるのではなく、TSet はエレメントを評価するオーバーライド可能な関数で要素そのものをキーとして使います。TSet は要素を迅速に追加、検索、削除します。デフォルトで、TSet は重複するキーをサポートしませんが、このビヘイビアはテンプレート パラメータでアクティベートすることができます。

TSet

TSet は、順序が重要ではないユニークな要素を格納する高速のコンテナ クラスです。ほとんどのユースケースで、必要とされるパラメータは要素型だけです。ただし、TSet は様々なテンプレート パラメータを使ってビヘイビアの変更や多目的への設定が可能です。セット内で複数のキーが同じ値を持つことを可能にしたり、ハッシング機能を付けるように、DefaultKeyFuncs から派生した構造体を指定することができます。最後に、他のコンテナ クラスと同様に、データ ストレージに対してカスタム アロケータを指定することができます。

TArray と同様に、TSet も均一な型です。つまり要素はすべてまったく同じ型です。TSet も value 型で、通常のコピー、アサイメント、デストラクタ操作をサポートします。エレメントの強力なオーナーシップを持つのでマップが破棄されると破棄されます。Key 型はまた value 型でなければなりません。

TSet`はハッシュを使います。つまり、KeyFuncs テンプレート パラメータが与えられている場合、エレメントからキーを判断する方法、2 つのキーの等価の比較方法、キーのハッシュ方法、キーの複製を許可するかどうかを指示します。デフォルトで、等価比較には`operator==、ハッシングには非メンバ関数 GetTypeHash を使って、リファレンスをそのキーに戻します。デフォルトで、set はキーの複製を許可しません。Key 型がこれらの関数をサポートしている場合、カスタム仕様の KeyFuncs を与えなくてもセット キーとして使用できます。カスタム仕様の KeyFuncs を書くには、DefaultKeyFuncs 構造体を拡張します。

最後に、TSet は、メモリの割り当て動作を制御するオプションのアロケータを受け取ります。標準の Unreal Engine 4 (UE4) のアロケータ (FHeapAllocatorTInlineAllocator など) は TSet のアロケータとしては使用できません。代わりに、TSet が使用すべきハッシュ バケット数や、エレメント格納に使う標準 UE4 アロケータを定義します。詳細は TSetAllocator をご覧ください。

TArray とは異なり、メモリ内における TSet 要素の相対的順序は信頼できません (安定していません)。要素を繰り返し処理すると、要素を追加した順序とは異なる順序で要素が返される可能性があります。また、要素がメモリ内で隣り合うように配置されない可能性もあります。マップのバッキング データ構造はスパース行列です。セットのバッキング データ構造は、要素間のギャップを効果的にサポートするスパース配列です。セットから要素が削除されると、スパース行列にギャップが発生します。新しい要素を配列に追加することで、そのギャップを埋めることができます。しかし、TSet ではギャップを埋めるために要素をシャッフルしませんが、セット要素へのポインタは引き続き無効化されている場合があります。ストレージがいっぱいのときに新しい要素を追加する場合、ストレージ全体が再割り当てされることがあるからです。

セットの作成と追加

TSet は次のように作成できます。

    TSet<FString> FruitSet;

これにより、空の TSet が作成され、これに FString データが保持されます。TSetoperator== と直接要素を比較し、GetTypeHash を使ってそれらをハッシュし、標準のヒープ アロケータを使用します。この時点で、メモリは割り当てられません。

セットをエントリするには、Add 関数でキー (要素) を与えるのが標準的な方法です。

    FruitSet.Add(TEXT("Banana"));
    FruitSet.Add(TEXT("Grapefruit"));
    FruitSet.Add(TEXT("Pineapple"));
    // FruitSet == [ "Banana", "Grapefruit", "Pineapple" ]

ここで要素は挿入順にリストされていますが、この順番がメモリ内の実際の順番である保証はありません。新しいセットの場合、挿入順である可能性が高いですが、挿入や削除が多数行われる場合は、新しい要素が最後に表示される可能性はいっそう低くなります

このセットはデフォルトのアロケータを使用したので、キーがユニークであることが保証されます。以下に、重複するキーを追加しようとした結果を示します。

    FruitSet.Add(TEXT("Pear"));
    FruitSet.Add(TEXT("Banana"));
    // FruitSet == [ "Banana", "Grapefruit", "Pineapple", "Pear" ]
    // 注: バナナは 1 つのみエントリします。

今、セットにはエレメントが 4 つ含まれています。"Pear" によって数が 3 から 4 になりましたが、新規の "Banana" は前に入力された "Banana" に置き換えられたのでエレメント数は変わりません。

セットへの挿入時に一時要素が作成されるのを避けるために、TArray と同様に、Add の代わりに Emplace を使用することができます。

    FruitSet.Emplace(TEXT("Orange"));
    // FruitSet == [ "Banana", "Grapefruit", "Pineapple", "Pear", "Orange" ]

ここでは引数が key 型のコンストラクタに直接渡されています。一時的な Fstring が作成されないようにするためです。TArray とは異なり、単一の引数付きコンストラクタでのみエレメントのセットへの配置が可能です。

Append 関数を使って、別のセットからすべてのエレメントを挿入してマージすることも可能です。

    TSet<FString> FruitSet2;
    FruitSet2.Emplace(TEXT("Kiwi"));
    FruitSet2.Emplace(TEXT("Melon"));
    FruitSet2.Emplace(TEXT("Mango"));
    FruitSet2.Emplace(TEXT("Orange"));
    FruitSet.Append(FruitSet2);
    // FruitSet == [ "Banana", "Grapefruit", "Pineapple", "Pear", "Orange", "Kiwi", "Melon", "Mango" ]

上記の例では、結果のマップは Add または Emplace を使用して FruitMap2 の各要素を個別に追加します。ソース セットからの複製キーは、ターゲットでカウンターパートを置き換えます。

UPROPERTY TSets の編集

TSetUPROPERTY マクロと「編集可能」なキーワード (EditAnywhere, EditDefaultsOnly, or EditInstanceOnly) のいずれかでマークすると、エディタ内で要素の追加と編集 ができます。

    UPROPERTY(Category = SetExample, EditAnywhere)
    TSet<FString> FruitSet;

イタレーション

TSets のイタレーションは TArrays と似ています。C++ の ranged-for 機能を使うことができます。

    for (auto& Elem :FruitSet)
    {
        FPlatformMisc::LocalPrint(
            *FString::Printf(
                TEXT(" \"%s\"\n"),
                *Elem
            )
        );
    }
    // Output:
    //  "Banana"
    //  "Grapefruit"
    //  "Pineapple"
    //  "Pear"
    //  "Orange"
    //  "Kiwi"
    //  "Melon"
    //  "Mango"

CreateIterator および CreateConstIterators 関数を使用してイタレータを作成することもできます。CreateIterator は読み取り/書き込みアクセスができるイタレータを返しますが、CreateConstIterator は読み取り専用イタレータを返します。いずれの場合も、それらのイタレータの Key および Value 関数を使用して、要素を調査できます。イタレータを使用して例の「フルーツ」セットのコンテンツを出力すると、次のようになります。

    for (auto It = FruitSet.CreateConstIterator(); It; ++It)
    {
        FPlatformMisc::LocalPrint(
            *FString::Printf(
                TEXT("(%s)\n"),
                *It
            )
        );
    }

クエリ

セット内の現在の要素数を確認するには、Num 関数を呼び出します。

    int32 Count = FruitSet.Num();
    // Count == 8

セットに特定の要素が含まれているかどうかを判断するには、次のように Contains 関数を呼び出します。

    bool bHasBanana = FruitSet.Contains(TEXT("Banana"));
    bool bHasLemon = FruitSet.Contains(TEXT("Lemon"));
    // bHasBanana == true
    // bHasLemon == false

FSetElementId 構造体を使って、セット内でキーのインデックスの検索ができます。operator[] をそのインデックスを使って要素を取り出すことができます。Non-const セットで operator[] を呼び出すと non-const リファレンスが返され、const セット上で呼び出すと const リファレンスを返します。

    FSetElementId BananaIndex = FruitSet.Index(TEXT("Banana"));
    // BananaIndex の値は 0 から (FruitSet.Num() - 1) の間です
    FPlatformMisc::LocalPrint(
        *FString::Printf(
            TEXT(" \"%s\"\n"),
            *FruitSet[BananaIndex]
        )
    );
    // "Banana" をプリントします

    FSetElementId LemonIndex = FruitSet.Index(TEXT("Lemon"));
    // LemonIndex は INDEX_NONE (-1) です
    FPlatformMisc::LocalPrint(
        *FString::Printf(
            TEXT(" \"%s\"\n"),
            *FruitSet[LemonIndex]
        )
    ); // アサートします!

セットにキーが含まれているかどうか不明な場合は、Contains 関数で確認してから operator[] を使用します。しかし、この方法は最適ではありません。取得を正常に行うには、同じキーに対して 2 回の検索を行う必要があるからです。Find 関数は、その 2 つの動作を 1 回の検索にまとめたものです。Find は、セットにキーが含まれる場合、その要素の値へのポインタを返し、キーが含まれない場合は null ポインタを返します。定数セットで Find を呼び出すと、返されるポインタも定数になります。

    FString* PtrBanana = FruitSet.Find(TEXT("Banana"));
    FString* PtrLemon = FruitSet.Find(TEXT("Lemon"));
    // *PtrBanana == "Banana"
    //  PtrLemon == nullptr

Array 関数は TSet のすべてのエレメントのコピーがエントリされた TArray を返します。渡された配列は設定前は空の状態なので、エレメント数は常にセット内のエレメント数と等しい結果になります。

    TArray<FString> FruitArray = FruitSet.Array();
    // FruitArray == [ "Banana","Grapefruit","Pineapple","Pear","Orange","Kiwi","Melon","Mango" ] (順序は変更する場合があります)

削除

エレメントは Remove 関数を使ってインデックスで削除することができます。ただしこれは、エレメントをイタレーション中以外は望ましくありません。Remove 関数は削除したエレメント数を返します。与えられたキーがセットに含まれていないと 0 になります。TSet がキーの複製をサポートしている場合、Remove は入力パラメータと一致するすべてのキーを削除します。

    FruitSet.Remove(0);
    // FruitSet == [ "Grapefruit","Pineapple","Pear","Orange","Kiwi","Melon","Mango" ]

要素を削除すると、データ構造に穴が残る場合があります。これは、Visual Studio のウォッチ ウィンドウでセットを視覚化して確認できますが、ここでは分かりやすくするために省略しています。

    int32 RemovedAmountPineapple = FruitSet.Remove(TEXT("Pineapple"));
    // RemovedAmountPineapple == 1
    // FruitSet == [ "Grapefruit","Pear","Orange","Kiwi","Melon","Mango" ]
    FString RemovedAmountLemon = FruitSet.Remove(TEXT("Lemon"));
    // RemovedAmountLemon == 0

最後に、Empty または Reset 関数を使用して、セットからすべての要素を削除できます。

    TSet<FString> FruitSetCopy = FruitSet;
    // FruitSetCopy == [ "Grapefruit","Pear","Orange","Kiwi","Melon","Mango" ]

    FruitSetCopy.Empty();
    // FruitSetCopy == []

EmptyReset は似ていますが、Empty はセット内に残すスラック数を示すパラメータを受け取ることができるのに対し、Reset は常にできる限り多くのスラックを残します。

ソート

TSet はソートができます。ソート後、セットをイタレーションすると、ソートした順番で要素が表示されますが、この動作が保証されるのは、次にセットに変更を加える時点までです。ソートは不安定なので、キーの複製を許可するセットで同等のエレメントはどんな順序でも表示される可能性があります。

Sort 関数はソート順を指定するバイナリ述語を以下のように受け取ります。

    FruitSet.Sort([](const FString& A, const FString& B) {
        return A > B; // sort by reverse-alphabetical order
    });
    // FruitSet == [ "Pear", "Orange", "Melon", "Mango", "Kiwi", "Grapefruit" ] (order is temporarily guaranteed)

    FruitSet.Sort([](const FString& A, const FString& B) {
        return A.Len() < B.Len(); // sort strings by length, shortest to longest
    });
    // FruitSet == [ "Pear", "Kiwi", "Melon", "Mango", "Orange", "Grapefruit" ] (order is temporarily guaranteed)

演算子

TArray と同様に、TSet は通常の値型であり、標準的なコピー コンストラクタまたは代入演算子でコピーできます。セットは必ずエレメントを所有しているため、セットは「深いコピー」が行われ、新規のセットにはそのエレメントの個々のコピーが作られます。

    TSet<int32, FString> NewSet = FruitSet;
    NewSet.Add(TEXT("Apple"));
    NewSet.Remove(TEXT("Pear"));
    // FruitSet == [ "Pear", "Kiwi", "Melon", "Mango", "Orange", "Grapefruit" ]
    // NewSet == [ "Kiwi", "Melon", "Mango", "Orange", "Grapefruit", "Apple" ]

スラック

スラックは、要素を含まない割り当てメモリです。Reserve を呼び出すことで、要素を追加しなくてもメモリを割り当てることができます。また、Reset を呼び出すか、0 ではないスラック パラメータを指定して Empty を呼び出すことで、使用中のメモリの割り当てを解除することなく要素を削除することができます。スラックを使用すると、新しいメモリを割り当てる代わりに、事前割り当てしたメモリを利用することで、セットに新しい要素を追加するプロセスを最適化できます。また、システムでメモリの割り当てを解除する必要がないため、要素の削除も容易になります。この方法は、セットを空にした直後に、同数またはそれよりも少数の要素でそのマップを再度埋める場合に、特に効果的です。

TSet には、TArrayMax 関数のような、事前割り当てされた要素数を確認する方法が用意されていません。

次のコードは、メモリの割り当てを解除せずにセットからすべての要素を削除するため、スラックが作成されます。

    FruitSet.Reset();
    // FruitSet == [ <invalid>, <invalid>, <invalid>, <invalid>, <invalid>, <invalid> ]

要素を追加する前にメモリを事前割り当てするなど、スラックを直接作成するには、Reserve 関数を使用します。

    FruitSet.Reserve(10);
    for (int32 i = 0; i < 10; ++i)
    {
        FruitSet.Add(FString::Printf(TEXT("Fruit%d"), i));
    }
    // FruitSet == [ "Fruit9", "Fruit8", "Fruit7" ... "Fruit2", "Fruit1", "Fruit0" ]

スラックを事前アロケートすると新しい要素が逆の順番で追加されます。配列とは異なり、セットはエレメントの順序を維持しようとはせず、セットを処理するコードは要素の順序が安定または予測可能であることを求めません。

TSet からすべてのスラックを削除するには、Collapse 関数と Shrink 関数を使用します。Shrink は、コンテナの最後にあるすべてのスラックを削除しますが、最初や途中にある空の要素はそのままにします。

    // セットから他のすべての要素を削除します。
    for (int32 i = 0; i < 10; i += 2)
    {
        FruitSet.Remove(FSetElementId::FromInteger(i));
    }
    // FruitSet == ["Fruit8", <invalid>, "Fruit6", <invalid>, "Fruit4", <invalid>, "Fruit2", <invalid>, "Fruit0", <invalid> ]

    FruitSet.Shrink();
    // FruitSet == ["Fruit8", <invalid>, "Fruit6", <invalid>, "Fruit4", <invalid>, "Fruit2", <invalid>, "Fruit0" ]

上記のコードには終わりに空の要素が 1 つあるだけなので、Shrink は、無効な要素を 1 つ削除しただけです。すべてのスラックを削除するには、Shrink を実行する準備のために、まず Compact 関数または CompactStable 関数を呼び出して、空いたスペースをまとめます。名前が示すように、CompactStable は空の要素を連結しつつ要素の順序を維持します。

    FruitSet.CompactStable();
    // FruitSet == ["Fruit8", "Fruit6", "Fruit4", "Fruit2", "Fruit0", <invalid>, <invalid>, <invalid>, <invalid> ]
    FruitSet.Shrink();
    // FruitSet == ["Fruit8", "Fruit6", "Fruit4", "Fruit2", "Fruit0" ]

DefaultKeyFuncs

タイプに operator== があって非メンバ GetTypeHash がオーバーロードする限り、エレメントとキーが両方タイプなので、何も変更せずに TSet として使用できます。ただし、これらの関数をオーバーロードしたくない場合は型を key として使うと便利かもしれません。このようなケースでは、DefaultKeyFuncs を自分でカスタム化することができます。キーの型に KeyFuncs を作成するには、次に示す 2 つの typedef と 3 つの静的関数を定義する必要があります。

  • KeyInitType — キーを渡すために使用する型。通常は、ElementType テンプレート パラメータから渡されます。

  • ElementInitType — 要素を渡すために使用する型。こちらも通常は ElementType テンプレート パラメータから渡されるので、KeyInitType と同じになります。

  • KeyInitType GetSetKey(ElementInitType Element) — 要素のキーを返します。セットの場合、これは通常要素そのものです。

  • bool Matches(KeyInitType A, KeyInitType B)AB が等しい場合に true を返します。等しくない場合は false を返します。

  • uint32 GetKeyHash(KeyInitType Key)Key のハッシュ値を返します。

KeyInitTypeElementInitType は key 型 / element 型の通常の渡し方の規則に対する typedef です。通常、トリビアル型の場合は値、非トリビアル型の場合は定数参照になります。セットの element 型は key 型でもあるので、DefaultKeyFuncs は、テンプレート パラメータ ElementType を 1 つだけ使って両方を指定することを覚えておいてください。

独自の KeyFuncs を用意するときに注意すべき点は、TSet では、Matches (DefaultKeyFuncs の) を使用して等価を比較する 2 つのアイテムが、GetKeyHash (KeyFuncs の) からも同じ値を返すことを前提としていることです。

DefaultKeyFuncs を使用するとき、operator==GetKeyHash

その他

CountBytes 関数と GetAllocatedSize 関数は、現在内部配列が使用しているメモリを概算します。CountBytesFArchive パラメータを受け取りますが、GetAllocatedSize は受け取りません。これらの関数は通常、統計情報の報告に使用されます。

Dump 関数は FOutputDevice を受け取り、セットのコンテンツに関する実装情報を書き出します。すべてのハッシュ エントリからエレメントをリスト表示する DumpHashElements という関数もあります。これらの関数は、通常はデバッグ作業に使用します。

タグ
Unreal Engine のドキュメントを改善するために協力をお願いします!どのような改善を望んでいるかご意見をお聞かせください。
調査に参加する
キャンセル