TMap

Après TArray, le conteneur le plus couramment utilisé dans l'Unreal Engine est TMap. TMap est similaire à TSet, car sa structure repose sur des clés de hachage. Cependant, contrairement à TSet, TMap stocke les données sous forme de paires clé-valeur (TPair<KeyType, ValueType>) qui utilisent des clés uniquement pour le stockage et la récupération.

Types de mappages dans l'Unreal Engine

Il existe deux types de mappages dans l'Unreal Engine :

• TMap

• TMultiMap

Aperçu du TMap

• Dans un TMap, les paires clé-valeur sont traitées comme le type d'élément du mappage, comme si chaque paire était un objet individuel. Dans ce document, un élément désigne une paire clé-valeur, tandis que ses composants individuels sont appelés clé de l'élément ou valeur de l'élément.

• Le type d'élément est un TPair<KeyType, ElementType>, bien qu'il soit rare que vous deviez faire directement référence au type TPair.

• Les clés TMap sont uniques.

• À l'instar de TArray, TMap est un conteneur homogène, ce qui signifie que tous ses éléments sont strictement du même type.

• TMap est 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 mappage est détruit. La clé et la valeur doivent également être des types de valeur.

• TMap est un conteneur de hachage, ce qui signifie que le type de clé doit prendre en charge la fonction GetTypeHash et fournir un opérateur == permettant de comparer les clés en termes d'égalité

Aperçu du TMultiMap

• Prend en charge le stockage de plusieurs clés identiques.

• Lorsque vous ajoutez une nouvelle paire clé-valeur à un TMap avec une clé qui correspond à une paire existante, la nouvelle paire remplace l'ancienne.

• Dans un TMultiMap, le conteneur stocke la nouvelle paire et l'ancienne.

Le TMap peut accepter un allocateur facultatif pour contrôler le comportement d'allocation de la mémoire. Toutefois, à la différence de TArray, il s'agit d'allocateurs d'ensemble et non des allocateurs Unreal standard tels que FHeapAllocator et TInlineAllocator. Set Allocators, (TSetAllocator), détermine le nombre de compartiments de hachage que le mappage doit utiliser, ainsi que les allocateurs UE standard qui doivent être utilisés pour le hachage et le stockage des éléments.

Le dernier paramètre du modèle TMap est KeyFuncs. Il indique au mappage comment récupérer la clé du type d'élément, comment comparer deux clés pour déterminer l'égalité et comment hacher la clé. 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 appellent la fonction non membre GetTypeHash pour le hachage. Si votre type de clé prend en charge ces fonctions, vous pouvez l'utiliser comme clé de mappage sans fournir de fonction KeyFuncs personnalisée.

Contrairement à TArray, l'ordre relatif des éléments d'un TMap 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 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 mappage est une matrice creuse, qui prend en charge efficacement les espaces entre ses éléments. Étant donné que des éléments sont supprimés du mappage, 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 TMap ne réorganise pas les éléments pour combler les creux, les pointeurs vers les éléments du mappage 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.

Créer et remplir un mappage

Le code suivant crée un TMap :

TMap<int32, FString> FruitMap;

FruitMap est désormais un TMap vide de chaînes identifiées par des clés entières. Nous n'avons pas spécifié d'allocateur ni de KeyFuncs. Le mappage effectue donc une allocation de tas standard, compare la clé de type int32 à l'aide de l'opérateur == et procède au hachage de la clé avec GetTypeHash. Aucune mémoire n'a été allouée à ce stade.

Ajouter

La méthode standard pour remplir un mappage consiste à appeler Add avec une clé et une valeur :

FruitMap.Add(5, TEXT("Banana"));
FruitMap.Add(2, TEXT("Grapefruit"));
FruitMap.Add(7, TEXT("Pineapple"));
// FruitMap == [
// 	{ Key: 5, Value: "Banana"     },
// 	{ Key: 2, Value: "Grapefruit" },
// 	{ Key: 7, Value: "Pineapple"  }
// ]

Il ne s'agit pas d'un TMultiMap ; les clés sont donc uniques. Voici le résultat obtenu lors d'une tentative d'ajout d'une clé en double :

FruitMap.Add(2, TEXT("Pear"));
// FruitMap == [
// 	{ Key: 5, Value: "Banana"    },
// 	{ Key: 2, Value: "Pear"      },
// 	{ Key: 7, Value: "Pineapple" }
// ]

