🔒 Locked

STL std::map and sorting using value_compare

Started by darrylsh Oct 11, 2004 at 11:07 AM 7 replies 14.6k views

Original Post

Oct 11, 2004 at 11:07 AM

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

dalleboy

Oct 11, 2004 at 12:12 PM

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 that maps the age to the name. What are you trying to do?

darrylsh

Oct 11, 2004 at 1:35 PM

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

Fruny

Oct 11, 2004 at 3:35 PM

Use a std::priority_queue

darrylsh

Oct 11, 2004 at 3:59 PM

Quote:
Original post by Fruny
Use 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

Fruny

Oct 11, 2004 at 4:34 PM

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]

darrylsh

Oct 12, 2004 at 8:51 AM

Quote:
Original post by Fruny
Sheeesh, 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

Qw3r7yU10p!

Oct 12, 2004 at 9:31 AM

Quote:
Original post by darrylsh
Don'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

valoh

Oct 12, 2004 at 8:33 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.