# STL std::map and sorting using value_compare

This topic is 5392 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi all, Although I am pretty familiar with c++, I mostly avoided using STL, but as of late I have found it to be very useful and invaluable, however, I find the documentation for it to be quite cryptic. Anyways, I want to create a standard map using a alternative sorting function. I understand that a map is by default sorted by the key value, However, I'd like to sort it by it's data value, for example: Suppose I have a map of names (key) and an int (data) Tom 10 Dick 20 Harry 30 Darryl 40 by default the map will be sorted alphabetically by name (key) I would like it to be sorted as listed above, by data value. I have looked at using the value_compare member, but am lost as to what I need to do and have not found any simple/clear examples on the net. Any assitance would be appreciated. Thanks, Darryl

##### Share on other sites
There is no way for std::map to be sorted by the 'value', only the 'key'. But you could have an extended 'key', that also contain the 'value'. But I think you're biting your self in the foot. You could have a std::multi_map<int, std::string> that maps the age to the name. What are you trying to do?

##### Share on other sites
Quote:
 Original post by dalleboy But I think you're biting your self in the foot. You could have a std::multi_map that maps the age to the name. What are you trying to do?

I am open to suggestions...the above was just an example, below is closer to the actual program, though simplified a bit.

basically I have a program that maps a custom enum "location" type
variable and a int
enum location{a, b, c, d, e . . . z};location DesiredLocation = cstd::map<location,int> DistanceToDisredLocationfor( int i = 0;i <= z; i++){	DistanceToDesiredLocation[static_cast<Location>(i)] = Distance(i,DesiredLocation);}// Sort Map here

so now I want sort the map by distance from the closest to desired, to the farthest.

Darryl

##### Share on other sites
Use a std::priority_queue

##### Share on other sites
Quote:
 Original post by FrunyUse a std::priority_queue

Don't see how priority_queue would work, it doesn't take a map container, only something like a vector or a deque(any container that supports front(), push_back(), pop_back()), but as I need to store the pair of values, those won't work. Though I guess I could make a vector of maps first, but it would be easier to just sort the map into a vector directly.

I think dalleboy's suggestion of multimap will work directly as I can use the distance as a non-unique key that will automatically be sorted as I want and provide back the location.

Thanks,
Darryl

##### Share on other sites
Sheeesh, you've not even tried, have you? Nothing is stopping you from creating a priority queue of pairs with a custom comparison functor.

#include <iostream>#include <map>#include <deque>#include <queue>#include <string>#include <utility>#include <functional>template<class T>struct greater_second: std::binary_function<T,T,bool>{   inline bool operator()(const T& lhs, const T& rhs)   {      return lhs.second > rhs.second;   }};int main(){  std::map<std::string,int> themap;  themap["hello"] = 10;  themap["world"] = 5;  typedef std::pair<std::string,int> data_t;  typedef std::priority_queue<data_t, std::deque<data_t>, greater_second<data_t> > queue_t;  queue_t q(themap.begin(), themap.end());  std::cout << q.top().first << std::endl;}

Or, if you don't want to use a priority queue, you can just as well use a vector and manually sort it.

#include <iostream>#include <map>#include <vector>#include <string>#include <utility>#include <algorithm>#include <functional>template<class T>struct less_second: std::binary_function<T,T,bool>{   inline bool operator()(const T& lhs, const T& rhs)   {      return lhs.second < rhs.second;   }};int main(){  std::map<std::string,int> themap;  themap["hello"] = 10;  themap["world"] = 5;  typedef std::pair<std::string,int> data_t;  std::vector<data_t> vec(themap.begin(), themap.end());  std::sort(vec.begin(), vec.end(), less_second<data_t>());  std::cout << vec.front().first << std::endl;}

There almost always are ways to plug things together. [smile]

[Edited by - Fruny on October 12, 2004 8:34:49 PM]

##### Share on other sites
Quote:
 Original post by FrunySheeesh, you've not even tried, have you? Nothing is stopping you from creating a priority queue of pairs with a custom comparison functor....There almost always are ways to plug things together. [smile]

Well no I didn't try, but as I sort of explained in the first post, I am not so familiar with STL and the Docs are pretty cryptic to me...I mostly have learned STL from looking at examples of their use, so after you suggested priority queues, I went to the docs and ofcourse, was unable to put it together the way you did, but then again if I could had done that, I probably wouldn't had needed to ask in the first place ;-). But your example is very useful and I will tuck it away for future reference, if you had included it originally, I probably wouldn't had written of Priority queues so quick :-)

I did however implement what I wanted using the multimap because I am familiar with the similar map class...but let me ask this real quick. Are [] defined for multimap? For map I can insert using mapobject[key] = value, but this didn't work for multimap, so I used insert, but I would had preferred the other way. Don't see why it wouldn't be defined, maybe has to do with there not being unique keys...hmmm

Anyway, thanks
Darryl

##### Share on other sites
Quote:
 Original post by darrylshDon't see why it wouldn't be defined, maybe has to do with there not being unique keys...hmmm

That would seem the sensible reason.

multimap

##### Share on other sites
perhaps a little bit offtopic, but you could also have a look into boost::multi_index in the current boost cvs.

I haven't used it myself yet but it look like a very interesting container which also will perfectly fit your needs.
With boost::multi_index you can have a container with several indices to access it (in your case sorted string and sorted int). It is like a lightweight database container where you can query your data through several different indices which you configurate at compile time.

• 21
• 15
• 9
• 17
• 13