今天来学学LRU在UE5.6引擎里的实现，之前会写大致的LRU算法，也没太关注内存有没有泄漏什么的。顺带学学C++的RAII，深入理解一下。

代码文件在此：

1
Engine/Source/Runtime/Core/Public/Containers/LRUCache.h

一点一点看吧。

首先，这份代码先写了一个TLruCache的键比较器模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Default comparer for keys in TLruCache.
 *
 * @param KeyType The type of keys to compare.
 */
template<typename KeyType>
struct DefaultKeyComparer
{
	[[nodiscard]] static FORCEINLINE bool Matches(KeyType A, KeyType B)
	{
		return (A == B);
	}

	/** Calculates a hash index for a key. */
	[[nodiscard]] static FORCEINLINE uint32 GetKeyHash(KeyType Key)
	{
		return GetTypeHash(Key);
	}
};

Matches(KeyType A, KeyType B)主要判断两个键是否相等。[[nodiscard]]是C++17的属性，提醒用户必须使用返回值。FORCEINLINE就是UE的宏，如其名，强制内联以提升性能。这里用了return (A == B);也就是说KeyType类型必须实现==比较运算符。

GetKeyHash就是计算键的哈希值。

然后进入正题，TLruCache。首先把一堆接口函数折叠起来，看看私有成员：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class TLruCache
{
public:...
public:...
public:...
protected:...
public:...
private:
	/** Set of entries for fast lookup. */
	TSet<FCacheEntry*, FKeyFuncs> LookupSet;

	/** Least recent item in the cache. */
	FCacheEntry* LeastRecent;

	/** Most recent item in the cache. */
	FCacheEntry* MostRecent;

	/** Maximum number of elements in the cache. */
	int32 MaxNumElements;

}

先了解一下私有成员：LookupSet就是一个哈希表，用来存储FCacheEntry*指针。LeastRecent应该就是指向最旧条目的那个指针。MostRecent就是最新的了。至于FCacheEntry为什么起这名呢？一会翻到了再看。

类的开头就是FCacheEntry结构体的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/** An entry in the LRU cache. */
	struct FCacheEntry
	{
		/** The entry's lookup key. */
		KeyType Key;

		/** The less recent entry in the linked list. */
		FCacheEntry* LessRecent;

		/** The more recent entry in the linked list. */
		FCacheEntry* MoreRecent;

		/** The entry's value. */
		ValueType Value;

		/**
		 * Create and initialize a new instance.
		 *
		 * @param InKey The entry's key.
		 * @param InValue The entry's value.
		 */
		[[nodiscard]] FCacheEntry(const KeyType& InKey, const ValueType& InValue)
			: Key(InKey)
			, LessRecent(nullptr)
			, MoreRecent(nullptr)
			, Value(InValue)
		{
		}

		/**
		 * Create a new instance with a default key value.
		 *
		 * @param InKey The entry's key.
		 */
		[[nodiscard]] FCacheEntry(const KeyType& InKey)
			: Key(InKey)
			, LessRecent(nullptr)
			, MoreRecent(nullptr)
		{
		}


		/** Add this entry before the given one. */
		FORCEINLINE void LinkBefore(FCacheEntry* Other)
		{
			LessRecent = Other;

			if (Other != nullptr)
			{
				Other->MoreRecent = this;
			}
		}

		/** Remove this entry from the list. */
		FORCEINLINE void Unlink()
		{
			if (LessRecent != nullptr)
			{
				LessRecent->MoreRecent = MoreRecent;
			}

			if (MoreRecent != nullptr)
			{
				MoreRecent->LessRecent = LessRecent;
			}

			LessRecent = nullptr;
			MoreRecent = nullptr;
		}
	};

	/** Lookup set key functions. */
	struct FKeyFuncs : public BaseKeyFuncs<FCacheEntry*, KeyType>
	{
		[[nodiscard]] FORCEINLINE static const KeyType& GetSetKey(const FCacheEntry* Entry)
		{
			return Entry->Key;
		}

		[[nodiscard]] FORCEINLINE static bool Matches(KeyType A, KeyType B)
		{
			return KeyComp::Matches(A, B);
		}

		[[nodiscard]] FORCEINLINE static uint32 GetKeyHash(KeyType Key)
		{
			return KeyComp::GetKeyHash(Key);
		}
	};

先看 FCacheEntry 结构体。它是一个双向链表节点，包含四个成员：Key 和 Value 存储键值对数据；LessRecent 和 MoreRecent 是两个指针，用于链接节点。LessRecent 指向时间更早的节点（类似平常写的pre，next指针），MoreRecent 指向时间更晚的节点。链表的方向是从最新到最旧，每个节点通过这两个指针形成双向链接。

结构体提供了两个构造函数。第一个构造函数同时接收键和值，用于完整初始化条目，链表指针都设为 nullptr。第二个构造函数只接收键，用于需要延迟初始化值的场景（如 AddUninitialized_GetRef），此时值会使用默认构造或由调用者后续设置。

LinkBefore 方法将当前节点插入到指定节点之前。它先设置当前节点的 LessRecent 指向目标节点，如果目标节点存在，再将目标节点的 MoreRecent 指向当前节点。这样就把当前节点插入到了更靠近链表头部的位置。需要注意，这里只建立了局部连接，如果当前节点原本在链表中的其他位置，调用前通常需要先调用 Unlink 断开原有连接。

