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?

Hydra

when you say map do you want the facilities of std::map(which has ordered set of elements) or something else – Beachlamar

by map I mean std::map api, an array with indexed by thare first element pairs.. so to say having pair<stringed_index, some_class_of_mine> inside of it I would call my_map[stringed_index_id] and get some_class_of_mine_id or have a new one created for me. – Hydra

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

Overscrupulous

Answer 2

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

Implementations already exist.

Drag

Grate!) Where to get tham? Are there any in boost? – Hydra

@patros, so does StackOverflow: #2057924 – Selfannihilation

Answer 3

Well not really a "circular buffer" since that doesn't make much sense for a map, but we can use a simple array without any additional linked lists or anything.

This is called closed hashing - the wiki article summarizes it quite nicely. Double hashing is the most often used as it avoids clustering (which leads to worse performance), but has its own problems (locality).

Edit: Since you want a specific implementation, I don't think boost has one but this or this were mentioned in another SO post about closed hashing..

Inalterable