Le mappage contient toujours trois éléments, mais la valeur précédente de Grapefruit avec une clé de 2 a été remplacée par Pear.

La fonction Add peut accepter une clé sans valeur. À l'appel d'une fonction Add surchargée, la valeur est construite par défaut :

FruitMap.Add(4);
// FruitMap == [
// 	{ Key: 5, Value: "Banana"    },
// 	{ Key: 2, Value: "Pear"      },
// 	{ Key: 7, Value: "Pineapple" },
// 	{ Key: 4, Value: ""          }
// ]

Emplace

Comme TArray, on peut utiliser Emplace au lieu de Add pour éviter la création de variables temporaires lors de l'insertion dans le mappage :

FruitMap.Emplace(3, TEXT("Orange"));
// FruitMap == [
// 	{ Key: 5, Value: "Banana"    },
// 	{ Key: 2, Value: "Pear"      },
// 	{ Key: 7, Value: "Pineapple" },
// 	{ Key: 4, Value: ""          },
// 	{ Key: 3, Value: "Orange"    }
// ]

Ici, la clé et la valeur sont transmises directement à leurs constructeurs de type respectifs. Bien que cela n'ait pas d'impact pour la clé int32, cela permet d'éviter la création d'un FString temporaire pour la valeur. Contrairement à TArray, il n'est possible d'insérer des éléments dans un mappage qu'avec des constructeurs à un seul argument.

Append

Vous pouvez fusionner deux mappages avec la fonction Append, qui déplace tous les éléments du mappage d'argument dans le mappage d'objet appelant :

TMap<int32, FString> FruitMap2;
FruitMap2.Emplace(4, TEXT("Kiwi"));
FruitMap2.Emplace(9, TEXT("Melon"));
FruitMap2.Emplace(5, TEXT("Mango"));
FruitMap.Append(FruitMap2);
// FruitMap == [
// 	{ Key: 5, Value: "Mango"     },
// 	{ Key: 2, Value: "Pear"      },
// 	{ Key: 7, Value: "Pineapple" },
// 	{ Key: 4, Value: "Kiwi"      },

Dans l'exemple ci-dessus, le mappage résultant équivaut à l'utilisation de Add ou Emplace pour ajouter chaque élément de FruitMap2 individuellement, ce qui permet de vider FruitMap2 une fois le processus terminé. Cela signifie que tout élément de FruitMap2 qui partage sa clé avec un élément déjà présent dans FruitMap remplace cet élément.

Si vous marquez le TMap 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'éditeur.

UPROPERTY(EditAnywhere, Category = MapsAndSets)
TMap<int32, FString> FruitMap;

Itérer

L'itération sur les TMaps est similaire aux TArrays. Vous pouvez utiliser la boucle for étendue de C++, en gardant à l'esprit que le type d'élément est un TPair :

for (auto& Elem : FruitMap)
{
	FPlatformMisc::LocalPrint(
		*FString::Printf(
			TEXT("(%d, \"%s\")\n"),
			Elem.Key,
			*Elem.Value
		)
	);
}

Vous pouvez créer des itérateurs avec les fonctions CreateIterator et CreateConstIterator.

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 exemple de FruitMap avec des itérateurs :

for (auto It = FruitMap.CreateConstIterator(); It; ++It)
{
	FPlatformMisc::LocalPrint(
		*FString::Printf(
			TEXT("(%d, \"%s\")\n"),
			It.Key(),   // same as It->Key
			*It.Value() // same as *It->Value
		)
	);
}

Get Value

Si vous savez que votre mappage contient une certaine clé, vous pouvez rechercher la valeur correspondante avec l'opérateur [], en utilisant la clé comme index. Faire cela avec un mappage non constant renvoie une référence non constante, tandis qu'un mappage constant renvoie une référence constante.

FString Val7 = FruitMap[7];
// Val7 == "Pineapple"
FString Val8 = FruitMap[8];
// Assert!

Query

Pour déterminer le nombre d'éléments présents dans un TMap, appelez la fonction Num :

int32 Count = FruitMap.Num();
// Count == 6

Pour déterminer si un mappage contient ou non une clé spécifique, appelez la fonction Contains :

