Assign key value in map - special strings(% and $)

Question

I have below map code in C++-

std::map<std::string, std::string> vals;
vals["%"] = "PERCENT";
vals["$"] = "DOLLAR";
vals["="] = "EQUAL";

With above code lines I expect % will be at index 0 and $ at index 1. But when I compile and debug I always find $ at index 0 and % at index 1.

anybody has any idea why this is happening? maintaining sequence is must for me , any suggestion how can I get rid of it.

What do you mean by "index 0"? Do you mean `vals.begin()` is `$`? — NathanOliver, Jan 22 '16 at 14:00
`std::map` must guaranty O(log n) access by key, so usually it is realized with the rb-tree. If you need same functionality without key access, but keeping order you can use `std::vector>` — johngull, Jan 22 '16 at 14:06
On a side note, you can use `Uniform Initialization` (introduced by C++11) by writting `std::map vals = { {"%", "PERCENT"}, {"$", "DOLLAR"}, {"=", "EQUAL"} };` — Richard Dally, Jan 22 '16 at 14:12

Hatted Rooster · Answer 1 · 2016-01-22T14:05:34.960

3

That's because std::map sorts its content. The order of insertion doesn't matter. Here, it will sort on alphabetical order.(because the key value is std::string) Because $ has a lower value than % this means that $ == vals.begin(). This is also why user-defined types used as keys in a map require their operator< to be overloaded.

edited Jan 22 '16 at 14:05

answered Jan 22 '16 at 14:03

Hatted Rooster

35,759
6
62
122

is there anyway I can maintain order of insertion? – user987316 Jan 22 '16 at 14:05
@user987316 Maintaining order of insertion is not something `map` cares about. Try `std::vector`. – Hatted Rooster Jan 22 '16 at 14:06
insert elements into std::list and have a std::map::const_iterator>> for fast lookup ? – Jan 22 '16 at 14:07
1

I see this post: [A std::map That Keeps Order of Insertion](http://stackoverflow.com/questions/1098175/a-stdmap-that-keep-track-of-the-order-of-insertion). – Shadow2531 Jan 22 '16 at 14:08

score 1 · Answer 2 · answered Jan 22 '16 at 14:11

There is no 'natural' standard dictionary container that preserves the order of insertion. Neither std::map nor std::unordered_map will do this. If you need to preserve the order of insertions, you need to use a container which can do this and insert std::pair<your_key_type, your_value_type>.

The obvious drawback of that is that uniqueness of your keys will no longer be enforced automatically, so that is something you will have to take care about - with huge performance penalty.

The 3 standard containers which will suit you are std::vector, std::deque and std::list, and the most performant one usually is the std::vector.

There are also third-party libraries (boost, for example) which have some containers which might suit you as well.

score 0 · Answer 3 · answered Jan 22 '16 at 14:12

You can't think of the subscript operator as an array index in this case. For std::map operator is overloaded where the contents of [] is the templated type of your key. In this case you're using a string to string map and so you put strings inside of []. As far as how the contents are sorted when you iterate over the contents, I believe this STL implementation specific. However, looking at the link map you will see that you can optionally provide a comparitor that can override the default sort.

I think you'd have a hard time getting to a insertion order iteration, but that isn't the point of a map.

Assign key value in map - special strings(% and $)

3 Answers3