CODEWITHSUNDEEP
c++sortingdictionarykey-value
user15849957
user15849957

Reputation:

Sort a map on the basis of first value of pair

Suppose I have to describe my map as:

map<int, pair<long, int>> mp;

Now I insert elements as:

int y; long x;
pair<long, int> p;

for(int i = 0; i < 5; i++)
{ 
    cin >> x >> y;
    p.first = x;
    p.second = y;
    mp.insert({i, p});   // What is wrong here syntax wise?
}

Further, I want to sort it on the basis of first value of the pair.

Upvotes: 0

Views: 477

Answers (2)

Serge Ballesta
Serge Ballesta

Reputation: 148890

A std::map in indexed and ordered by its key. Full stop.

I can only imagine 2 possible ways to have it sorted according to its values:

  • reverse the struct to have the element giving the order as the key (this is @Suspicio's answer)
  • use what is called a secondary index in database world, that is an auxialiary thing that will be sorted according to your requirements and point to the real data.

Here, I would use either a vector of integers (the keys to your actual map) if you can accept to sort it once before using it (said differently if you map does not change once populated) or a std::multimap if you want to be able to easily add (or remove) items.

multimap<long, int> indices;
for (auto elt : mp) {
    indices.insert({ elt.second.first, elt.first });
}

You can now the process your sorted map:

for (auto index : indices) {
    auto elt = mp.find(index.second); // *elt will give the elements in order
    ...
}

You just have to update the indices multimap whenever you add or remove elements to your original mp map.

Upvotes: 0

Suspicio
Suspicio

Reputation: 341

You can use a little trick here.

Map in c++ automatically sorts everything by key, so you can do following =>

map <long, (set,vector) < int > > mp; //Create this kind of map
//it will sort elements by first value and depending on your needs, select vector or set
//if you need to sort elements by second value use set
//if you do not care about it use vector

long x;
int y;
for (int i = 0; i < n; i++)
{
   cin >> x >> y;
   if (mp.find(x) != mp.end()) // if element exist
      {
         mp[x].push_back(y); // add it to vector
      }
      else
      {
         mp[x] = vector < int > (); // if not create new vector
         mp[x].push_back(y); // and then push new element
      }
}

Upvotes: 1

Related Questions