bool bHas7 = FruitMap.Contains(7);
bool bHas8 = FruitMap.Contains(8);
// bHas7 == true
// bHas8 == false

Si vous ne savez pas si votre mappage 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 la texture contient la clé, ou un pointeur nul si ce n'est pas le cas. L'appel de Find sur un mappage constant renvoie un pointeur constant.

FString* Ptr7 = FruitMap.Find(7);
FString* Ptr8 = FruitMap.Find(8);
// *Ptr7 == "Pineapple"
//  Ptr8 == nullptr

Sinon, pour garantir un résultat valide à votre requête, vous pouvez utiliser FindOrAdd ou FindRef :

Étant donné que les fonctions FindOrAdd et FindRef réussissent même lorsque la clé n'est pas trouvée dans le mappage, vous pouvez les appeler en toute sécurité sans les procédures de sécurité habituelles telles que la vérification de Contains à l'avance ou la vérification de la valeur de retour.

FString& Ref7 = FruitMap.FindOrAdd(7);
// Ref7     == "Pineapple"
// FruitMap == [
// 	{ Key: 5, Value: "Mango"     },
// 	{ Key: 2, Value: "Pear"      },
// 	{ Key: 7, Value: "Pineapple" },
// 	{ Key: 4, Value: "Kiwi"      },
// 	{ Key: 3, Value: "Orange"    },
// 	{ Key: 9, Value: "Melon"     }
// ]

La fonction FindKey effectue une recherche inversée, ce qui signifie qu'une valeur fournie est associée à une clé, et renvoie un pointeur vers la première clé associée à la valeur fournie. La recherche d'une valeur qui n'est pas présente dans le mappage renvoie un pointeur nul.

const int32* KeyMangoPtr   = FruitMap.FindKey(TEXT("Mango"));
const int32* KeyKumquatPtr = FruitMap.FindKey(TEXT("Kumquat"));
// *KeyMangoPtr   == 5
//  KeyKumquatPtr == nullptr

Les fonctions GenerateKeyArray et GenerateValueArray remplissent un TArray avec une copie de toutes les clés et de toutes les valeurs, respectivement. Dans les deux cas, la matrice transmise est vidée avant le remplissage. Le nombre d'éléments qui en résulte est donc toujours égal au nombre d'éléments du mappage.

TArray<int32>   FruitKeys;
TArray<FString> FruitValues;
FruitKeys.Add(999);
FruitKeys.Add(123);
FruitMap.GenerateKeyArray  (FruitKeys);
FruitMap.GenerateValueArray(FruitValues);
// FruitKeys   == [ 5,2,7,4,3,9,8 ]
// FruitValues == [ "Mango","Pear","Pineapple","Kiwi","Orange",
//                  "Melon","" ]

Supprimer

Vous pouvez supprimer des éléments d'un mappage à l'aide de la fonction Remove et en fournissant la clé de l'élément à supprimer. La valeur de retour correspond au nombre d'éléments qui ont été supprimés. Elle peut être nulle si le mappage ne contenait aucun élément correspondant à la clé.

FruitMap.Remove(8);
// FruitMap == [
// 	{ Key: 5, Value: "Mango"     },
// 	{ Key: 2, Value: "Pear"      },
// 	{ Key: 7, Value: "Pineapple" },
// 	{ Key: 4, Value: "Kiwi"      },
// 	{ Key: 3, Value: "Orange"    },
// 	{ Key: 9, Value: "Melon"     }
// ]

La fonction FindAndRemoveChecked peut être utilisée pour supprimer un élément du mappage et renvoyer sa valeur. La mention "checked" dans le nom indique que le mappage effectue une vérification si la clé n'existe pas.

FString Removed7 = FruitMap.FindAndRemoveChecked(7);
// Removed7 == "Pineapple"
// FruitMap == [
// 	{ Key: 5, Value: "Mango"  },
// 	{ Key: 2, Value: "Pear"   },
// 	{ Key: 4, Value: "Kiwi"   },
// 	{ Key: 3, Value: "Orange" },
// 	{ Key: 9, Value: "Melon"  }
// ]

La fonction RemoveAndCopyValue est similaire à Remove, mais elle copie la valeur de l'élément supprimé dans un paramètre de référence. Si la clé que vous avez spécifiée n'est pas présente dans le mappage, le paramètre de sortie reste inchangé et la fonction renvoie false.

