通过引用 std::list 中的元素从 std::unordered_map 中删除元素

Question

我正在实现 LRUCache，但在理解从 std::unordered_map 中删除方面遇到了问题。互联网上的所有示例都表明，可以使用 std::list 中的元素引用从 std::unordered_map 中删除元素（通过使用 std: :list::back())。为什么会这样呢？我查看了 std::unordered_map::erase() 的文档，它接受映射迭代器或键作为参数，但肯定不是对另一个数据结构中元素的引用？是否有一些我不明白的关于迭代器的特定转换或某些东西？先感谢您！

PS 我会感谢对我的代码结构和实现的任何评论。

这是我的缓存代码：

#ifndef LRUCACHE_H
#define LURCACHE_H

#include <list>
#include <unordered_map>
#include <assert.h>
#include <iostream>

template<typename T, typename KeyT = T>
class LRUCache
{

using ListItr = typename std::list<T>::iterator;

public:
    LRUCache(int size) : m_size(size)
    {

    }

    int size() const
    {
        return m_size;
    }

    bool isFull() const
    {
        return m_size == m_cache.size();
    }

    bool contains(const KeyT& key)
    {
        m_lookup_table.find(key) != m_lookup_table.end();
    }

    T get(const KeyT& key)
    {
        auto hit = m_lookup_table.find(key);
        assert("No such element present" && hit != m_lookup_table.end());
        if (hit != m_lookup_table.begin()) {
            m_cache.splice(m_cache.begin(), m_cache, hit->second);
        }
        return *(hit->second);
    }

    void set(const KeyT& key, const T& value)
    {
        auto hit = m_lookup_table.find(key);
        if (hit == m_lookup_table.end()) {
            if (isFull()) {
                m_lookup_table.erase(m_cache.back()); // <-- I don't understand this
                m_cache.pop_back();
            }
            m_cache.push_front(value);
            m_lookup_table[key] = m_cache.begin();
            return;
        }

        if (hit->second != m_cache.begin()) {
            m_cache.splice(m_cache.begin(), m_cache, hit->second);
        }
    }

    void display() const
    {
        for (const auto& e : m_cache) {
            std::cout << e << " ";
        }
        std::cout << std::endl;
    }

private:
    int m_size;
    std::list<T> m_cache;
    std::unordered_map<KeyT, ListItr> m_lookup_table;
};

#endif

Answer 1

erase 有一个重载，它接受 Key （在您的情况下等于 KeyT），而不是迭代器：https://en.cppreference.com/w/cpp/container/unordered_map/erase。

请注意，来自 std::list 的 back 不会返回迭代器，而是返回元素（在您的情况下为 T）： https://en.cppreference.com/w/cpp/container/list/back

所以我的猜测是代码仅当 KeyT = T 时针对您的默认情况进行编译。