UE_C++——ContainerTMap

目录

一，Types of Maps in Unreal Engine

二，Create and Fill a Map

Add

Emplace

Append

三，Iterate

四，Get Value

五，Query

六，Remove

七，Sort

八，Operators

九，Slack

十一，KeyFuncs

十二，Miscellaneous

---

        TMap 由键值对定义，是 TArray 后最常用的容器；类似 TSet，结构均基于对键进行散列运算；与 TSet 不同，将数据存储为键值对（TPair<KeyType, ValueType>），只将键用于存储和获取；

一，Types of Maps in Unreal Engine TMapTMultiMap

TMap

在 TMap 中，键值对被视为其元素类型；元素就意味着键值对，而各个组件就被称作元素的键或元素的值；元素类型实际上是 TPair<KeyType, ElementType>，但很少需要直接引用 TPair 类型；在 TMap 中，键是唯一的；类似 TArray，TMap 也是同质容器，所有元素的类型都完全相同；TMap 是值类型，支持通常的复制、赋值和析构函数运算，以及元素的强所有权；在被销毁时，元素都会被销毁；键和值也必须为值类型；TMap 是哈希容器，意味着键类型必须支持 GetTypeHash 函数，并提供 operator== 来比较各个键是否等值；

TMultiMap

支持存储多个相同的键；当向TMap添加新的与现有键值对匹配的键值对时，新键值对将替换旧键值对；在TMultiMap中，容器对新旧键值对都会存储；

        TMap 可使用可选的分配器来控制内存分配行为；但不同于 TArray，这些是set分配器，而不是 FHeapAllocator 和 TInlineAllocator 之类的标准UE分配器；set分配器（TSetAllocator类）定义map应使用的散列桶数量，以及应使用哪个标准UE分配器来存储散列和元素；

        KeyFuncs 是最后一个 TMap 模板参数，该参数告知map如何从元素类型获取键，如何比较两个键是否相等，以及如何对键进行散列计算；这些参数有默认值，只会返回对键的引用，使用 operator== 确定相等性，并调用非成员 GetTypeHash 函数进行散列计算；如果键类型支持这些函数，可使用它作为映射键，不需要提供自定义 KeyFuncs；

        与 TArray 不同的是，内存中 TMap 元素的相对排序既不可靠也不稳定，对这些元素进行迭代很可能会使它们返回的顺序和它们添加的顺序有所不同；这些元素也不太可能在内存中连续排列；        

        map的基础数据结构是稀疏数组，这种数组可有效支持元素之间的空位；当元素从map中移除时，稀疏数组中就会出现空位；将新的元素添加到数组可填补这些空位；但是，即便 TMap 不会打乱元素来填补空位，指向map元素的指针仍然可能失效，因为如果存储器被填满，又添加了新的元素，整个存储可能会重新分配；

二，Create and Fill a Map TMap<int32, FString> FruitMap;

        FruitMap 是一个字符串的空 TMap，该字符串由整数键标识；既没有指定分配器，也没有指定 KeyFuncs，所以映射将执行标准的堆分配，使用 operator== 对键进行对比（int32 类型），并使用 GetTypeHash 对键进行散列运算；此时没有分配任何内存；

Add

        填充map的标准方法是调用带有键和值的 Add 函数；

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" } // ]

注，此处的元素按插入顺序排列，但不保证这些元素在内存中实际排序；如是新的map，可能会保留插入排序，但插入和删除的次数越多，新元素不出现在末尾的可能性就越大；

        这不是 TMultiMap，所以各个键都必定是唯一；如尝试添加重复键，map替换旧值；

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

        Add 函数可接受不带值的键，调用此重载后的 Add，值将被默认构建；

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

        和 TArray 一样，可使用 Emplace 代替 Add，防止插入映射时创建临时文件；

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" } // ]

        此处直接将键和值传递给了各自的构造函数；这对 int32 键实际上没有影响，但避免了为该值创建临时 FString；与 TArray 不同的是，只能通过单一参数构造函数将元素安放到map中；

