Sorting std::map by value
Author
Wow, I haven't posted on these boards in...probably 4 years. I used to be andromeda, if anyone remembers me.
Anyways, I have an std::map<string, int> that maps words to the number of times they occur in a block of text. This is fine, but when I output them, I'd kind of like them to be ordered by the number of times they occur, highest to lowest (a.k.a., by the values of the map, not the keys).
Is there any easy way to do this? Or do I have to do something like make a std::vector, output all the map elements to that, and then sort it?
Instead of using a std::vector, you could insert every element of the map into a sorted container (like std::set), then iterate through that.
I can't think of any better way to do it right now - sorting by multiple attributes can get tricky.
I can't think of any better way to do it right now - sorting by multiple attributes can get tricky.
std::sort(map.begin(), map.end(), std::greater<int>());
http://www.sgi.com/tech/stl/sort.html
http://www.sgi.com/tech/stl/greater.html
<3 Thetan
http://www.sgi.com/tech/stl/sort.html
http://www.sgi.com/tech/stl/greater.html
<3 Thetan
Quote:Original post by Thetan
std::sort(map.begin(), map.end(), std::greater<int>());
http://www.sgi.com/tech/stl/sort.html
http://www.sgi.com/tech/stl/greater.html
<3 Thetan
No. a std::map is a sorted container. std::sort and other mutating algorithms won't work on it.
Quote:Original post by cyphr
Is there any easy way to do this?
A bidirectional map? (may need tweaking to handle duplicate counts).
Quote:Or do I have to do something like make a std::vector, output all the map elements to that, and then sort it?
That would be the other easy way, yes.
Quote:Original post by FrunyQuote:Original post by cyphr
Is there any easy way to do this?
A bidirectional map? (may need tweaking to handle duplicate counts).
O_o
...
Is there anything that Boost doesn't do?
Quote:Original post by Mushu
Is there anything that Boost doesn't do?
I tried to get it to make me dinner once... that didn't work [sad]
But, this is just another example of why everyone who programs in C++ should have a copy of boost installed and in use.
Author
Thanks for the replies - bidirectional map is so close, but I can't guarantee uniqueness of the second values. In fact, there will almost definitely be duplicates.
So, I'll probably just copy all the elements to a vector.
Boost is still God, though.
So, I'll probably just copy all the elements to a vector.
Boost is still God, though.
Quote:Original post by cyphr
Thanks for the replies - bidirectional map is so close, but I can't guarantee uniqueness of the second values. In fact, there will almost definitely be duplicates.
So, I'll probably just copy all the elements to a vector.
Boost is still God, though.
They have a couple of examples that do exactly what you are trying to do:
Quote:Example 5: sequenced indices
See source code.
The combination of a sequenced index with an index of type ordered_non_unique yields a list-like structure with fast lookup capabilities. The example performs some operations on a given text, like word counting and selective deletion of some words.
Quote:Example 8: hashed indices
See source code.
Hashed indices can be used as an alternative to ordered indices when fast lookup is needed and sorting information is of no interest. The example features a word counter where duplicate entries are checked by means of a hashed index. Confront the word counting algorithm with that of example 5.
As for using a vector, I suppose it is rather easy:
#include <string>#include <map>#include <vector>#include <functional>#include <algorithm>typedef std::map< std::string, int > WordMap;typedef std::pair< std::string, int > Word;struct OrderByCount : std::binary_function< Word, Word, bool > { bool operator()( Word const &lhs, Word const &rhs ) { return lhs.second < rhs.second; }};int main() { WordMap words; words["One"] = 3; words["High"] = 66; words["Dude"] = 24; words["Car"] = 31; words["Foo"] = 143; words["in"] = 2; words["Glue"] = 64; std::vector< Word > ordered_words; std::copy( words.begin(), words.end(), std::back_inserter( ordered_words ) ); std::sort( ordered_words.begin(), ordered_words.end(), OrderByCount() );}jfl.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
