Solved

sorting map

Posted on 2006-05-21
Medium Priority
320 Views
suppose:

typedef map< string, int , less<string>> new_type;
new_type nt;
nt.insert(new_type::value_type("car", 300));
nt.insert(new_type::value_type("train", 150));
nt.insert(new_type::value_type("truck", 100));
nt.insert(new_type::value_type("bike", 330));

This is my company's interview questions for new interviewers.
need to write a sorting algorithm to sort the order of key and value respectively
without using sorting functions provided by language
0
Question by:ytt5509Experts
• 7
• 5

LVL 86

Expert Comment

ID: 16730979
If the intrviewees are smart, they'll tell you that a map is sorted anyway by default. 'Sorting' the map is done each time when you insert an element and the map implementation evaluates 'operator<()' or predicate, i.e. the item ends up in the right place.
0

LVL 86

Expert Comment

ID: 16730990
BTW, see also http://www.sgi.com/tech/stl/Map.html for more info - sorting a map by value would be kinda defeating the purpose of a map, though.
0

Author Comment

ID: 16731006
I do know items in a map is alreadys "sorted" when they were inserted into map.
The thing is boss needs a workable answer, and we don't have one.
0

LVL 86

Expert Comment

ID: 16731013
So, what should the expected result be like?
0

Author Comment

ID: 16731117
results should have 2 functions. One is to sort the map by the order of key
and the other to sort by value.
And, testing functions would use iterators to loop through the map,
using  nt.begin(), nt.end() and print the key and value.
0

LVL 86

Expert Comment

ID: 16731151
So it i about exporting the contents on the map to other containers? As I wrote, iterating through the map will yield the sorted sequence and sorting a map by value is simply neither a good idea nor is it possible - using that very std::map. A different container - e.g. a std::multiset - would be possible though (yet not a map either)
0

LVL 86

Expert Comment

ID: 16731181
>>So it i about exporting the contents on

Sorry, should have been "So it is about exporting the contents of..."
0

Author Comment

ID: 16731211
I see what you are saying.
so, it is not possible to overwrite the underlying sorting algorithm in std::map?
say, when a pair(key and value) in inserted, map will put them in ASCII order
according to key (or value)?

If this is not possible, I will take the following answer. Functions that could
just print out  the map's content in ASCII order according to key and value respectively.
you can put the contains in other containers or arrays, but, still,  can't using any
default "sort" functions provided by the language.
0

Author Comment

ID: 16731219
sorry, I mean:
put the "contents" in other containers or arrays.....
0

LVL 86

Expert Comment

ID: 16731243
>>so, it is not possible to overwrite the underlying sorting algorithm in std::map?

It is possible if ypu supply your own 'map' implementation - but, again, sorting a map by values does not make sense at all, since keys are unique, values aren't. So you bsaically want the behaviour of a container that is everything but a map, but using the same interface.

To be blunt a about that: This is not a good interview question unless you want to end up in theoretical discussions.
0

Author Comment

ID: 16731308
jkr, I'm not a decent C++ programmer and just try to find out all answers for
my boss who wrote those questions. If you could take the alternative,
it worths the same points.

Functions that could just print out  the map's content in ASCII order
according to key and value respectively. You can put the contents in other
containers or arrays, but, still,  can't using any default "sort" functions
provided by the language.
0

LVL 86

Accepted Solution

jkr earned 2000 total points
ID: 16731366
>>Functions that could just print out  the map's content in ASCII order
>>according to key and value respectively.

To print a maps sorted contents, just use

#include <map>
#include <string>
#include <iostream>
using namespace std;

typedef map<string,int> new_type;

int main () {

new_type nt;
nt.insert(new_type::value_type("car", 300));
nt.insert(new_type::value_type("train", 150));
nt.insert(new_type::value_type("truck", 100));
nt.insert(new_type::value_type("bike", 330));

new_type::iterator i;

for ( i = nt.begin(); i != nt.end(); ++i) {

cout << i-> first << " " << i->second << endl;

}

return 0;
}

Sorry, but my time zone takes it's tribute, gotta go...
0

Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a Gā¦
Looking for a way to avoid searching through large data sets for data that doesn't exist? A Bloom Filter might be what you need. This data structure is a probabilistic filter that allows you to avoid unnecessary searches when you know the data definā¦
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses
Course of the Month16 days, 1 hour left to enroll