Append

        可使用 Append 函数合并两个map，将一个map的所有元素移至另一个映射；

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" }, // { Key: 3, Value: "Orange" }, // { Key: 9, Value: "Melon" } // ] // FruitMap2 is now empty.

        结果map和使用 Add 或 Emplace 逐个添加 FruitMap2 的元素相同，在该过程完成时会清空 FruitMap2；这意味着如果 FruitMap2 中任何元素的键与 FruitMap 中原有元素的键相同，就会取代该元素；

        如用 UPROPERTY 宏和一个可编辑的关键词（EditAnywhere、EditDefaultsOnly 或 EditInstanceOnly）标记 TMap，即可在编辑器中添加并编辑元素；

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

        TMaps 的迭代类似于 TArrays，可使用C++的范围for，注意元素类型是 TPair；

for (auto& Elem : FruitMap) { FPlatformMisc::LocalPrint( *FString::Printf( TEXT("(%d, \"%s\")\n"), Elem.Key, *Elem.Value ) ); } // Output: // (5, "Mango") // (2, "Pear") // (7, "Pineapple") // (4, "Kiwi") // (3, "Orange") // (9, "Melon")

        可使用 CreateIterator 和 CreateConstIterators 函数来创建迭代器，均可用这些迭代器的 Key 和 Value 来检查元素；

CreateIterator 返回拥有读写访问权限的迭代器；CreateConstIterator 返回拥有只读访问权限的迭代器； 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

        如已知道map包含特定的key，可使用 operator[] 来查看对应的值，使用key作为索引；非常量map返回非常量引用，常量map返回常量引用；

注，在使用 operator[] 前应该检查key，如没有指定的key会assert；

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

        调用 Num 函数可查询map中保存的元素数量；

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

        调用 Contains 函数可检查map是否包含特定key；如不确定是否包含指定键，可使用contains函数进行检查，然后使用 operator[]；然而，这是次优的，因为成功的检索涉及对同一关键字的两次查找；

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

        使用 Find 函数查找一次即可完成这些行为；如map包含该键，Find 将返回指向该元素数值的指针；如map不包含该键，则返回null；在常量map上调用 Find，返回的指针也将为常量；

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

        为确保查询的结果有效，可使用 FindOrAdd 或 FindRef；

FindOrAdd 将返回给定键关联的值的引用； 如map中不存在该键，FindOrAdd 将返回新创建的元素（使用给定键和默认构建值），该元素也会被添加到map；FindOrAdd 可修改映射，因此仅适用于非常量映射； FindRef 返回与给定键关联的值副本（不要被名称迷惑）； 若map中未找到给定键，则返回默认构建值；FindRef 不会创建新元素，因此既可用于常量映射，也可用于非常量映射；

        即使在映射中找不到键，FindOrAdd 和 FindRef 也会成功运行，因此无需执行常规的安全规程（如提前检查 Contains 或对返回值进行空白检查）就可安全地调用；

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" } // ] FString& Ref8 = FruitMap.FindOrAdd(8); // Ref8 == "" // 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" }, // { Key: 8, Value: "" } // ] FString Val7 = FruitMap.FindRef(7); FString Val6 = FruitMap.FindRef(6); // Val7 == "Pineapple" // Val6 == "" // 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" }, // { Key: 8, Value: "" } // ]

注，FindOrAdd 可向映射添加新条目，因此之前获得的指针（来自 Find）或引用（来自 FindOrAdd）可能会无效；如map的后端存储需要扩展以容纳新元素，会执行分配内存和移动现有数据的添加操作，会导致这一结果；

        FindKey 函数执行逆向查找，这意味着提供的值与键匹配，并返回指向与所提供值配对的第一个键的指针；搜索不存在的值将返回空指针；

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

注，按值查找比按键查找慢（线性时间），这是因为map是根据键而不是值进行哈希；此外，如map有多个具有相同值的键，FindKey 可返回其中任一键；

        GenerateKeyArray 和 GenerateValueArray 分别使用所有键和值的副本来填充 TArray；在这两种情况下，都会在填充前清空所传递的数组，因此产生的元素数量始终等于映射中的元素数量；

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","" ] 六，Remove

        从map中移除元素的方法是使用 Remove 函数并提供要移除元素的键，返回值是被移除元素的数量；如果map不包含与键匹配的元素，则返回值可为零；

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" } // ]

