0

Actually, I'm trying to sort the map by the values stored in them.

The map by default has the sort function (greater<int>) applied to the key values but this is not providing the functionality to sort by value directly. Please let me know if any alternative available???

Any help will be appreciated...

Soni-Sumit-Raghukant
  • 28
  • 7
  • 4
    A `std::map` can only ever be sorted by the key. You need to invert the key and the value, or look at `std::set`. – François Andrieux Aug 18 '23 at 17:55
  • 1
    If you want a map sorted on both key and value then standard C++ does not have anything like that. But you could use boost's [bimap](https://www.boost.org/doc/libs/1_83_0/libs/bimap/doc/html/index.html) container instead. – john Aug 18 '23 at 17:58
  • You already understand that a map is sorted by the key, I don't understand why you want it sorted in a way it can't do. Try copying it to a vector – Mark Ransom Aug 18 '23 at 17:59
  • There is no guarantee on unique value fields. What is your expectation when there are multiple values assigned to different keys? – Thomas Matthews Aug 18 '23 at 20:40
  • 1
    You cannot sort a map. It is always ordered such that the keys are in a non-decreasing order. It cannot exist in any other state. The order is fixed, so there is no `sort` function. Any desire to sort a map is grounded in a misunderstanding. – n. m. could be an AI Aug 18 '23 at 21:39

3 Answers3

0

you are looking for a set which sorts based on values, and allows lookup of values, it basically has no keys.

if you want to get the key corresponding to a certain value in the map, then you should create another map which has the keys and values of the first map reversed, and just do the lookup in it, or have the value of the second map be a vector of "keys" if your "values" are not unique.

Ahmed AEK
  • 8,584
  • 2
  • 7
  • 23
0

You cannot sort the map itself, but you can kind of create a sorted view on the values like this :

#include <iostream>
#include <map>
#include <functional>
#include <vector>
#include <algorithm>
#include <iterator>

auto sorted_view_of_values(const std::map<int, int>& values)
{
    std::vector<std::reference_wrapper<const int>> view;
    std::transform(values.begin(), values.end(), std::back_inserter(view), [](const auto& pair) { return std::reference_wrapper(pair.second); });
    std::sort(view.begin(), view.end(), [](const auto& lhs, const auto& rhs) {return lhs < rhs; });
    return view;
}

int main()
{
    std::map<int, int> values{ {1,10}, {3,30}, {2,20} };
    auto sorted_view = sorted_view_of_values(values);

    for (const auto value : sorted_view)
    {
        std::cout << value << " ";
    }

    return 0;
}
Pepijn Kramer
  • 9,356
  • 2
  • 8
  • 19
0

The general idea is that you need another data structure to help you achieve this, because your map is already sorted based on keys (the sorting for std::map is done during insertion of nodes).

First you need to define whether you just need the sorted values of the map or you need to preserve the pairs to be able to access the keys after sorting based on value.

For the first option:

Use std::set

Use std::set only if you don't need the duplicate values. Also beware that insertion, deletion, and search has O(log(n)) complexity.

Use std::vector

Using std::vector can allow you to keep duplicates, however the std::vector component is not sorted by default so you'd need a call to std::sort after insertion. So total complexity will be O(N) for copying the values, and O(Nlog(N)) for sorting.

For the second option:

You can use std::map or std::vector. You can refer the following link that shows how to do this using a transformed map or vector. Sorting std::map using value

Your choice in the end of what data structure to use should be judged by how this data structure will be used for the rest of the program.

Sarah Essam
  • 27
  • 2