C++ dictionary/map with added order

Question

I want to have something similar to map but while iterating I want them to be in the same order as it is added.

Example

map.insert("one", 1);
map.insert("two", 2);
map.insert("three", 3);

While iterating I want the items to be like "one", ""two", "three"..By default, map doesn't provide this added order. How to get the map elements the way I have added? I want to retain the insertion order.

Anything with STL is fine or other alternative suggestions also fine.

Answer 1

http://stackoverflow.com/questions/1098175/a-stdmap-that-keep-track-of-the-order-of-insertion this is a duplicate (thanks to neil butterworth)

You could use a map with a sorted structure parallel to it.

map<key, value>
vector<value*> //holds only pointers to map entries.
vector<key> //holds only map keys. Adds one indirection.

Answer 2

Boost mult iindex makes it possible to have a container which can be iterated over in several different orders.

http://www.boost.org/doc/libs/1_42_0/libs/multi_index/doc/index.html

Slightly modified example:

struct record {
    int         insertion_index;
    std::string somestring;
    int         somevalue;
    bool operator < (const record& e) const {return insertion_index < e.insertion_index;}
};

typedef multi_index_container<
    record,
    indexed_by<
        // sort by record::operator<
        ordered_unique<insertion_indexentity<record> >,        
        // sort by less<string> on somestring
        ordered_non_unique<member<record,std::string,&record::somestring> >    
    >
> record_set;

Answer 3

Actually std::map by default sorts your keys using std::less<T> where T is your key's type. If you don't want the elements sorted by key, you should be using an std::list<std::pair<K,V> > or an std::vector<std::pair<K,V> > -- where K is your key type, and V is your value type, and then using push_back to add elements to the end of the list/vector.