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.

Are you asking about retaining insertion order or having the keys ordered in the sense of the English words? — , Mar 31 '10 at 10:02
In one of my comments he also states that he needs the index access, so many of the post are wrong, due to the lack of clarity in the question — Ronny Brendel, Mar 31 '10 at 10:06
In that case, this is a dupe several times over - see for example http://stackoverflow.com/questions/1098175/a-stdmap-that-keep-track-of-the-order-of-insertion — , Mar 31 '10 at 10:09

score 5 · Answer 1 · edited May 23 '17 at 11:48

5

A std::map 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.

edited May 23 '17 at 11:48

Community

1
1

answered Mar 31 '10 at 09:58

Ronny Brendel

4,777
5
35
55

But I want to access by index such as map["one"] to return 1. Otherwise the vector needs iteration to pick find and return the elements – Mar 31 '10 at 10:00
3

You can't have a vector of references, because vector elements have to be Assignable. – Khaled Alshaya Mar 31 '10 at 10:08
You can have an unordered map with iterator as the second element – thegreatcoder Jan 10 '19 at 03:22

Andreas Brinck · Answer 2 · 2010-03-31T10:10:56.433

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;

score 3 · Answer 3 · answered Mar 31 '10 at 10:03

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.

C++ dictionary/map with added order

3 Answers3

Linked