注，移除元素将在数据结构中留下空位，但为保证清晰度，此处省略；

        FindAndRemoveChecked 函数可用于从映射移除元素并返回其值；名称的"已检查"部分表示若键不存在，map将调用 check；

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" } // ] FString Removed8 = FruitMap.FindAndRemoveChecked(8); // Assert!

        RemoveAndCopyValue 函数的作用与 Remove 相似，不同点是会将已移除元素的值复制到引用参数；如不存在指定的键，则输出参数将保持不变，函数将返回 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" } // ] bool bFound8 = FruitMap.RemoveAndCopyValue(8, Removed); // bFound8 == false // Removed == "Pear", i.e. unchanged // FruitMap == [ // { Key: 5, Value: "Mango" }, // { Key: 4, Value: "Kiwi" }, // { Key: 3, Value: "Orange" }, // { Key: 9, Value: "Melon" } // ]

        使用 Empty 或 Reset 函数可将map中的所有元素移除；

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 == []

注，Empty 和 Reset 相似，但 Empty 可采用参数指示映射中保留的slack量，而 Reset 则是尽可能多地留出slack量；

七，Sort

       可通过键或值对 TMap 进行排序。排序后，迭代会以排序的顺序显示元素，但下次修改map时，排序可能会发生变化；排序是不稳定的，因此等值元素在MultiMap中可能以任何顺序出现；

        使用 KeySort 或 ValueSort 函数可分别按键和值进行排序，两个函数均使用二元谓词来进行排序；

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" } // ] FruitMap.ValueSort([](const FString& A, const FString& B) { return A.Len() < B.Len(); // sort strings by length }); // FruitMap == [ // { Key: 4, Value: "Kiwi" }, // { Key: 5, Value: "Mango" }, // { Key: 9, Value: "Melon" }, // { Key: 3, Value: "Orange" } // ] 八，Operators

        和 TArray 一样，TMap 是常规值类型，可通过标准拷贝构造函数或赋值运算符进行复制；因为map严格拥有其元素，所以是深拷贝，新map将拥有其自己的元素副本；

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 == [ // { Key: 4, Value: "Kiwi" }, // { Key: 5, Value: "Apple" }, // { Key: 9, Value: "Melon" } // ]

        TMap 支持移动语义，使用 MoveTemp 函数可调用这些语义；在移动后，源map会为空；

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

        Slack是不包含元素的已分配内存；调用 Reserve 在不添加元素时，分配内存；通过非零slack参数调用 Reset 或 Empty 可移除元素，无需取消内存分配；Slack优化了将新元素添加到映射的过程，因为可以使用预先分配的内存，而不必分配新内存；它在移除元素时也十分实用，因为系统不需要取消内存分配；在清空希望用相同或更少的元素立即重新填充map时，此方法尤其有效；

注，TMap 不像 TArray 中的 Max 函数那样可以检查预分配元素的数量；

        Reserve 函数预先分配map；

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" }, // { Key: 0, Value: "Fruit0" } // ]

        使用 Collapse 和 Shrink 函数可移除 TMap 中的全部slack；Shrink 将从容器的末端移除所有slack，但这会在中间或开始处留下空白元素；

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" }, // <invalid>, // { Key: 3, Value: "Fruit3" }, // <invalid>, // { Key: 1, Value: "Fruit1" }, // <invalid> // ] FruitMap.Shrink(); // FruitMap == [ // { Key: 9, Value: "Fruit9" }, // <invalid>, // { Key: 7, Value: "Fruit7" }, // <invalid>, // { Key: 5, Value: "Fruit5" }, // <invalid>, // { Key: 3, Value: "Fruit3" }, // <invalid>, // { Key: 1, Value: "Fruit1" } // ]

        对于 Shrink 要移除所有slack，首先应调用 Compact 函数，将空白空间组合在一起，为调用 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>, // <invalid> // ] FruitMap.Shrink(); // FruitMap == [ // { Key: 9, Value: "Fruit9" }, // { Key: 7, Value: "Fruit7" }, // { Key: 5, Value: "Fruit5" }, // { Key: 3, Value: "Fruit3" }, // { Key: 1, Value: "Fruit1" } // ] 十一，KeyFuncs

        只要类型具有 operator== 和非成员 GetTypeHash 重载，即可用作 TMap 的键类型；但是，可能需要将类型用作键，而不重载这些函数；在这些情况下，可对 KeyFuncs 进行自定义；为键类型创建 KeyFuncs，必须定义两个typedef和三个静态函数；

typedef：

KeyInitType —— 用于传递键的类型；ElementInitType —— 用于传递元素的类型；

静态函数：

KeyInitType GetSetKey(ElementInitType Element)——返回元素的键；bool Matches(KeyInitType A, KeyInitType B) —— 如果 A 和 B 等值将返回 true，否则返回 false；uint32 GetKeyHash(KeyInitType Key) —— 返回 Key 的散列值；

        KeyInitType 和 ElementInitType 是键类型和值类型的常规传递约定的typedef；它们通常为浅显类型的一个值，和非浅显类型的一个常量引用；请记住，map的元素类型是 TPair；

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()) , SomeFloat(InFloat) { } }; template <typename ValueType> struct TMyStructMapKeyFuncs : BaseKeyFuncs< TPair<FMyStruct, ValueType>, FString > { private: typedef BaseKeyFuncs< TPair<FMyStruct, ValueType>, FString > Super; public: typedef typename Super::ElementInitType ElementInitType; typedef typename Super::KeyInitType KeyInitType; static KeyInitType GetSetKey(ElementInitType Element) { return Element.Key.UniqueID; } static bool Matches(KeyInitType A, KeyInitType B) { return A.Compare(B, ESearchCase::CaseSensitive) == 0; } static uint32 GetKeyHash(KeyInitType Key) { return FCrc::StrCrc32(*Key); } };

        FMyStruct 具有唯一标识符，以及一些与身份无关的其他数据；GetTypeHash 和 operator== 不适用于此，因为 operator== 为实现通用目的不应忽略任何类型的数据，但同时又需要如此才能与 GetTypeHash 的行为保持一致，后者只关注 UniqueID 字段；以下步骤有助于为 FMyStruct 创建自定义 KeyFuncs：

