UE_C++ —— Container TMap
目录
一,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
- TMap
- TMultiMap
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
可修改映射,因此仅适用于非常量映射;
- 如map中不存在该键,
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
,并写出关于映射内容的实现信息;此函数常用于调试;