Can STL or Boost help sort a map by value?
The word "sort" in the title can be misleading. I am looking for this behavior:
{ 1: 100, { 1: 1,
3: 10, => 3: 10,
5: 1000, 5: 100,
9: 1 } 9: 1000 }
That is, reassign the values to the existing keys in ascending order.
It's not hard to do this with a temporary:
using K = int;
using V = int;
std::map<K, V> myMap{ {1, 100}, {3, 10}, {5, 1000}, {9, 1} };
std::vector<V> tempVec; // insert map values into vector
std::transform(myMap.begin(), myMap.end(), std::back_inserter(tempVec),
[](auto const& mapPair) { return mapPair.second; });
std::sort(tempVec.begin(), tempVec.end());
size_t i = 0;
for (auto& mapPair : myMap) {
mapPair.second = tempVec[i++];
}
Can this be simplified or even better done on site?
source to share
If we don't need an efficient algorithm, we can simply implement sorting.
for (auto mi = myMap.begin(); mi != myMap.end(); ++mi) {
auto const& mini = min_element(mi, myMap.end(), [](auto const& pa, auto const& pb) { return pa.second < pb.second; });
swap(mi->second, mini->second);
}
source to share
You cannot sort the map by value.
Since it std::map
organizes records by key to accomplish this task (like O(log n)
search and insert), there is no way to change this behavior.
However, you can use std::set<YourType>
where YourType
is a tuple (for example, std::pair
or a custom type as shown below) and you provide your custom comparison operator so that the set is organized by value.
struct YourType {
int key;
int value;
bool operator<(const YourType& other) const {
return std::tie(value, key) < std::tie(other.value, other.key);
}
};
source to share