sorting in std::map where key is a std::string

Question

I have a std::map mymap

Now, if I insert values in the map like:

std::map <string, string> mymap;
mymap["first"] = "hi";
mymap["third"] = "how r you";
mymap["second"] = "hello";

Now I want to iterate over the map and print the value in sorted(keys) manner:

map<string, string>::iterator itr;
for(itr = mymap.begin(); itr != mymap.end(); itr++)
{
   string newline = itr->second;
   cout << newline << endl;
}

Output should be:

hi 
hello 
how r you

I thought that by default map stores in sorted keys manner but I'm getting the same order in output as I'm giving in input. Do I need to provide my sort function for this or need to do something extra before iterating over the map?

The for loop refers to file_line and not mymap. I take it this is not the actual code as first is not quoted in population of mymap. — hmjd
– hmjd, Commented Dec 13, 2011 at 13:58
I am not quite sure about the C++ std::map implementation, but such hashtables are not usually sorted. They are meant to be accessed via indexer, not traversed. — Gigi
– Gigi, Commented Dec 13, 2011 at 14:00
@user983064 std::map is a binary tree, ordered by key. C++11 has hash tables, such as std::unordered_map. — juanchopanza
– juanchopanza, Commented Dec 13, 2011 at 14:49

hmjd · Accepted Answer · 2011-12-13 15:46:16Z

47

The elements in std::map are ordered (by default) by operator< applied to the key.

The code you posted, with minor edits, worked for me as you expected:

std::map <string, string> mymap;
mymap["first"]="hi";
mymap["third"]="how r you";
mymap["second"]="hello";

for (std::map<string, string>::iterator i = mymap.begin(); i != mymap.end(); i++)
{
    cout << i->second << "\n";
}

Prints:

hi
hello
how r you

edited Dec 13, 2011 at 15:46

answered Dec 13, 2011 at 14:14

hmjd

122k21 gold badges216 silver badges259 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Emilio Garavaglia Over a year ago

uhmmmm ... what about "fourth"?? Should it be after "first" or "third"? May be he needs to customize the comparison predicate...

hmjd Over a year ago

@EmilioGaravaglia, yes he would or just use an int as the key.

juliomalegria Over a year ago

auto? this question wasn't tagged as c++11

hmjd Over a year ago

@julio.alegria, there you go.

Moses Kirathe Over a year ago

Just a follow-up question on this response, what is the difference between for (std::map<string, string>::iterator i = mymap.begin(); i != mymap.end(); i++) and for (std::map<string, string>::iterator i = mymap.begin(); i != mymap.end(); ++i) where the iterator is incremented before rather than after?

|

Giovanni Funchal · Accepted Answer · 2011-12-13 14:12:04Z

9

The map is actually a tree, and is sorted by KEY order. You are printing itr->second which is the VALUE not the KEY. If you want your key/value pairs sorted by VALUE, use the VALUE as key instead, or store everything in another container (say an array), then sort them.

answered Dec 13, 2011 at 14:12

Giovanni Funchal

9,28215 gold badges66 silver badges111 bronze badges

1 Comment

juliomalegria Over a year ago

What you said is correct, so KEYS are: "first" < "second" < "third", thus, we should expect the same result as the OP said: hi | hello | how r you, but he said: I'm getting the same order in output as I'm giving in input, that is: hi | how r you | hello.

MGZero · Accepted Answer · 2011-12-13 14:20:05Z

4

std::map is already ordered. If you were using unordered_map, now you'd have a problem!

Entries in std::map are ordered by the key, or itr->first. itr->second as you have it, refers to the value associated with the key.

Further more, you're not iterating over the map, you're iterating over file_line (I don't know what that is, but I'm going to assume it's different from mymap. That is what you should be iterating over).

answered Dec 13, 2011 at 14:20

MGZero

6,0225 gold badges33 silver badges47 bronze badges

Comments

Shawnone · Accepted Answer · 2011-12-13 14:52:25Z

2

The standard defines:

The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them.

answered Dec 13, 2011 at 14:52

Shawnone

8605 silver badges17 bronze badges

Collectives™ on Stack Overflow

sorting in std::map where key is a std::string

4 Answers 4

6 Comments

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

6 Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related