linked_map

• Download demo project - 52 Kb
• Download source - 5.63 Kb

Introduction

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 get or 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:

class customer
{
};

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>
{
    public:
    ~customer_ptr_cache()
    {
        clear();
    }
    void delete_value( const iterator & i)
    {
        std::pair <bool,customer*> least_used_customer = at ( i );

        delete least_used_customer.second;
    }
}

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.

Background

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 >
class linked_map;

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 linked_map.

void erase(const iterator & iter);

Erases the entry corresponding to the iterator iter.

void erase(const K & k);

Erases the entry with the key k.

void clear();

Clears the map and linked_list elements. Calls delete_value() for each element.

boolean empty();

Returns true if the linked_map has no elements, false otherwise.

std::pair<boolean,V> get(const K & k);

Returns <true,val> if there is a <k,v> entry with key k, and moves its corresponding linked_list node to the end. Or <false,val()> otherwise.

std::pair<boolean,V> at( const iterator & iter)

Returns <true,val> if there is a <k,v> entry for the iterator iter, or <false,val()> otherwise. Doesn't change the linked_list order.

size_t size()

Returns the number of items in the linked_map.

iterator begin()

Returns an iterator to the beginning (least recently used) element of the linked_map.

iterator end()

Returns an iterator just past the last element of a linked_map.

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 free or 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.