Remove pairs in a vector sharing the same first element, but keep the pair containing the largest second element

Question

Let's say the elements of the vector of pairs are

1, 0
2, 0
1, 2
2, 4
4, 0
5, 0

The output should be

1, 2
2, 4
4, 0
5, 0

In the above example, the pairs {1, 0}, and {1, 2} are replaced by the pair {1, 2}, since they share the same first element (1), and the largest second element is (2).

I tried to use set and make the vector unique based on the first element but this doesn't fulfill my second condition.

Answer 1

I suspect that you are trying to do this (in which case nisssh's now-deleted answer should have prior recognition). Efficient? Well, depends what you are actually trying to do ultimately. It would have been better to use a map from the start.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main()
{
   vector<pair<int,int>> input = { { 1, 0 }, { 2, 0 }, { 1, 2 }, { 2, 4 }, { 4, 0 }, { 5, 0 } };
// vector<pair<int,int>> input = { { 1, 2 }, { 2, 4 }, { 4, 0 }, { 5, 0 }, { 1, 0 }, { 2, 0 } };        // check both

   map<int,int> M;
   for ( auto [ p, q ] : input )
   {
      if ( M.count( p ) ) M[p] = max( M[p], q );
      else                M[p] = q;
   }

   vector<pair<int,int>> output( M.begin(), M.end() );
   for ( auto [ p, q ] : output ) cout << p << " " << q << '\n';
}

Output:

1 2
2 4
4 0
5 0

EDIT If you want to use "sort and unique" (as in cigien's comment) then this would work. Output order may or may not be acceptable.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using PR = pair<int,int>;

int main()
{
   vector<PR> input = { { 1, 0 }, { 2, 0 }, { 1, 2 }, { 2, 4 }, { 4, 0 }, { 5, 0 } };
// vector<PR> input = { { 1, 2 }, { 2, 4 }, { 4, 0 }, { 5, 0 }, { 1, 0 }, { 2, 0 } };        // check both

   sort( input.begin(), input.end(), greater<PR>() );
   input.erase( unique( input.begin(), input.end(), []( PR a, PR b ){ return a.first == b.first; } ), input.end() );

   for ( auto [ p, q ] : input ) cout << p << " " << q << '\n';
}

Output:

5 0
4 0
2 4
1 2

Answer 2

You might std::sort by increasing first and decreasing second, then use std::unique based on first:

std::sort(v.begin(), v.end(),
          [](const auto& lhs, const auto& rhs) {
              return std::tie(lhs.first, rhs.second) < std::tie(rhs.first, lhs.second);
          });
v.erase(std::unique(v.begin(), v.end(),
                    [](const auto& lhs, const auto& rhs){
                        return lhs.first == rhs.first; }),
         v.end());

Demo.