FString Removed;
bool bFound2 = FruitMap.RemoveAndCopyValue(2, Removed);
// bFound2  == true
// Removed  == "Pear"
// FruitMap == [
// 	{ Key: 5, Value: "Mango"  },
// 	{ Key: 4, Value: "Kiwi"   },
// 	{ Key: 3, Value: "Orange" },
// 	{ Key: 9, Value: "Melon"  }
// ]

Enfin, vous pouvez supprimer tous les éléments du mappage avec les fonctions Empty ou Reset.

TMap<int32, FString> FruitMapCopy = FruitMap;
// FruitMapCopy == [
// 	{ Key: 5, Value: "Mango"  },
// 	{ Key: 4, Value: "Kiwi"   },
// 	{ Key: 3, Value: "Orange" },
// 	{ Key: 9, Value: "Melon"  }
// ]

FruitMapCopy.Empty();		// You can also use Reset() here.
// FruitMapCopy == []

Trier

Vous pouvez trier un TMap par clé ou par valeur. Après le tri, l'itération sur le mappage présente les éléments dans un ordre ordonné, mais ce comportement n'est garanti que jusqu'à la prochaine modification du mappage. Le tri est instable, ce qui fait que les éléments équivalents d'un TMultiMap peuvent apparaître dans n'importe quel ordre.

Vous pouvez effectuer un tri par clé ou par valeur en utilisant respectivement les fonctions KeySort et ValueSort. Les deux fonctions utilisent un prédicat binaire qui spécifie l'ordre de tri.

FruitMap.KeySort([](int32 A, int32 B) {
	return A > B; // sort keys in reverse
});
// FruitMap == [
// 	{ Key: 9, Value: "Melon"  },
// 	{ Key: 5, Value: "Mango"  },
// 	{ Key: 4, Value: "Kiwi"   },
// 	{ Key: 3, Value: "Orange" }
// ]

Opérateurs

À l'instar de TArray, TMap 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 mappages étant propriétaires de leurs éléments, la copie d'un mappage est un processus complexe, et le nouveau mappage aura sa propre copie des éléments.

TMap<int32, FString> NewMap = FruitMap;
NewMap[5] = "Apple";
NewMap.Remove(3);
// FruitMap == [
// 	{ Key: 4, Value: "Kiwi"   },
// 	{ Key: 5, Value: "Mango"  },
// 	{ Key: 9, Value: "Melon"  },
// 	{ Key: 3, Value: "Orange" }
// ]
// NewMap == [

TMap prend en charge la sémantique de déplacement, qui peut être appelée à l'aide de la fonction MoveTemp. Après un déplacement, le mappage source est forcément vide :

FruitMap = MoveTemp(NewMap);
// FruitMap == [
// 	{ Key: 4, Value: "Kiwi"  },
// 	{ Key: 5, Value: "Apple" },
// 	{ Key: 9, Value: "Melon" }
// ]
// NewMap == []

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 au mappage 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 mappage qui doit se remplir immédiatement avec le même nombre d'éléments ou moins.

Dans le code ci-dessous, la fonction Reserve alloue de l'espace permettant au mappage de contenir jusqu'à dix éléments :

FruitMap.Reserve(10);
for (int32 i = 0; i < 10; ++i)
{
	FruitMap.Add(i, FString::Printf(TEXT("Fruit%d"), i));
}
// FruitMap == [
// 	{ Key: 9, Value: "Fruit9" },
// 	{ Key: 8, Value: "Fruit8" },
// 	...
// 	{ Key: 1, Value: "Fruit1" },

Pour supprimer toute marge d'un TMap, 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.

for (int32 i = 0; i < 10; i += 2)
{
	FruitMap.Remove(i);
}
// FruitMap == [
// 	{ Key: 9, Value: "Fruit9" },
// 	<invalid>,
// 	{ Key: 7, Value: "Fruit7" },
// 	<invalid>,
// 	{ Key: 5, Value: "Fruit5" },

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, utilisez d'abord la fonction Compact afin que les espaces vides soient regroupés en préparation de l'appel de la fonction Shrink.

