CODEWITHSUNDEEP
c++sorting
Tengis
Tengis

Reputation: 2809

C++ sort pair with respect to two criteria

I have the following vector with pair values:

first 3  second 2
first 1  second 2
first 1  second 1
first 2  second 2

I would like to sort my vector such that the result would be

==========================
first 1  second 2
first 1  second 1
first 2  second 2
first 3  second 2

That means:

My code looks like: 

#include <utility>      // std::pair
#include <iostream>     // std::cout
#include <vector>

typedef std::pair<double, double> my_pair;
struct sort_pred
{
      bool operator () (const my_pair& left, const my_pair& right)
            {
                  return (left.first < right.first) && (left.second > right.second);
            }
};

int main () {
      std::vector<my_pair> data;
      data.push_back(my_pair(3,2) );
      data.push_back(my_pair(1,2) );
      data.push_back(my_pair(1,1) );
      data.push_back(my_pair(2,2) );

      for(auto a: data)
            std::cout << "first "<< a.first << "  second " << a.second << std::endl;

      std::cout << "==========================\n";
      std::sort(data.begin(), data.end(), sort_pred());  
      for(auto a: data)
            std::cout << "first "<< a.first << "  second " << a.second << std::endl;

      return 0;
}

The condition in the sort_pred expressed what I would like to do, but is not correct. I get wrong values.

Any idea how this can be easily solved?

Upvotes: 1

Views: 2801

Answers (7)

Daniel Jour
Daniel Jour

Reputation: 16156

You want A to be before B if

  • A first is less than B first, or
  • If A first and B first are equal and B second is less than A second

In code that is

(a.first < b.first) or
((a.first == b.first) and
 (b.second < a.second))

But this is suboptimal, from a programming point of view: Now you need an additional operator== implemented.

But since a value can only be less, equal or greater than another, you can rewrite that to

(a.first < b.first) or
(not (b.first > a.first) and
 (b.second < a.second))

Upvotes: 0

Vlad from Moscow
Vlad from Moscow

Reputation: 310990

Here you are

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

typedef std::pair<double, double> my_pair;

struct sort_pred
{
    bool operator ()( const my_pair &left, const my_pair &right ) const
    {
        return ( left.first < right.first ) || 
               ( !( right.first < left.first ) && ( right.second < left.second ) );
    }
};

int main()
{
    std::vector<my_pair> data;

    data.push_back( my_pair( 3, 2 ) );
    data.push_back( my_pair( 1, 2 ) );
    data.push_back( my_pair( 1, 1 ) );
    data.push_back( my_pair( 2, 2 ) );

    std::stable_sort( data.begin(), data.end(), sort_pred() );

    for ( const auto &p : data ) std::cout << p.first << ' ' << p.second << std::endl;
}

The program output is

1 2
1 1
2 2
3 2

Upvotes: 0

DerickThePoney
DerickThePoney

Reputation: 75

I think your predicate is wrong ?

If I understand correctly, you want precedence on the first element, and only in case of equality on the second element?

so maybe something like:

struct sort_pred
{
     bool operator () (const my_pair& left, const my_pair& right)
           {
                 return (left.first == right.first) ? 
                        (left.second > right.second) : 
                        (left.first < right.first);
           }
};

Upvotes: 0

Barry
Barry

Reputation: 303087

Your comparator isn't quite right, since you want it to return true if either the first check succeeds OR the first are equal and the second check succeeds. You only want to check the seconds if the firsts are equal. So something like this:

struct sort_pred
{
    bool operator()(const my_pair& left, const my_pair& right) const
    {
        if (left.first != right.first) {
            return left.first < right.first;
        }
        return left.second > right.second;
    }
};

This can be simplified using the fact that tuples are lexicographically comparable:

struct sort_pred
{
    bool operator()(const my_pair& left, const my_pair& right) const
    {
        return std::tie(left.first, right.second) < 
               std::tie(right.first, left.second);
    }
};

Upvotes: 7

peterchen
peterchen

Reputation: 41106

You have to distinguish more cases:

bool operator () (const my_pair& left, const my_pair& right)
{
   if (left.first < right.first)
      return true;

   if (left.first != right.first)
      return false;

    // when primary criterion is equal:
    if (left.second > right.second) 
           // you want this to sort descending, right?
      return true;

    // .... other criteria

    return false;
}

Upvotes: 0

QuestionC
QuestionC

Reputation: 10064

Your use of && doesn't really make sense. It goes on to evaluate the second element if left.first > right.first, but really you want that to only happen if left.first == right.first.

This should work:

  bool operator () (const my_pair& left, const my_pair& right)
        {
              if (left.first != right.first)
                  return left.first < right.first;
              else
                  return left.second > right.second;
        }

Upvotes: 0

TartanLlama
TartanLlama

Reputation: 65620

This is possible with a bit of tweaking to your predicate:

struct sort_pred
{
    bool operator () (const my_pair& lhs, const my_pair& rhs)
    {
        return lhs.first<rhs.first || 
               (!(rhs.first<lhs.first) && lhs.second>rhs.second);
    }
};

Live demo

Upvotes: 0

Related Questions