首先，继承 BaseKeyFuncs，因为它可以帮助定义某些类型，包括 KeyInitType 和 ElementInitType；

BaseKeyFuncs 使用两个模板参数：

map元素类型；和所有映射一样，元素类型是 TPair，使用 FMyStruct 作为其 KeyType，TMyStructMapKeyFuncs 的模板参数作为其 ValueType；将备用 KeyFuncs 用作模板，可为每个映射指定 ValueType，因此每次要在 FMyStruct 上创建键控 TMap 时不必定义新的 KeyFuncs；第二个 BaseKeyFuncs 参数是键类型，不要与元素存储的键区（TPair 的 KeyType）混淆；因为此映射应使用 UniqueID（来自 FMyStruct）作为键，所以此处使用 FString；

然后，定义三个必需的 KeyFuncs 静态函数；

第一个是 GetSetKey，该函数返回给定元素类型的键；由于元素类型是 TPair，而键是 UniqueID，所以该函数可直接返回 UniqueID；

第二个静态函数是 Matches，该函数接受两个元素的键（由 GetSetKey 获取），然后比较它们是否相等；在 FString 中，标准的等效测试（运算符==）不区分大小写；要替换为区分大小写的搜索，请用相应的大小写对比选项使用 Compare 函数；

最后，GetKeyHash 静态函数接受提取的键并返回其散列值；由于 Matches 函数区分大小写，GetKeyHash 也必须区分大小写；区分大小写的 FCrc 函数将计算键字符串的散列值；

现在结构已满足 TMap 要求的行为，可创建它的实例。

TMap< FMyStruct, int32, FDefaultSetAllocator, TMyStructMapKeyFuncs<int32> > MyMapToInt32; // Add some elements MyMapToInt32.Add(FMyStruct(3.14f), 5); MyMapToInt32.Add(FMyStruct(1.23f), 2); // MyMapToInt32 == [ // { // Key: { // UniqueID: "D06AABBA466CAA4EB62D2F97936274E4", // SomeFloat: 3.14f // }, // Value: 5 // }, // { // Key: { // UniqueID: "0661218447650259FD4E33AD6C9C5DCB", // SomeFloat: 1.23f // }, // Value: 5 // } // ]

注，在自行设置KeyFuncs时，要注意 TMap 假设两个项目使用 Matches 比较的结果相等，则它们会从 GetKeyHash 返回相同的值；此外，如对现有映射元素的键进行的修改将会改变来自这两个函数中任一个的结果，那么系统会将这种修改视作未定义的行为，因为这会使映射的内部散列失效；这些规则也适用于使用默认 KeyFuncs 时 运算符== 和 GetKeyHash 的重载；

十二，Miscellaneous

        CountBytes 和 GetAllocatedSize 函数用于估计内部数组的当前内存使用情况；CountBytes 接受 Farchive 参数，而 GetAllocatedSize 则不会；这些函数常用于统计报告；Dump 函数接受 FOutputDevice，并写出关于映射内容的实现信息；此函数常用于调试；