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

Question

我想知道是否有可能拥有一个像 boost 循环缓冲区一样工作的地图。这意味着它的大小是有限的，当它达到其有限的大小时，它将开始覆盖第一个插入的元素。我也希望能够通过这样的缓冲区find or create和[name]. 是否有可能创造这样的东西以及如何去做？

Answer 1

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

实现已经存在。

Answer 2

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

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

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

Answer 3

好吧，我不认为 boost 中的结构是开箱即用的（尽管可能存在于其他地方），所以你应该创建它。不过，我不建议使用operator[]()，至少因为它是在 中实现的std::map，因为这可能难以跟踪添加到地图中的元素（例如，使用operator[]()with 值会将空值添加到地图中），然后选择用于添加和检索地图元素的更明确的 get 和 put 操作。

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

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();
       }
     }
};