C++ - Sort map based on values, if values same sort based on key

Question

I came across a problem where I needed to store two values, one id and other its influence, and id should be randomly accessible. Also it should be sorted based on influence and if both influence are same , sort based on id. With these things in mind, I used map,but is there a way to actually do it ?

I tried below comparator and map but it gives error

struct cmp
{
 bool comparator()(const pair<int,int>a,const pair<int,int>b)
 {
    if(a.second==b.second) return a.first<b.first;
    else return a.second<b.second;
 }
};

unordered_map<int,int,cmp>m;

`std::map` calls it's compare with the `first` of the `std::pair`s that it stores — Caleth, Oct 28 '22 at 11:26
`unordered_map` uses `std::hash` on *the key* by default, so it's also not a good fit for your use case. You may want a set instead of a map. — kotatsuyaki, Oct 28 '22 at 11:30
@kotatsuyaki .. id should be accessible means i should be able to change the influence for a given ID. thats why I have used map instead of set — learner, Oct 28 '22 at 11:32
To sum up your requirements, **1)** To be able to access and update "influence" based on the "id" **2)** To have the collection always sorted first by "id" and then by "influence". With these requirements, why are you using an `unordered_map`? Are you aware that `unordered_map` is based on hashing instead of comparing? Or is maintaining the order not strictly required? — kotatsuyaki, Oct 28 '22 at 11:41
@kokatsuyaki Correction -2.) the nodes should be sorted first by "influence" then by "id". I am aware of that. What should I use then — learner, Oct 28 '22 at 11:43
Does this answer your question? [How can I sort a std::map first by value, then by key?](https://stackoverflow.com/questions/19842035/how-can-i-sort-a-stdmap-first-by-value-then-by-key) — kotatsuyaki, Oct 28 '22 at 11:53
@learner It is fundamentally impossible to have a container that is sorted by some value, while that value is also mutable. If you change the value, the container may become unsorted. You need to remove the old value and reinsert the new value. — François Andrieux, Oct 28 '22 at 12:00

score 3 · Accepted Answer · answered Oct 28 '22 at 12:01

From what I understand, you want a collection sorted by one value but quickly indexable by another. These two points are in contradiction. Sorting a collection by a key value makes it quicker to index by that key value. There is no easy way to make a collection quickly indexable in two different ways at the same time. Note that I say "quickly indexable" instead of talking about random access. That's yet a different concept.

In short, you need two collections. You can have a main one that stores influence-ID pairs and is sorted by influences, and a secondary one that stores IDs and maps them to the main collection. There are many options for that; here is one:

std::set<std::pair<int,int>> influences;
std::unordered_map<int, decltype(influences)::iterator> ids;

When inserting an influence-ID pair, you can insert into influence first and then take the iterator to that new element and insert it with the ID.

Another solution is to keep a main collection of influence-ID pairs but this time sorted by IDs (and binary search it when you need to get the influence from an ID), and maintain a array of permutation indices that tells you at what index an element of the main collection would be if it were sorted by influence. Something like this:

std::vector<std::pair<int,int>> influences;
// insert all elements sorted by ID
std::vector<decltype(influences)::size_type> sorted_indices;
// now sort by influences but modifying `sorted_indices` instead.

Relevant question

If the IDs are all from 0 to N, you can even just have influences indexed by ID:

std::vector<int> influences; // influences[id] is the influence value corresponding to id

This gives you random access.

The "correct" choice depends on the many other possible constraints you may have.

C++ - Sort map based on values, if values same sort based on key

1 Answers1