linked_map is a C++ template wrapper of the
std::map associative container that:
- as entries are inserted into the map, they are joined in an ordered double linked list.
- every time you call
insert, the map pair's linked list node is removed from its current position and placed at the end.
This is very useful for implementing a “least recently used” discipline for a cache. For example, you may want to keep frequently accessed customers in memory, and discard the less frequently accessed. For example:
typedef linked_map <std::string,customer,10> customer_cache;
or even make the
linked_map manage the deallocation of memory overwriting some virtual functions:
class customer_ptr_cache: public linked_map <std::string,customer *,10>
void delete_value( const iterator & i)
std::pair <bool,customer*> least_used_customer = at ( i );
Now, you could freely add and get customers from your cache, and be sure that there won't be no more than 10 in memory, and if the cache has to discard a customer, it will be the "least used" one.
linked_map is a very simple template. It has an inner
std::map that holds your value, and a pointer to a double linked list node. Something like this:
That way, we can re-link the nodes of the linked list to track the insertion/get/erase order, keeping the tree order to look up keys efficiently. Here is an example of the structure before and after the method
get() is called for the left child node of the tree (previous nodes hidden for clarity):
Using the code
The interface of the class is:
template <typename K,typename V,typename Pr = std::less<K>,int Cap = -1 >
boolean insert(const K & k,const V & v);
Inserts the pair
<k,v> and places its corresponding linked node at the end of the list, and returns true. Returns false if that key is already in the
void erase(const iterator & iter);
Erases the entry corresponding to the iterator
void erase(const K & k);
Erases the entry with the key
Clears the map and
linked_list elements. Calls
delete_value() for each element.
true if the
linked_map has no elements,
std::pair<boolean,V> get(const K & k);
<true,val> if there is a
<k,v> entry with key
k, and moves its corresponding
linked_list node to the end. Or
std::pair<boolean,V> at( const iterator & iter)
<true,val> if there is a
<k,v> entry for the iterator
<false,val()> otherwise. Doesn't change the
Returns the number of items in the
Returns an iterator to the beginning (least recently used) element of the
Returns an iterator just past the last element of a
virtual void delete_value(const iterator & i)
This function will be called for every erase operation. You can override it to de-allocate your value with
delete. Please don't change anything but the value from here!! Don't forget to override the destructor also.
Points of Interest
Although I did my best to test this code, I know this is not a final work. I'm open to any suggestions, corrections, improvements, etc. Also, I would like to say that in my opinion, this kind of containers are very useful, and should be part of the standard. Perhaps, a
linked_set and a
linked_hash (a hash first, actually), are the next steps.
In the sources, you will find the linked_map.h file, and a VC++ 6.0 test project where I call the insert/get/erase functions randomly, checking memory leaks and the consistency of the data.