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

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;

CodePudding user response：

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.