FruitMap.Compact();
// FruitMap == [
// 	{ Key: 9, Value: "Fruit9" },
// 	{ Key: 7, Value: "Fruit7" },
// 	{ Key: 5, Value: "Fruit5" },
// 	{ Key: 3, Value: "Fruit3" },
// 	{ Key: 1, Value: "Fruit1" },
// 	<invalid>,
// 	<invalid>,
// 	<invalid>,

KeyFuncs

Tant qu'un type dispose d'un opérateur == et d'une surcharge GetTypeHash non membre, vous pouvez l'utiliser comme type de clé pour un TMap sans aucune autre modification. Toutefois, vous pouvez utiliser des types comme clés sans surcharger ces fonctions. Dans ce cas, vous pouvez fournir votre propre fonction KeyFuncs 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 et ElementInitType sont des définitions de type pour la convention de transmission normale du type de clé et du type d'é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 mappage est un TPair.

L'extrait de code suivant est un exemple de KeyFuncs personnalisée :

MyCustomKeyFuncs.cpp

struct FMyStruct
{
	// String which identifies our key
	FString UniqueID;

	// Some state which doesn't affect struct identity
	float SomeFloat;

	explicit FMyStruct(float InFloat)
		: UniqueID (FGuid::NewGuid().ToString())

FMyStruct comporte un identificateur unique ainsi que d'autres données qui ne contribuent pas à son identité. GetTypeHash et operator== ne conviendraient pas dans le cas présent, car operator== ne devrait ignorer aucune donnée du type pour un usage général, mais devrait simultanément le faire pour rester cohérent avec le comportement de GetTypeHash, qui ne prend en compte que le champ UniqueID.

Pour créer une KeyFuncs personnalisée pour FMyStruct, procédez comme suit :

1. Hériter de BaseKeyFuncs, car elle définit des types utiles, comme KeyInitType et ElementInitType.

   • BaseKeyFuncs accepte deux paramètres de modèle :

     1. Le type d'élément du mappage.

        • Comme pour tous les mappages, le type d'élément est un TPair. Il prend FMyStruct comme KeyType et le paramètre de modèle de TMyStructMapKeyFuncs comme son ValueType. La KeyFuncs de remplacement est un modèle. Vous pouvez donc spécifier un ValueType par mappage, au lieu de définir une nouvelle fonction KeyFuncs chaque fois que vous souhaitez créer un TMap incrusté dans FMyStruct.

     2. Le type de notre clé.

        • Le deuxième argument BaseKeyFuncs est le type de la clé. Il ne faut pas le confondre avec le KeyType de TPair, le champ Key des banques d'éléments. Puisque cet mappage doit utiliser UniqueID (de FMyStruct) comme clé, FString est utilisé ici.

2. Définissez les trois fonctions statiques KeyFuncs nécessaires.

   • La première est GetSetKey, qui renvoie la clé pour un type d'élément donné. Notre type d'élément est TPair et notre clé est UniqueID. La fonction peut donc renvoyer directement l'identifiant unique UniqueID.

   • La deuxième fonction statique est Matches, qui prend les clés de deux éléments récupérés par GetSetKey et les compare pour déterminer s'ils sont équivalents. Pour FString, le test d'équivalence standard (opérateur==) est insensible à la casse ; pour le remplacer par une recherche sensible à la casse, utilisez la fonction Compare() avec l'option de comparaison de casse appropriée.

   • La troisième fonction statique est GetKeyHash, qui prend une clé extraite et renvoie une valeur de hachage correspondante. La fonction Matches étant sensible à la casse, GetKeyHash doit l'être également. Une fonction FCrc sensible à la casse calcule la valeur de hachage à partir de la chaîne de clé.

3. Maintenant que la structure prend en charge les comportements requis par TMap, vous pouvez en créer des instances.

   C++

   TMap<
            FMyStruct,
            int32,
            FDefaultSetAllocator,
            TMyStructMapKeyFuncs<int32>
        > MyMapToInt32;
   		
        // Add some elements
        MyMapToInt32.Add(FMyStruct(3.14f), 5);
        MyMapToInt32.Add(FMyStruct(1.23f), 2);
   
   Expand code Copy full snippet(26 lines long)

   Dans cet exemple, l'allocateur défini par défaut est spécifié. Ceci est dû au fait que le paramètre KeyFuncs vient en dernier et que ce type de TMap l'exige.

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 du mappage. Cette fonction est généralement utilisée pour le débogage.