C++ how to mix a map with a circular buffer?

Question

I wonder is it possible to have a map that would work like boost circular buffer. Meaning it would have limited size and when it would get to its limited size it will start overwriting first inserted elements. Also I want to be capable to search thru such buffer and find or create with [name]. Is It possible to create such thing and how to do it?

Answer 1

Well, I don't think that structure is present out of the box in boost (may exist elsewhere, though), so you should create it. I wouldn't recommend using operator[](), though, at least as it is implemented in std::map, because this may make difficult to track elements added to the map (for exapmle, using operator[]() with a value adds that empty value to the map), and go for a more explicit get and put operations for adding and retrieving elements of the map.

As for the easiest implementation, I would go for using an actual map as the storage, and a deque for the storage of the elements added (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'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();
       }
     }
};