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

Question

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

Answer 1

好吧，我不认为 boost 中的结构是现成的（不过可能存在于其他地方），所以你应该创建它。不过，我不建议使用operator[]()，至少因为它是在 中实现的std::map，因为这可能会使跟踪添加到地图中的元素变得困难（例如，operator[]()与值一起使用会将该空值添加到地图中），然后选择用于添加和检索地图元素的更明确的 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();
       }
     }
};