std::list splice 简介
splice函数通过重新排列链表指针，将一个std::list中的节点转移到另一个std::list中。在元素的转移过程中不会触发元素的拷贝或者移动。因此，调用splice函数之后，元素现有的引用和迭代器都不会失效。
下面是一个将listA中所有节点附加到listB的一个简单代码示例，转移的过程不会导致listA中元素的引用和迭代器失效:
1// Note: c++17 required below. (For CTAD(Class template argument deducation))
2std::list listA{1, 2, 3};
3std::list listB{4, 5, 6};
4
5auto it = listA.begin(); // Iterator to 1
6
7// Append listA to listB
8listB.splice(listB.end(), listA);
9
10// All listA elements transferred to listB
11std::cout << listB.size() << " " << listA.size() << std::endl; // 6 0
12
13// Prints Below: 4 5 6 1 2 3
14for (auto i : listB) {
15 std::cout << i << " ";
16}
17std::cout << std::endl;
18
19// Iterator still valid
20std::cout << *it << std::endl; // 1
当然，我们也可以在不使用splice的情况下将一个 list 中的元素转移到另一个 list 中，但是需要将原 list 中的元素删除，并在目标 list 中插入新的元素。删除和新增元素对于较小的对象（例如 int）是可以接受的，但是对于较大的对象来说，由于需要调用拷贝/移动构造和析构函数，所以成本会很高。
splice函数有一些重载，用于传输所有节点、或者特定节点或者一系列节点。这些函数可以将节点从一个列表转移到另一个列表，或者修改节点在列表中的位置。除了将一系列节点（并非所有）从一个列表转移到另一个列表这一种情况，其他所有情况下splice函数的时间复杂度均为常数 O(1)。
splice 的另一个值得注意的特性是，我们可以将一个节点从列表的一个位置转移到该列表的另一个位置。而后面我们实现 LRU Cache 就是需要使用到这个特性。
1std::list<std::string> strList{"A", "B", "C"};
2// Transfers "C" to the front (before "A")
3strList.splice(strList.begin(), strList, --strList.end());
4// Prints below: C A B
5for (auto& str : strList) {
6 std::cout << str << " ";
7}
LRU Cache
Least Recently Used (LRU) Cache，最近最少使用缓存，是一种容量有限的缓存，它会丢弃最近最少使用的元素，以便在容量已满时为新的元素腾出空间。
接下来我们将要创建一个通用的 KV LRU Cache，他可以添加 KV，也可以通过给定的 K 来检索，以及删除特定的元素。无论是添加元素，检索元素还是删除元素，这些操作的平均时间复杂度都应为常数 O(1)。
设计
我们通常将缓存等同于哈希表+淘汰策略。虽然看上去有点简单粗暴，但是也不无道理。缓存的实现需要有一个能够加快检索的索引结构，在这里我们可以使用 hashmap 来作为键值对的索引，用于提升检索的时间复杂度。然而 LRU Cache 还有一个隐含的淘汰策略，那就是顺序，根据最近的使用情况来排列元素项，并进行相应的淘汰。 因此，我们将在这里使用两种数据结构来实现：链表和 hashmap。
链表按照最近使用顺序存储键值对，hashmap 用来构建索引。
最近使用的元素项是链表的第一个节点，最近最少使用的元素项是链表的最后一个节点。我们在列表前面添加一个新的元素项，如果缓存已满，则删除链表最后一个元素（淘汰最近最少访问的元素）。当一个元素被访问时，他会被转移到链表的前面。
实现
我们分别使用std::list和std::unordered_map来作为链表和哈希表，实现 LRU Cache:
1// Note: c++17 required.
2
3template<typename K, typename V, std::size_t Capacity> class LRUCache
4{
5public:
6 // Assert that Max size is greater than 0
7 static_assert(Capacity > 0);
8
9 // Adds a <key, Val> item, Returns false if key already exists
10 bool put(const K& k, const V& v);
11
12 // Gets the value for a key.
13 // Returns empty std::optional if not found.
14 // The returned item becomes most-recently-used
15 std::optional<V> get(const K& k);
16
17 // Erases an item
18 void erase(const K& k);
19
20 // Utility function.
21 // Calls callback for each {key, value}
22 template<typename C> void forEach(const C& cb) const
23 {
24 for (auto& [k, v] : items) {
25 cb(k, v);
26 }
27 }
28
29private:
30 // std::list stores items (pair<K, V>) in most-recently-used to least-recently-used order
31 std::list<std::pair<K, V>> items;
32
33 // unordered_map acts as an index to the items store above.
34 std::unordered_map<K, typename std::list<std::pair<K, V>>::iterator> index;
35};
put方法用于添加一个键值对。为了简单起见，如果 key 已经存在了，那么他什么都不做，并返回 false。如果缓存已经满了，那么会删除列表中最后一项(LRU)。最后新的键值对总是被添加到列表的最前面，同时索引会更新：
1template<typename K, typename V, std::size_t Capacity>
2bool LRUCache<K, V, Capacity>::put(const K& k, const V& v)
3{
4 // Return false if the key already exists
5 if (index.count(k)) {
6 return false;
7 }
8
9 // Check if cache is full
10 if (items.size() == Capacity) {
11 // Delete the LRU item
12 index.erase(items.back().first); // Erase the last item key from the map
13 items.pop_back(); // Evict last item from the list
14 }
15
16 // Insert the new item at front of the list
17 items.emplace_front(k, v);
18
19 // Insert {Key->item_iterator} in the map
20 index.emplace(k, items.begin());
21
22 return true;
23}
get方法返回给定键的值。这里使用了std::optional，他可以为一个值，也可以为空，这取决于是否找到该项。在返回找到的值之前，通过调用splice函数，将当前查询的项转移到列表的开始位置。这个splice操作具有恒定的时间复杂度，不设及到元素的拷贝或者移动：
1template<typename K, typename V, std::size_t Capacity>
2std::optional<V> LRUCache<K, V, Capacity>::get(const K& k)
3{
4 auto itr = index.find(k);
5 if (itr == index.end()) {
6 // empty std::optional
7 return {};
8 }
9
10 // Use list splice to transfer this item to the first position,
11 // which makes the item most-recently-used. Iterators still stay valid
12 items.splice(items.begin(), items, itr->second);
13
14 // Return the value in a std::optional
15 return itr->second->second;
16}
erase方法是最简单的一个，只需要将找到的元素从链表和哈希表中删除即可：
1template<typename K, typename V, std::size_t Capacity>
2void LRUCache<K, V, Capacity>::erase(const K& k)
3{
4 auto itr = index.find(k);
5 if (itr == index.end()) {
6 return;
7 }
8
9 // Erase from the list
10 items.erase(itr->second);
11
12 // Erase from the map
13 index.erase(itr);
14}
测试
我们使用下面的代码来对上面实现的LRUCache进行测试：
1// Prints all items of an LRUCache in a line
2// Items are printed in MRU -> LRU order
3template<typename C> void printlnCache(const C& cache)
4{
5 cache.forEach([](auto& k, auto& v) { std::cout << k << "=>" << v << " "; });
6 std::cout << std::endl;
7}
8
9int main()
10{
11 // City -> Population in millions (Max size 3)
12 LRUCache<std::string, double, 3> cache;
13
14 // Add 3 entries
15 cache.put("London", 8.4);
16 cache.put("Toronto", 2.5);
17 cache.put("Sydney", 5.2);
18
19 // Sydney=>5.2 Toronto=>2.5 London=>8.4
20 printlnCache(cache);
21
22 // Make "London" the most recently accessed
23 std::cout << "London =>" << cache.get("London").value_or(-1) << std::endl;
24
25 // London=>8.4 Sydney=>5.2 Toronto=>2.5
26 printlnCache(cache);
27
28 // This would remove the LRU item (Toronto)
29 cache.put("Tokyo", 9.4);
30
31 // Tokyo=>9.4 London=>8.4 Sydney=>5.2
32 printlnCache(cache);
33
34 return 0;
35}
完整的实现和测试代码可以在godbolt上查看。
总结
虽然列表的splice功能一直都存在，但是他在同一个列表中修改节点位置的特性通常会被大家所忽略。通过上述的 LRUCache 的实现，我们能够很好的加深对 list 的splice功能的理解和使用，在实际的开发中，灵活使用标准库中提供的方法，能够在简化我们代码的同时，提升程序的效率。要做到这一点就需要我们不断加深对标准库的学习和理解。
评论