If you want to maintain the order of insertion, then you could create a list alongside your map. Each insert will give you an iterator in return, which references the newly inserted element. Store this element in your list, and you're done. If you want to retrieve your elements in order of insertion, use the list. If you want it ordered by key, or just want to retrieve a single object with a key, use your map.
class MyMap {
std::map m_map;
std::list > m_list;
public:
typedef std::list >::iterator insert_iterator;
typedef std::map::iterator key_iterator;
void insert(int key, int value) {
m_list.push_back(m_map.insert(pair(key, value)));
}
insert_iterator ibegin() { return m_list.begin(); }
insert_iterator iend() { return m_list.end(); }
key_iterator kbegin() { return m_map.begin(); }
key_iterator kend() { return m_map.end(); }
};
Note that you will have to dereference your insert_iterator twice: once to get the list element which is an iterator to the map, and a second time to get the actual element of the map:
MyMap mymap;
mymap.insert(5, 15);
mymap.insert(100, 20);
mymap.insert(34, 30);
for (MyMap::key_iterator kit = mymap.kbegin(); kit != mymap.kend(); ++kit)
std::cout << (*kit).second << std::endl; // prints 15 30 20
for (MyMap::insert_iterator it = mymap.ibegin(); it != mymap.iend(); ++it)
std::cout << (*(*it)).second << std::endl; // prints 15 20 30
Of course, this mechanism breaks down once you start erasing elements from your map - the moment you do this, the accompanying iterators stored in the list will be invalidated! You could of course search for these elements and remove them from the list, but that would be very inefficient and might negate the efficiency that you gained from using a map in the first place. In that case you might be better off to just use a list without a map, and sequentially search for the key when you want to retrieve a particular element. Note that you can use the std::find() methods to search for particular elements, you just have to provide a comparator that specifically compares the key. If you have a compiler that supports C++0x you might even use an unnamed lambda to provide the comparator instead of having to define a function object class.
