Jump to content
  • Advertisement
Sign in to follow this  
darrylsh

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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<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 = c
std::map<location,int> DistanceToDisredLocation

for( 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 this post


Link to post
Share on other sites
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

Share this post


Link to post
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 this post


Link to post
Share on other sites
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

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!