Unlink 方法将当前节点从双向链表中移除。它先检查前驱和后继节点，如果前驱存在，将前驱的 MoreRecent 指向当前节点的后继；如果后继存在，将后继的 LessRecent 指向当前节点的前驱。这样即使移除了当前节点，链表的其他部分仍然保持连接。最后将当前节点的两个指针都设为 nullptr，完成解除链接。上面这个插入删除操作就是链表结点的插入删除，没有什么高深的地方。只不过，这种操作在面试写的时候都是把插入删除方法封装在Node结点外面的，这里直接放在了结点的Struct里面，通过传递指针完成操作。

接下来是 FKeyFuncs 结构体，它继承自 BaseKeyFuncs<FCacheEntry*, KeyType>。这个适配器的作用是让 TSet 能够存储 FCacheEntry* 指针，同时使用 KeyType 作为查找键。TSet 需要从存储的元素中提取键，但存储的是指针类型，查找用的是键类型，所以需要这个适配器来桥接。

FKeyFuncs 提供了三个静态方法。GetSetKey 方法从 FCacheEntry* 指针中提取键，直接返回 Entry->Key，这样 TSet 就知道如何从存储的指针中获取键了。Matches 方法比较两个键是否相等，它委托给模板参数 KeyComp 的 Matches 方法，这样支持了自定义键比较逻辑。GetKeyHash 方法计算键的哈希值，同样委托给 KeyComp 的 GetKeyHash 方法，用于哈希表的定位和查找。

当 TSet 需要查找某个键时，它会使用 FKeyFuncs 来进行操作。TSet 遍历哈希桶中的 FCacheEntry* 指针，对每个指针调用 GetSetKey 得到对应的键，然后调用 Matches 方法比较该键与查找的键是否相等。如果相等就返回该指针。这样 TSet 就能存储指针类型，但用键类型进行查找，实现了类型转换的适配。

LRU所需的数据结构如上，定义完毕。

先把第一个public翻开，看看里面是什么：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public:

	/** Default constructor (empty cache that cannot hold any values). */
	[[nodiscard]] TLruCache()
		: LeastRecent(nullptr)
		, MostRecent(nullptr)
		, MaxNumElements(0)
	{
	}

	/**
	 * Create and initialize a new instance.
	 *
	 * @param InMaxNumElements The maximum number of elements this cache can hold.
	 */
	[[nodiscard]] TLruCache(int32 InMaxNumElements)
		: LeastRecent(nullptr)
		, MostRecent(nullptr)
		, MaxNumElements(InMaxNumElements)
	{
		Empty(InMaxNumElements);
	}

	/** Destructor. */
	~TLruCache()
	{
		Empty();
	}

构造函数和析构函数都比较好理解，就不展开看了。

再下面就是各种插入删除结点的接口，实现的思路和平常一样。

用工业级的代码与我们平常写的做一个对比。平常面试写的时候，类型单一，限制很多。见：https://leetcode.cn/problems/lru-cache-lcci/description/

简易LRU实现将键类型固定为 int，UE引擎的LRU缓存采用模板设计，KeyType 可以是任意类型。这是适配器存在的原因之一，但不是唯一原因。

简易实现使用 unordered_map<int, Node*>，哈希表直接以 int 作为键进行存储和查找，类型匹配，无需额外转换。即便改为模板类以支持多种键类型，例如 unordered_map<KeyType, Node*>，类型仍然匹配，因为键类型就是模板参数，哈希表可以直接处理。

UE引擎的实现采用了不同的设计。它使用 TSet<FCacheEntry*, FKeyFuncs>，哈希表中存储的是 FCacheEntry* 指针，但查找时使用的是 KeyType，从而造成类型不匹配：存储的是指针类型，查找传入的是键类型，两者在类型系统上无法直接对应。为解决这个问题，UE 引入了 FKeyFuncs 适配器。适配器提供 GetSetKey 方法，告知哈希表如何从存储的 FCacheEntry* 指针中提取 KeyType 类型的键。当调用 LookupSet.Find(Key) 时，哈希表会遍历存储的指针，对每个指针调用 GetSetKey 提取键，再与传入的键比较，从而找到匹配的条目。

除了解决类型不匹配问题，适配器还承担了支持模板灵活性的职责。由于 UE 的 LRU 缓存是模板类，KeyType 可以是 int、string、自定义结构体等任意类型。不同键类型可能需要不同的比较和哈希方式，因此适配器还提供 Matches 和 GetKeyHash 方法，这些方法委托给模板参数 KeyComp 处理，使得可以自定义键类型的比较和哈希逻辑。这种设计虽然增加了代码复杂度，但提供了更大的灵活性，能够适应各种不同的键类型和使用场景。

总结来说，适配器的存在主要源于两个因素：一是存储指针但用键查找导致的类型不匹配问题，二是模板设计带来的类型灵活性需求。即使简易版本改成模板支持多种键类型，只要使用 unordered_map<KeyType, Node*> 这种类型匹配的设计仍然不需要适配器。UE 版本需要适配器主要是因为它选择了“存储指针 + 用键查找”这种设计模式，这种模式在提供灵活性的同时也带来了类型系统上的挑战，适配器就是用来解决这些问题。

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~