Click here to Skip to main content
13,503,505 members
Click here to Skip to main content
Add your own
alternative version

Tagged as


17 bookmarked
Posted 9 Sep 2005


, 21 Apr 2006
Rate this:
Please Sign up or sign in to vote.
A template to traverse STL maps in insertion order.


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


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.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Software Developer
Argentina Argentina
No Biography provided

You may also be interested in...

Comments and Discussions

GeneralMy vote of 5 Pin
aputic9-Aug-11 10:59
memberaputic9-Aug-11 10:59 
GeneralAlternative implementation [modified] Pin
Daniel Trebbien2-Jan-10 13:11
memberDaniel Trebbien2-Jan-10 13:11 
QuestionWhy not a list? Pin
Pierre Couderc6-Sep-06 2:49
memberPierre Couderc6-Sep-06 2:49 
AnswerRe: Why not a list? Pin
Pierre Couderc6-Sep-06 5:20
memberPierre Couderc6-Sep-06 5:20 
GeneralBoost Multi-index containers Pin
thog25-Apr-06 16:41
memberthog25-Apr-06 16:41 
AnswerRe: Boost Multi-index containers Pin
lagos_fernando28-Apr-06 4:45
memberlagos_fernando28-Apr-06 4:45 
GeneralI got it, ... Pin
WREY29-Sep-05 7:37
memberWREY29-Sep-05 7:37 
GeneralTerribly confusing. Pin
WREY10-Sep-05 11:27
memberWREY10-Sep-05 11:27 
GeneralRe: Terribly confusing. Pin
karl_marx13-Sep-05 16:55
memberkarl_marx13-Sep-05 16:55 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.180417.1 | Last Updated 21 Apr 2006
Article Copyright 2005 by lagos_fernando
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid