TSet ähnelt TMap und TMultiMap, hat aber einen wichtigen Unterschied: Anstatt Datenwerte mit unabhängigen Schlüsseln zu verknüpfen, verwendet TSet den Datenwert selbst als Schlüssel – und zwar mit einer überschreibbaren Funktion, die das Element auswertet. TSet ist sehr schnell (konstante Zeit) zum Hinzufügen, Finden und Entfernen von Elementen. Standardmäßig unterstützt TSet keine doppelten Schlüssel, aber dieses Verhalten kann mit einem Vorlagenparameter aktiviert werden.
TSet
TSet ist eine schnelle Container-Klasse, um einzigartige Elemente in einem Kontext zu speichern, in dem die Reihenfolge keine Rolle spielt. Für die meisten Anwendungsfälle wird nur ein Parameter – der Elementtyp – benötigt. Allerdings kann TSet mit verschiedenen Vorlagenparametern eingerichtet werden, um sein Verhalten zu verändern und es vielseitiger zu machen. Sie können eine abgeleitete Struktur basierend auf DefaultKeyFuncs spezifizieren, um Hashing-Funktionalität bereitzustellen oder mehrere Schlüssel mit demselben Wert im Set zu erlauben. Zu guter Letzt können Sie, wie bei den anderen Container-Klassen, einen benutzerdefinierten Speicherallokator für die Datenspeicherung bereitstellen.
Ebenso wie TArray ist TSet ein homogener Container, was bedeutet, dass alle seine Elemente genau den gleichen Typ haben. TSet ist auch ein Werttyp und unterstützt die üblichen Kopier-, Zuweisungs- und Destructor-Operationen sowie starken Besitz seiner Elemente, die zerstört werden, wenn das TSet zerstört wird. Der Schlüsseltyp muss auch ein Werttyp sein.
TSet verwendet Hashes, was bedeutet, dass der KeyFuncs-Parameter (sofern angegeben) dem Set mitteilt, wie der Schlüssel aus einem Element bestimmt wird, wie zwei Schlüssel auf Gleichheit verglichen werden, wie der Schlüssel gehasht wird und ob das Duplizieren von Schlüsseln zulässig ist oder nicht. Diese haben Standardwerte, die eine Referenz zum Schlüssel zurückgeben, verwenden Sie operator== für Gleichheit und die Nicht-Mitglieds-Funktion GetTypeHash für das Hashing. Standardmäßig erlaubt das Set keine doppelten Schlüssel. Wenn Ihr Schlüsseltyp diese Funktionen unterstützt, kann er als Set-Schlüssel genutzt werden, ohne ein benutzerdefiniertes KeyFuncs bereitstellen zu müssen. Um ein benutzerdefiniertes KeyFuncs zu schreiben, müssen Sie die DefaultKeyFuncs-Struktur erweitern.
Zu guter Letzt kann TSet einen optionalen Allokator nutzen, um das Verhalten der Speicherallokation zu steuern. Standard-Allokatoren der Unreal Engine 4 (UE4) (wie FHeapAllocator und TInlineAllocator) können nicht als Allokatoren für TSet verwendet werden. Stattdessen verwendet TSet Set-Allokatoren, die definieren, wie viele Hash-Buckets das Set benutzen soll, und welche Standard-UE4-Allokatoren für den Element-Speicherplatz genutzt werden sollen. Weitere Informationen finden Sie unter TSetAllocator.
Im Gegensatz zu TArray ist die relative Reihenfolge von TSet-Elementen im Speicher nicht zuverlässig oder stabil, und das Iterieren über die Elemente gibt diese wahrscheinlich in einer anderen Reihenfolge zurück als der Reihenfolge, in der sie hinzugefügt wurden. Es ist auch unwahrscheinlich, dass Elemente im Speicher zusammenhängend angeordnet sind. Die Datenstruktur eines Sets ist ein dünnbesetztes Array, also ein Array, das Lücken zwischen seinen Elementen effizient unterstützt. Wenn Elemente aus dem Set entfernt werden, treten Lücken im dünnbesetzten Array auf. Durch das Hinzufügen neuer Elemente zum Array können diese Lücken geschlossen werden. Auch wenn TSet Elemente nicht mischt, um Lücken zu füllen, können Pointer auf Set-Elemente trotzdem ungültig werden, da der gesamte Speicherplatz neu zugewiesen werden kann, wenn er voll ist und neue Elemente hinzugefügt werden.
TSet (wie viele Unreal-Engine-Container) geht davon aus, dass der Elementtyp trivial verschiebbar ist, was bedeutet, dass Elemente sicher von einem Ort im Speicher an einen anderen verschoben werden können, indem die Roh-Bytes direkt kopiert werden.
Erstellen und Füllen eines Sets
Sie können ein TSet folgendermaßen erstellen:
TSet<FString> FruitSet;Dadurch wird ein leeres TSet erstellt, das die FString-Daten enthalten wird. Das TSet vergleicht Elemente direkt mit operator==, hasht sie mit GetTypeHash und verwendet den Standard-Heap-Allokator. Zu diesem Zeitpunkt wurde noch kein Speicher zugewiesen.
Standardmäßig verwendet man die Add-Funktion und gibt einen Schlüssel (Element) an, um ein Set zu bevölkern:
FruitSet.Add(TEXT("Banana"));
FruitSet.Add(TEXT("Grapefruit"));
FruitSet.Add(TEXT("Pineapple"));
// FruitSet == [ "Banana", "Grapefruit", "Pineapple" ]Obwohl die Elemente hier in der Reihenfolge aufgeführt sind, in der sie eingefügt wurden, kann keine Garantie gegeben werden, dass sie im Speicher tatsächlich sortiert sind. Bei einem neuen Set befinden sie sich wahrscheinlich in der Reihenfolge des Einfügens, aber je mehr Elemente eingefügt und entfernt werden, desto unwahrscheinlicher wird es, dass neue Elemente am Ende erscheinen.
Da dieses Set den Standard-Allokator verwendet, sind Schlüssel garantiert einzigartig. Es folgt das Ergebnis des Versuchs, einen doppelten Schlüssel hinzuzufügen:
FruitSet.Add(TEXT("Pear"));
FruitSet.Add(TEXT("Banana"));
// FruitSet == [ "Banana", "Grapefruit", "Pineapple", "Pear" ]
// Note: Only one banana entry.Das Set enthält jetzt vier Elemente. „Pear“ erhöhte die Anzahl von drei auf vier, aber das neue „Banana“ änderte die Anzahl der Elemente im Set nicht, da es den alten „Banana“-Eintrag ersetzte.
Wie bei TArray können wir auch Emplace anstatt Add verwenden, um beim Einfügen in ein Set die Erstellung von Provisorien zu vermeiden.
FruitSet.Emplace(TEXT("Orange"));
// FruitSet == [ "Banana", "Grapefruit", "Pineapple", "Pear", "Orange" ]Hier wird das Argument direkt an den Constructor des Schlüsseltyps weitergegeben. Dies vermeidet die Erstellung eines temporären FString für den Wert. Im Gegensatz zu TArray ist es nur möglich, Elemente mit einem Argument-Constructor in ein Set einzufügen.
Es ist auch möglich, alle Elemente aus einem anderen Set einzufügen, indem Sie die Funktion Append verwenden, um sie zusammenzuführen:
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" ]Das Ergebnis im obigen Beispiel entspricht dem Verwenden von Add oder Emplace zum einzelnen Hinzufügen der Elemente. Doppelte Keys aus dem Quell-Set ersetzen ihre Gegenstücke im Ziel.
UPROPERTY-TSets bearbeiten
Wenn Sie das TSet mit dem UPROPERTY-Makro und einem der „bearbeitbaren“ Stichworte (EditAnywhere, EditDefaultsOnly oder EditInstanceOnly) markieren, können Sie Elemente im Unreal Editor hinzufügen und bearbeiten.
UPROPERTY(Category = SetExample, EditAnywhere)
TSet<FString> FruitSet;Iteration
Die Iteration über TSets ist ähnlich wie bei TArrays. Sie können die C++-„-Ranged-for“-Funktion verwenden:
for (auto& Elem : FruitSet)
{
FPlatformMisc::LocalPrint(
*FString::Printf(
TEXT(" \"%s\"\n"),
*Elem
)
);
}
// Output:
Sie können Iteratoren auch mit den Funktionen CreateIterator und CreateConstIterators erstellen. CreateIterator gibt einen Iterator mit Lese-/Schreibzugriff zurück, während CreateConstIterator einen schreibgeschützten Iterator zurückgibt. In jedem Fall kannst du die Key- und Value-Funktionen dieser Iteratoren verwenden, um die Elemente zu untersuchen. Die Ausgabe der Inhalte unseres Beispiel-„Fruit“-Sets mit Iteratoren sieht so aus:
for (auto It = FruitSet.CreateConstIterator(); It; ++It)
{
FPlatformMisc::LocalPrint(
*FString::Printf(
TEXT("(%s)\n"),
*It
)
);
}Anfragen
Um herauszufinden, wie viele Elemente aktuell im Set sind, rufen Sie die Num-Funktion auf.
int32 Count = FruitSet.Num();
// Count == 8Um zu bestimmen, ob ein Set ein spezifisches Element enthält oder nicht, rufe die Contains-Funktion wie folgt auf:
bool bHasBanana = FruitSet.Contains(TEXT("Banana"));
bool bHasLemon = FruitSet.Contains(TEXT("Lemon"));
// bHasBanana == true
// bHasLemon == falseSie können die FSetElementId-Struktur verwenden, um den Index eines Schlüssels innerhalb des Sets zu finden. Sie können diesen Index dann mit operator[] verwenden, um das Element abzurufen. Der Aufruf von operator[] auf einem Nicht-const-Set gibt eine Nicht-const Referenz zurück, und der Aufruf auf einem const-Set gibt eine const-Referenz zurück.
FSetElementId BananaIndex = FruitSet.Index(TEXT("Banana"));
// BananaIndex is a value between 0 and (FruitSet.Num() - 1)
FPlatformMisc::LocalPrint(
*FString::Printf(
TEXT(" \"%s\"\n"),
*FruitSet[BananaIndex]
)
);
// Prints "Banana"
Wenn Sie sich nicht sicher sind, ob Ihr Set einen Schlüssel enthält oder nicht, können Sie dies mit der Contains-Funktion prüfen und dann operator[] verwenden. Dies ist jedoch nicht optimal, da ein erfolgreicher Abruf zwei Lookups für denselben Schlüssel umfasst. Die Find-Funktion kombiniert diese Verhaltensweisen mit einem einzigen Lookup. Find gibt einen Pointer auf den Wert des Elements zurück, wenn das Set den Schlüssel enthält, oder einen Null-Pointer, wenn dieser nicht vorhanden ist. Ruft man Find auf einem const-Set auf, wird der const-Pointer der Rückgabe ebenfalls const.
FString* PtrBanana = FruitSet.Find(TEXT("Banana"));
FString* PtrLemon = FruitSet.Find(TEXT("Lemon"));
// *PtrBanana == "Banana"
// PtrLemon == nullptrDie Array-Funktion gibt ein TArray zurück, das mit einer Kopie aller Elemente im TSet bevölkert ist. Das Array, das Sie durchlaufen, wird zu Beginn der Operation geleert, sodass die resultierende Anzahl an Elementen immer der Anzahl der Elemente im Set entspricht:
TArray<FString> FruitArray = FruitSet.Array();
// FruitArray == [ "Banana","Grapefruit","Pineapple","Pear","Orange","Kiwi","Melon","Mango" ] (order may vary)Entfernung
Elemente können mit der Remove-Funktion nach Index entfernt werden. Diese Funktion sollte jedoch nur beim Iterieren durch die Elemente verwendet werden. Die Remove-Funktion gibt die Anzahl der entfernten Elemente zurück und ist 0, wenn der angegebene Schlüssel nicht im Set enthalten war. Falls ein TSet doppelte Schlüssel unterstützt, entfernt Remove alle passenden Elemente.
FruitSet.Remove(0);
// FruitSet == [ "Grapefruit","Pineapple","Pear","Orange","Kiwi","Melon","Mango" ]Das Entfernen von Elementen kann Lücken in der Datenstruktur hinterlassen, die bei der Visualisierung des Sets im Überwachungsfenster von Visual Studio sichtbar werden, aber aus Gründen der Klarheit wurden sie hier weggelassen.
int32 RemovedAmountPineapple = FruitSet.Remove(TEXT("Pineapple"));
// RemovedAmountPineapple == 1
// FruitSet == [ "Grapefruit","Pear","Orange","Kiwi","Melon","Mango" ]
FString RemovedAmountLemon = FruitSet.Remove(TEXT("Lemon"));
// RemovedAmountLemon == 0Zum Schluss können Sie mit den Funktionen Empty oder Reset alle Elemente aus dem Set entfernen.
TSet<FString> FruitSetCopy = FruitSet;
// FruitSetCopy == [ "Grapefruit","Pear","Orange","Kiwi","Melon","Mango" ]
FruitSetCopy.Empty();
// FruitSetCopy == []Empty und Reset sind ähnlich, aber Empty kann einen Parameter entgegennehmen, der angibt, wie viel Slack im Set gelassen werden soll, während Reset immer so viel Slack wie möglich lässt.
Sortierung
Ein TSet kann sortiert werden. Nach dem Sortieren werden die Elemente bei einer Iteration über das Set in sortierter Reihenfolge angezeigt. Dieses Verhalten ist aber nur so lange garantiert, bis Sie das nächste Mal das Set modifizieren. Die Sortierung ist instabil, daher können gleichartige Elemente in einem Set, das doppelte Schlüssel unterstützt, in beliebiger Reihenfolge erscheinen.
Die Sort-Funktion nimmt ein binäres Prädikat entgegen, das die Sortierreihenfolge angibt, wie folgt:
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)Operatoren
Wie bei TArray ist TSet ein regulärer Wert und kann als solcher mit dem Standard-Kopier-Constructor oder dem Zuweisungsoperator kopiert werden. Sets besitzen ihre Elemente vollständig, also ist das Kopieren eines Sets vollständig; das neue Set hat seine eigene Kopie der Elemente.
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" ]Slack
Slack ist zugewiesener Speicher, der kein Element enthält. Sie können Speicher allokieren, ohne Elemente hinzuzufügen, indem Sie Reserve aufrufen. Sie können zudem Elemente entfernen, ohne den von ihnen belegten Speicher freizugeben, indem Sie Reset oder Empty mit einem Slack-Parameter ungleich Null aufrufen. Slack optimiert den Prozess des Hinzufügens neuer Elemente zum Set, indem es vorab zugewiesenen Speicher verwendet, anstatt neuen Speicher allokieren zu müssen. Dies kann außerdem bei der Entfernung von Elementen helfen, da das System keinen Speicher freigeben muss. Das ist besonders effizient, wenn Sie ein Set leeren, das sofort neu mit der gleichen Anzahl von Elementen oder weniger gefüllt werden soll.
TSet bietet im Gegensatz zur Max-Funktion in TArray keine Möglichkeit, zu überprüfen, wie viele Elemente vorab zugewiesen wurden.
Der folgende Code entfernt alle Elemente aus dem Set, ohne Speicher freizugeben, was zu Slack führt:
FruitSet.Reset();
// FruitSet == [ <invalid>, <invalid>, <invalid>, <invalid>, <invalid>, <invalid> ]Um Slack direkt zu erstellen, etwa um Speicher vor dem Hinzufügen von Elementen vorzuallokieren, können Sie die Reserve-Funktion verwenden.
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" ]Die Vorab-Allokation des Slacks hat dazu geführt, dass die neuen Elemente in umgekehrter Reihenfolge hinzugefügt wurden. Anders als Arrays versuchen Sets nicht, die Reihenfolge der Elemente aufrechtzuerhalten, und Code, der mit Sets arbeitet, sollte nicht erwarten, dass die Reihenfolge der Elemente stabil oder vorhersehbar ist.
Um sämtlichen Slack aus einem TSet zu entfernen, verwenden Sie die Collapse- und Shrink-Funktionen. Shrink entfernt sämtlichen Slack vom Ende des Containers, aber leere Elemente bleiben in der Mitte oder am Anfang.
// Remove every other element from the set.
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" ]DurchSchrumpfen wurde nur ein ungültiges Element im obigen Code entfernt, weil am Ende nur ein leeres Element war. Um sämtlichen Slack zu entfernen, sollte zuerst die Funktion Compact oder CompactStable aufgerufen werden, damit die leeren Räume zur Vorbereitung auf Shrink gruppiert werden. Wie der Name andeutet, behält CompactStable die Reihenfolge der Elemente bei, während es leere Elemente konsolidiert.
FruitSet.CompactStable();
// FruitSet == ["Fruit8", "Fruit6", "Fruit4", "Fruit2", "Fruit0", <invalid>, <invalid>, <invalid>, <invalid> ]
FruitSet.Shrink();
// FruitSet == ["Fruit8", "Fruit6", "Fruit4", "Fruit2", "Fruit0" ]DefaultKeyFuncs
Solange ein Typ einen operator== und eine Nicht-Mitglieds-GetTypeHash-Überladung hat, kann TSet diese verwenden, da der Typ sowohl das Element als auch der Schlüssel ist. Allerdings kann es nützlich sein, Typen als Schlüssel zu verwenden, wenn eine Überladung dieser Funktionen unerwünscht ist. In diesen Fällen können Sie Ihre eigenen benutzerdefinierten DefaultKeyFuncs angeben. Um KeyFuncs für Ihren Schlüsseltyp zu erstellen, müssen Sie zwei Typedefs und drei statische Funktionen wie folgt definieren:
KeyInitType: Typ, der verwendet wird, um Schlüssel zu übergeben. Wird normalerweise aus dem ElementType-Vorlage-Parameter abgerufen.ElementInitType: Typ, mit dem Elemente übergeben werden. Wird normalerweise auch aus dem Vorlage-Parameter bezogen und ist daher identisch mit KeyInitType.KeyInitType GetSetKey(ElementInitType Element)– Gibt den Schlüssel eines Elements zurück. Bei Sets ist das meist einfach das Element selbst.bool Matches(KeyInitType A, KeyInitType B)– GibtTruezurück, wennAundBgleichwertig sind, sonstFalse.uint32 GetKeyHash(KeyInitType Key)– Gibt den Hash-Wert vonKeyzurück.
KeyInitType und ElementInitType sind Typedefs der normalen Übergabekonvention des Schlüssel-/Elementtyps. In der Regel ist das ein Wert für triviale Typen und eine const-Referenz für nicht-triviale Typen. Zur Erinnerung: Der Elementtyp eines Sets ist auch der Schlüsseltyp, weshalb DefaultKeyFuncs nur einen Vorlage-Parameter, ElementType, verwendet, um beide zu definieren.
TSet geht davon aus, dass zwei Elemente, die mit Matches (in DefaultKeyFuncs) als gleich ermittelt wurden, auch von GetKeyHash (in KeyFuncs) denselben Wert zurückgeben.
Modifizieren Sie nicht den Schlüssel eines bestehenden Elements auf eine Weise, die Ergebnisse aus diesen Funktionen verändert, da der interne Hash des Sets ungültig wird. Diese Regeln gelten auch für Überladungen von operator== und GetKeyHash, wenn die Standard-Implementierung von DefaultKeyFuncs verwendet wird.
Verschiedenes
Die Funktionen CountBytes und GetAllocatedSize schätzen, wie viel Speicher das interne Array aktuell verwendet. CountBytes akzeptiert einen FArchive-Parameter, GetAllocatedSize jedoch nicht. Diese Funktionen werden in der Regel für die Berichterstattung zu Statistiken verwendet.
Die Dump-Funktion nimmt ein FOutputDevice und schreibt einige Implementierungsinformationen über die Inhalte des Sets aus. Es gibt auch eine DumpHashElements-Funktion, die alle Elemente aus allen Hash-Einträgen auflistet. Diese Funktionen werden normalerweise für das Debugging verwendet.