C ++ how to mix map with circular buffer?

Question

I wonder if it is possible to have a card that will act as a booster buffer. This means that it will have a limited size, and when it reaches its limited size, it will begin to overwrite the first inserted elements. I also want to be able to search through such a buffer and find or create using [name] . Is it possible to create such a thing and how to do it?

Answer 1

Well, I don’t think the structure is present from the box in boost (maybe elsewhere), so you have to create it. I would not recommend using operator[]() , although at least as implemented in std::map , because it can make it difficult to keep track of elements added to the map (for exapmle, using operator[]() with a value of adds that the value is empty to the map) and move on to more explicit get and put operations to add and extract map elements.

As for the simplest implementation, I would use to use the actual map as storage and deque to store the added elements (not tested):

 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 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 2

What you want is an LRU (least recently used) Card or an LRA (less recently added) Card depending on your needs.

Implementations already exist.

Answer 3

This is actually not a circular buffer, since it does not make much sense for the map, but we can use a simple array without any additional linked lists or anything else.

This is called private hashing - the wiki article outlines it very well. Double hashing is most often used, since it avoids clustering (which leads to performance degradation), but has its own problems (locality).

Edit: since you need a specific implementation, I don't think boost has one, but this or this was mentioned in another SO message about closed hashing.