TSet est similaire à TMap et TMultiMap, mais avec une différence importante : au lieu d'associer des valeurs de données à des clés indépendantes, un TSet utilise la valeur de données elle-même comme clé via une fonction remplaçable qui évalue l'élément. TSet est très rapide (temps constant) pour l'ajout, la recherche et la suppression d'éléments. Par défaut, TSet ne prend pas en charge les clés en double, mais ce comportement peut être activé à l'aide d'un paramètre de modèle.
TSet
TSet est une classe de conteneur rapide qui permet de stocker des éléments uniques dans un contexte où l'ordre importe peu. Dans la plupart des cas, un seul paramètre est nécessaire, à savoir le type d'élément. Cependant, un TSet peut être configuré avec différents paramètres de modèle pour modifier son comportement et le rendre plus polyvalent. Vous pouvez spécifier une structure dérivée basée sur DefaultKeyFuncs pour fournir une fonctionnalité de hachage et autoriser l'utilisation de plusieurs clés de même valeur dans l'ensemble. Enfin, comme pour les autres classes de conteneur, vous pouvez fournir un allocateur de mémoire personnalisé pour le stockage de ses données.
Tout comme TArray, TSet est un conteneur homogène, ce qui signifie que tous ses éléments sont strictement du même type. TSet est également un type par valeur et prend en charge les opérations habituelles de copie, d'assignation et de destruction, ainsi qu'une gestion stricte de ses éléments, qui sont détruits lorsque le TSet est détruit. Le type de clé doit également être un type de valeur.
Le TSet utilise des hachages, ce qui signifie que le paramètre du modèle KeyFuncs, s'il est fourni, indique à l'ensemble comment déterminer la clé à partir d'un élément, comment comparer deux clés pour en déterminer l'égalité, comment calculer le hachage de la clé et s'il faut ou non autoriser les clés en double. Celles-ci ont des valeurs par défaut qui renvoient une référence à la clé, puis utilisent l'opérateur == pour déterminer l'égalité et la fonction non membre GetTypeHash pour le hachage. Par défaut, l'ensemble ne prend pas en charge les clés en double. Si votre type de clé prend en charge ces fonctions, vous pouvez l'utiliser comme clé d'ensemble sans fournir de fonction KeyFuncs personnalisée. Pour écrire une fonction KeyFuncs personnalisée, développez la structure DefaultKeyFuncs.
Enfin, TSet peut utiliser un allocateur facultatif pour contrôler le comportement d'allocation de la mémoire. Les allocateurs standard de l'Unreal Engine 4 (UE4) (tels que FHeapAllocator et TInlineAllocator) ne peuvent pas être utilisés comme allocateurs pour TSet. Au lieu de cela, TSet utilise des allocateurs d'ensemble, qui définissent le nombre de compartiments de hachage que l'ensemble doit utiliser, et les allocateurs standard de l'UE4 à utiliser pour le stockage des éléments. Pour plus d'informations, consultez la rubrique TSetAllocator.
Contrairement à TArray, l'ordre relatif des éléments d'un TSet en mémoire n'est ni fiable ni stable, et l'itération sur les éléments risque de les renvoyer dans un ordre différent de celui dans lequel ils ont été ajoutés. Il est également peu probable que les éléments soient disposés de manière contiguë en mémoire. La structure de données de base d'un ensemble est une matrice creuse, qui prend en charge efficacement les espaces entre ses éléments. Étant donné que des éléments sont supprimés de l'ensemble, des espaces apparaîtront dans la matrice creuse. Pour combler ces espaces, vous pouvez ajouter de nouveaux éléments à la matrice. Cependant, même si le TSet ne réorganise pas les éléments pour combler les creux, les pointeurs vers les éléments de l'ensemble peuvent quand même devenir non valides, car l'ensemble du stockage peut être réalloué lorsqu'il est plein et que de nouveaux éléments sont ajoutés.
Le TSet (comme beaucoup de conteneurs de l'Unreal Engine) suppose que le type d'élément est facilement déplaçable, ce qui signifie que les éléments peuvent être déplacés en toute sécurité d'un emplacement mémoire à un autre en copiant directement leurs octets bruts.
Créer et remplir un ensemble
Vous pouvez créer un TSet comme suit :
TSet<FString> FruitSet;Cela crée un TSet vide qui contiendra les données de FString. Le TSet compare directement les éléments avec operator==, calcule leur hachage avec GetTypeHash et utilise l'allocateur de tas standard. Aucune mémoire n'a été allouée à ce stade.
La méthode standard de remplir un ensemble consiste à utiliser la fonction Add et à fournir une clé (élément) :
FruitSet.Add(TEXT("Banana"));
FruitSet.Add(TEXT("Grapefruit"));
FruitSet.Add(TEXT("Pineapple"));
// FruitSet == [ "Banana", "Grapefruit", "Pineapple" ]Bien que les éléments soient répertoriés dans l'ordre d'insertion, leur ordre réel n'est pas garanti en mémoire. Pour un nouvel ensemble, ils sont probablement ordonnés par ordre d'insertion, mais au fur et à mesure des ajouts et suppressions, il devient de moins en moins probable que les nouveaux éléments apparaissent à la fin.
Étant donné que cet ensemble utilise l'allocateur par défaut, les clés sont uniques. Voici le résultat obtenu lors d'une tentative d'ajout d'une clé en double :
FruitSet.Add(TEXT("Pear"));
FruitSet.Add(TEXT("Banana"));
// FruitSet == [ "Banana", "Grapefruit", "Pineapple", "Pear" ]
// Note: Only one banana entry.L'ensemble contient désormais quatre éléments. "Poire" a fait passer le nombre de trois à quatre, mais le nouvel élément "Banane" n'a pas modifié le nombre d'éléments de l'ensemble, car il a remplacé l'ancien élément "Banane".
Comme TArray, on peut également utiliser Emplace au lieu de Add pour éviter la création de variables temporaires lors de l'insertion dans l'ensemble :
FruitSet.Emplace(TEXT("Orange"));
// FruitSet == [ "Banana", "Grapefruit", "Pineapple", "Pear", "Orange" ]Ici, l'argument est transmis directement au constructeur du type de clé. Cela évite de devoir créer un FString temporaire pour la valeur. Contrairement à TArray, il n'est possible d'insérer des éléments dans un ensemble qu'avec des constructeurs à un seul argument.
Il est également possible d'insérer tous les éléments d'un autre ensemble en utilisant la fonction Append pour les fusionner :
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" ]Dans l'exemple ci-dessus, l'ensemble résultant équivaut à l'utilisation de Add ou Emplace pour ajouter les éléments individuellement. Les clés en double provenant de l'ensemble source remplaceront leurs homologues dans l'ensemble cible.
Modifier les TSets UPROPERTY
Si vous marquez le TSet avec la macro UPROPERTY et l'un des mots clé "modifiable" (EditAnywhere, EditDefaultsOnly ou EditInstanceOnly), vous pouvez ajouter et modifier des éléments dans l'Unreal Editor.
UPROPERTY(Category = SetExample, EditAnywhere)
TSet<FString> FruitSet;Itération
L'itération sur les TSets est similaire aux TArrays. Vous pouvez utiliser la boucle for étendue de C++ :
for (auto& Elem : FruitSet)
{
FPlatformMisc::LocalPrint(
*FString::Printf(
TEXT(" \"%s\"\n"),
*Elem
)
);
}
// Output:
Vous pouvez également créer des itérateurs avec les fonctions CreateIterator et CreateConstIterators. CreateIterator renvoie un itérateur avec un accès en lecture-écriture, tandis que CreateConstIterator renvoie un itérateur en lecture seule. Dans tous les cas, vous pouvez utiliser les fonctions Key et Value de ces itérateurs pour examiner les éléments. Voici à quoi ressemblerait l'affichage du contenu de notre ensemble d'exemple "fruit" avec des itérateurs :
for (auto It = FruitSet.CreateConstIterator(); It; ++It)
{
FPlatformMisc::LocalPrint(
*FString::Printf(
TEXT("(%s)\n"),
*It
)
);
}Requêtes
Pour savoir combien d'éléments sont actuellement présents dans l'ensemble, appelez la fonction Num.
int32 Count = FruitSet.Num();
// Count == 8Pour déterminer si un ensemble contient ou non un élément spécifique, appelez la fonction Contains comme suit :
bool bHasBanana = FruitSet.Contains(TEXT("Banana"));
bool bHasLemon = FruitSet.Contains(TEXT("Lemon"));
// bHasBanana == true
// bHasLemon == falseVous pouvez utiliser la structure FSetElementId pour trouver l'index d'une clé dans l'ensemble. Vous pouvez ensuite utiliser cet index avec l'opérateur [] pour récupérer l'élément. L'appel de l'opérateur [] sur un ensemble non constant renvoie une référence non constante tandis que l'appel de celui-ci sur un ensemble constant renvoie une référence constante.
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"
Si vous ne savez pas si votre ensemble contient ou non une clé, vous pouvez vérifier cela en utilisant la fonction Contains, puis utiliser l'opérateur []. Cependant, ce n'est pas optimal, puisqu'une récupération réussie implique deux recherches sur la même clé. La fonction Find associe ces comportements dans une même recherche. La fonction Find renvoie un pointeur vers la valeur de l'élément si l'ensemble contient la clé, ou un pointeur nul si ce n'est pas le cas. Lorsque l'option Find est appelée sur un ensemble constant, le pointeur renvoyé est également constant.
FString* PtrBanana = FruitSet.Find(TEXT("Banana"));
FString* PtrLemon = FruitSet.Find(TEXT("Lemon"));
// *PtrBanana == "Banana"
// PtrLemon == nullptrLa fonction Array renvoie un TArray contenant une copie de tous les éléments du TSet. La matrice que vous fournissez sera vidée au début de l'opération. Le nombre d'éléments résultants sera toujours égal au nombre d'éléments de l'ensemble :
TArray<FString> FruitArray = FruitSet.Array();
// FruitArray == [ "Banana","Grapefruit","Pineapple","Pear","Orange","Kiwi","Melon","Mango" ] (order may vary)Suppression
Les éléments peuvent être supprimés par index avec la fonction Remove, mais cette option n'est recommandée que pour itérer sur les éléments. La fonction Remove renvoie le nombre d'éléments supprimés et la valeur est de 0 si la clé fournie ne figurait pas dans l'ensemble. Si un TSet prend en charge les clés en double, Remove supprime tous les éléments correspondants.
FruitSet.Remove(0);
// FruitSet == [ "Grapefruit","Pineapple","Pear","Orange","Kiwi","Melon","Mango" ]La suppression d'éléments peut créer des trous dans la structure de données. Vous pouvez les voir en visualisant l'ensemble dans la fenêtre d'observation de Visual Studio, mais ils ont été omis ici par souci de clarté.
int32 RemovedAmountPineapple = FruitSet.Remove(TEXT("Pineapple"));
// RemovedAmountPineapple == 1
// FruitSet == [ "Grapefruit","Pear","Orange","Kiwi","Melon","Mango" ]
FString RemovedAmountLemon = FruitSet.Remove(TEXT("Lemon"));
// RemovedAmountLemon == 0Enfin, vous pouvez supprimer tous les éléments de l'ensemble avec les fonctions Empty ou Reset.
TSet<FString> FruitSetCopy = FruitSet;
// FruitSetCopy == [ "Grapefruit","Pear","Orange","Kiwi","Melon","Mango" ]
FruitSetCopy.Empty();
// FruitSetCopy == []Empty et Reset sont similaires, mais Empty peut prendre un paramètre pour indiquer la quantité de marge à laisser dans l'ensemble, alors que Reset laisse toujours autant de marge que possible.
Tri
Un TSet peut être trié. Après le tri, l'itération sur l'ensemble présente les éléments dans un ordre ordonné, mais ce comportement n'est garanti que jusqu'à la prochaine modification de l'ensemble. Le tri est instable. Les éléments équivalents d'un ensemble prenant en charge les clés en double peuvent donc apparaître dans n'importe quel ordre.
La fonction Sort accepte un prédicat binaire qui spécifie l'ordre de tri, comme suit :
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)Opérateurs
À l'instar de TArray, TSet est un type de valeur standard qui peut être copié à l'aide du constructeur de copie standard ou de l'opérateur d'assignation. Les ensembles étant propriétaires de leurs éléments, la copie d'un ensemble est un processus complexe, et le nouvel ensemble aura sa propre copie des éléments.
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" ]Marge
La marge est une allocation de mémoire qui ne contient pas d'élément. Vous pouvez allouer de la mémoire sans ajouter d'éléments en appelant Reserve et supprimer des éléments sans désallouer la mémoire qu'ils utilisaient en appelant Reset ou en appelant Empty avec un paramètre de marge non nul. La marge optimise le processus d'ajout de nouveaux éléments à l'ensemble en utilisant de la mémoire préallouée au lieu de devoir allouer à nouveau de la nouvelle mémoire. Elle peut également faciliter la suppression d'éléments, puisque le système n'a pas besoin de désallouer de la mémoire. Cette option est particulièrement efficace lors du vidage d'un ensemble qui doit se remplir immédiatement avec le même nombre d'éléments ou moins.
Le TSet ne permet pas de vérifier le nombre d'éléments préalloués de la même manière que la fonction Max de TArray.
Le code suivant supprime tous les éléments de l'ensemble sans désallouer de la mémoire, ce qui donne lieu à la création d'une marge :
FruitSet.Reset();
// FruitSet == [ <invalid>, <invalid>, <invalid>, <invalid>, <invalid>, <invalid> ]Pour créer directement la marge, par exemple pour préallouer de la mémoire avant d'ajouter des éléments, utilisez la fonction 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" ]La préallocation de la marge a entraîné l'ajout des nouveaux éléments dans l'ordre inverse. Contrairement aux matrices, les ensembles ne tentent pas de maintenir l'ordre des éléments et le code qui traite des ensembles ne doit pas s'attendre à ce que l'ordre des éléments soit stable ou prévisible.
Pour supprimer toute marge d'un TSet, utilisez les fonctions Collapse et Shrink. La fonction Shrink supprime toute marge à la fin du conteneur, mais laisse les éléments vides au début et au milieu.
// 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" ]La fonction Shrink n'a supprimé qu'un élément non valide du code ci-dessus, car il n'y avait qu'un seul élément vide à la fin. Pour supprimer toute marge, appelez d'abord la fonction Compact ou CompactStable afin que les espaces vides soient regroupés en préparation de l'appel de la fonction Shrink. Comme son nom l'indique, la fonction CompactStable maintient l'ordre des éléments tout en regroupant les éléments vides.
FruitSet.CompactStable();
// FruitSet == ["Fruit8", "Fruit6", "Fruit4", "Fruit2", "Fruit0", <invalid>, <invalid>, <invalid>, <invalid> ]
FruitSet.Shrink();
// FruitSet == ["Fruit8", "Fruit6", "Fruit4", "Fruit2", "Fruit0" ]DefaultKeyFuncs
Tant qu'un type a un operator== et une surcharge GetTypeHash non membre, le TSet peut l'utiliser, puisque le type est à la fois l'élément et la clé. Cependant, il peut être utile d'utiliser les types comme clés lorsqu'il n'est pas souhaitable de surcharger ces fonctions. Dans ce cas, vous pouvez fournir votre propre fonction DefaultKeyFuncs personnalisée. Pour créer une fonction KeyFuncs pour votre type de clé, vous devez définir deux définitions de type et trois fonctions statiques, comme suit :
KeyInitType— type utilisé pour transmettre des clés. Généralement tiré du paramètre de modèle ElementType.ElementInitType— Type utilisé pour transmettre des éléments. Généralement tiré du paramètre de modèle ElementType, et donc identique à KeyInitType.KeyInitType GetSetKey(ElementInitType Element)— Renvoyer la clé d'un élément. En ce qui concerne les ensembles, il s'agit généralement de l'élément lui-même.bool Matches(KeyInitType A, KeyInitType B)— renvoyertruesiAetBsont équivalents,falsesinon.uint32 GetKeyHash(KeyInitType Key)— renvoyer la valeur de hachage de laclé.
KeyInitType et ElementInitType sont des définitions de type pour la convention de transmission normale du type de clé/élément. Il s'agit généralement d'une valeur pour les types triviaux et d'une référence constante pour les types non triviaux. N'oubliez pas que le type d'élément d'un ensemble est également le type de clé, c'est pourquoi DefaultKeyFuncs n'utilise qu'un seul paramètre de modèle, notamment ElementType, pour définir les deux.
TSet suppose que deux éléments considérés comme égaux à l'aide de la fonction Matches (dans DefaultKeyFuncs) renverront également la même valeur que GetKeyHash (dans KeyFuncs).
Ne modifiez pas la clé d'un élément existant de manière à modifier les résultats de l'une de ces fonctions, car cela invaliderait le hachage interne de l'ensemble. Ces règles s'appliquent également aux surcharges de operator== et de GetKeyHash lors de l'utilisation de l'implémentation par défaut de DefaultKeyFuncs.
Divers
Les fonctions CountBytes et GetAllocatedSize calculent une estimation de la quantité de mémoire utilisée par la matrice interne. CountBytes prend un paramètre FArchive, contrairement à GetAllocatedSize. Ces fonctions sont généralement utilisées pour générer des rapports statistiques.
La fonction Dump prend un FOutputDevice et écrit des informations d'implémentation sur le contenu de l'ensemble. La fonction DumpHashElements répertorie également tous les éléments de toutes les entrées de hachage. Ces fonctions sont généralement utilisées pour le débogage.