0

Right now I have a map and I need to sort it by value(int), and then by key(string) if there is a tie. I know I would need to write a customized comparison function for this, however so far I haven't been able to make it work. (I need to store my stuffs in a map since the strings are words and ints are the frequencies and I will need to 'find' the pairs by searching the keys later)

Tina
  • 1
  • A `std::map` is always sorted by key. So, store it in a different container, maybe even a `std::map` or `std::multimap`. – Deduplicator Dec 02 '18 at 00:36
  • That's not how maps work. Unless you want to get into the new transparent comparison stuff, but you're still not going to get performance out of that. Have you considered maintaining an _index_ container alongside the data container? Why do you think you need to sort by value then key? Is that purely for iteration purposes? Again, if your iteration and lookup have different requirements then that's a flag that you need a second, view-like container IMO. One thing that might be useful for you here is a [_bimap_](https://www.boost.org/doc/libs/1_67_0/libs/bimap/doc/html/index.html)... – Lightness Races in Orbit Dec 02 '18 at 00:37
  • @Deduplicator That just moves the goalposts because now you broke lookup-by-K. – Lightness Races in Orbit Dec 02 '18 at 00:39
  • 1
    Perhaps populating a `std::set>` and provide the set with your comparison function would work? That set should be constructable via your maps iterators. – Ted Lyngmo Dec 02 '18 at 00:44
  • 3
    Possible duplicate of [Sorting std::map using value](https://stackoverflow.com/questions/5056645/sorting-stdmap-using-value) – Killzone Kid Dec 02 '18 at 01:03
  • @LightnessRacesinOrbit We don't know enough to say whether it moves the goalpost, or is a possible solution. The evidence that it might be a solution is a bit weak, truly. – Deduplicator Dec 02 '18 at 01:09
  • @Deduplicator We do know that because the question literally says "I will need to 'find' the pairs by searching the keys later") and your solution makes that as difficult to do, as the sorting-by-value is now. You just swapped the problem around. – Lightness Races in Orbit Dec 02 '18 at 01:22
  • Why do you need the order? You may want to use two structures instead of one. – Matthieu Brucher Dec 02 '18 at 10:27
  • This question lack information on how the data is to be filled and used as one would select appropriate container based on that. For exemple, do you get the frequency as a number from the data or you increment a counter each time you find that word. – Phil1970 Dec 03 '18 at 01:43

3 Answers3

1

The std::map can only be sorted by key (string in your case).

If you need to sort it by value as well, you'd need to create a std::multimap with the int as key and the string as value, and populate it by iterating over the map.

Alternatively, you could also create a vector<pair<int,string>> that you populate by iteration over the map and just use std::sort().

Christophe
  • 68,716
  • 7
  • 72
  • 138
1

You can use a std::multiset<std::pair<int, std::string>>

aeroyorch
  • 56
  • 1
  • 6
  • Why that instead of simpler `std::multimap>`? – Phil1970 Dec 02 '18 at 02:11
  • `std::multimap` orders by key not by value. Insertion of elements with same key are not ordered by value (https://en.cppreference.com/w/cpp/container/multimap/insert): _"If the container has elements with equivalent key, inserts at the upper bound of that range."_ (since C++11). Hence using a `std::multiset` or `std::set` of pairs provides a way of ordering both. – aeroyorch Dec 02 '18 at 11:01
0

With the information given, it's a bit of a guessing game, but unless you are shuffling massive amounts of data, this may do.

using entry = std::pair<std::string, int>;
using CompareFunc = bool(*)(const entry&, const entry&);
using sortset = std::set<entry, CompareFunc>;
sortset bv(themap.begin(), themap.end(), [](auto& a, auto&b){ a.second!=b.second?a.second<b.second:a.first<b.first; });
for(const auto& d : bv) {
    // 
}
Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108