C++如何将地图与循环缓冲区混合？

Question

我想知道是否有可能有一个像增强循环缓冲区一样工作的地图。这意味着它的大小有限，当它达到有限大小时，它将开始覆盖第一个插入的元素。另外，我希望能够搜索此类缓冲区并使用 [name] 查找或创建。是否有可能创造这样的东西以及如何做到？

Answer 1

您想要的是 LRU（最近最少使用）Map 或 LRA（最近最少添加）Map，具体取决于您的需要。

实施已经存在。

Answer 2

好吧，我不认为 boost 中的结构是现成的（不过可能存在于其他地方），所以你应该创建它。不过，我不建议使用 operator[]()，至少因为它是在 std::map 中实现的，因为这可能会导致难以跟踪添加到的元素映射（例如，使用带有值的 operator[]() 将该空值添加到映射中），并进行更明确的 get 和 put 操作来添加和检索映射的元素。

至于最简单的实现，我会选择使用实际的 map 作为存储，并使用 deque 来存储添加的元素（未测试）：

template <typename K, typename V>
struct BoundedSpaceMap
{
    typedef std::map<K,V> map_t;
    typedef std::deque<K> deque_t;

    // ...
    typedef value_type map_t::value_type;
    // Reuse map's iterators
    typedef iterator map_t::iterator;

    // ...
    iterator begin() { return map_.begin(); }

    // put
    void put ( K k, V v)
    { map_.insert(std::make_pair(k,v));
      deque_.push_back(k);
      _ensure();  // ensure the size of the map, and remove the last element
    }

     // ...

private:
     map_t map_;
     deque_t deque_;

     void _ensure() { 
       if (deque_size() > LIMIT) { 
         map_.erase(deque_.front()); deque_.pop_front();
       }
     }
};

Answer 3

好吧，这并不是一个真正的“循环缓冲区”，因为这对于映射来说没有多大意义，但我们可以使用一个简单的数组，而无需任何额外的链表或任何东西。

这称为封闭散列 - wiki 文章很好地总结了它。双散列是最常用的，因为它避免了聚类（这会导致性能较差），但也有其自身的问题（局部性）。

编辑：既然你想要一个特定的实现，我认为 boost 没有一个，但是这个 或 这 在另一篇关于封闭散列的 SO 帖子中提到过。