STL std::map and sorting using value_compare
Author
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
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?
Author
Quote:Original post by dalleboy
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?
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 hereso now I want sort the map by distance from the closest to desired, to the farthest.
Darryl
Author
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
Sheeesh, you've not even tried, have you? Nothing is stopping you from creating a priority queue of pairs with a custom comparison functor.
Or, if you don't want to use a priority queue, you can just as well use a vector and manually sort it.
There almost always are ways to plug things together. [smile]
[Edited by - Fruny on October 12, 2004 8:34:49 PM]
#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]
Author
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
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
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
