[C++] How should I compare pairs of pointers (for sort predicate)

Question

I have a STL container full of billions of the following objects

pair<SomeClass*, SomeClass*>

I need some function of the following form

/*returns items sorted biggest first */

bool sortPredicate (pair<SomeClass*, SomeClass*>two,  pair<SomeClass*, SomeClass*> one)
{
  return ???;
}

Is there some trick I can use to very quickly compare pairs of pointers?

Edit 1: A clarification

In the end I just want to sort the list of pointer-pairs such that all of the duplicates are next to each other. Assume that there is no clear method in SomeClass that can be used for this purpose---I only have pointer pairs, and I want to find all identical pairs (in parallel). I thought a sort would do the trick, but if you can think of a better parallel method, let me know.

Edit 2: A clarification

Fixed my code (the arguments to the sort predicate were wrong--they should be pairs).

Answer 1

Assuming your class has comparison operators:

bool sortPredicate (SomeClass *two,  SomeClass *one)
{
  return *two > *one;
}

If you just want to compare the pointer addresses, use std::greater<T>:

sort(container.begin(), container.end(), std::greater<SomeClass *>());

EDIT: OK, I really have no idea what you are trying to do now, with your most recent edit. Why not just use the default sort, if all you want to do is find duplicates?

Answer 2

If I understand correctly Your predicate should have the following signature

bool sortPredicate(pair<SomeClass*, SomeClass*>& lhs, pair<SomeClass*, SomeClass*>& rhs);

I know nothing about Your class and if there is any natural order for it, so it's hard to guess how You want to sort it. In The comment You write that the biggest items should be first. I assume there is < operator for the class. How about this?

bool sortPredicate(pair<SomeClass*, SomeClass*>& lhs, pair<SomeClass*, SomeClass*>& rhs)
{
    if(!(*(lhs.first) < *(rhs.first) || *(rhs.first) < *(lhs.first))) // If there is == operator use it.
    {
        return *(rhs.second) < *(lhs.second);
    }
    else
    {
        return *(rhs.first) < *(lhs.first);
    }

}

EDIT: Ok thx for clarifying. How about this?

bool sortPredicate(pair<SomeClass*, SomeClass*>& lhs, pair<SomeClass*, SomeClass*>& rhs)
{
    if(lhs.first == rhs.first)
    {
        return rhs.second < lhs.second;
    }
    else
    {
        return rhs.first < lhs.first;
    }
}

Answer 3

You should define an operator<on your pair class. I assume that your pair holds item1 and item2. So:

template <class T>
class pair{
private:
  T item1;
  T item2
public:
  // [...] other stuff goes here
  // here the comparing
  bool operator<(pair p){
    return (item1 < p.item1 || (item1 == p.item1 && item2 < p.item2));
  }
};

This solution assumes that the items have defined the < and the == operators.

I suppose I didn't meet what you were exactly looking for, but I recommend to overload the <, >, and == operators in your pair class.

Answer 4

It is a quirk of C++ that arbitrary pointers of the same type are not (necessarily) comparable with <, but are comparable with std::less.

Unfortunately, the operator< for std::pair is defined in terms of operator< on the components, not std::less.

So, assuming that you want two pairs to fall in the same sort position if and only if they point to the same two objects, you need:

// "less than"
template<typename T>
bool lt(const T &lhs, const T &rhs) {
    return std::less<T>()(lhs, rhs);
}

typedef std::pair<SomeClass*, SomeClass*> mypair;

bool sortPredicate(const mypair &lhs, const mypair &rhs) {
    return lt(lhs.first, rhs.first) 
        || (!lt(rhs.first, lhs.first) && lt(lhs.second, rhs.second));
 }

On pretty much any system you can name, this should compile to the same code as return lhs < rhs;, but that is not formally correct. If the referands of the pointers are all subobjects of the same object (for instance if you have a huge array and all the pairs point to elements of that one array), then operator< is OK for the pointers and hence OK for std::pair<pointer,pointer>.

If you want to pairs to fall in the same sort position if and only if the objects they point to sort the same, then you'd add the extra dereference:

bool sortPredicate(const mypair &lhs, const mypair &rhs) {
    return lt(*lhs.first, *rhs.first) 
        || (!lt(*rhs.first, *lhs.first) && lt(*lhs.second, *rhs.second));
 }

and perhaps you'd also add checks for null pointers, if those are permitted. Of course if you know that SomeClass really is a class type, not a pointer type, then you don't need to use std::less in the version above, just define operator< for SomeClass and:

inline bool lessptr(const SomeClass *lhs, const SomeClass *rhs) {
    if (lhs == 0) return rhs != 0;
    if (rhs == 0) return false;
    return *lhs < *rhs;
}

bool sortPredicate(const mypair &lhs, const mypair &rhs) {
    return lessptr(lhs.first, rhs.first) 
        || (!lessptr(rhs.first, lhs.first) && lessptr(lhs.second, rhs.second));
 }

You may or may not be able to optimise that a bit, since there are some repeated null checks performed in both the first and second calls to lessptr. If you care that much, see what the compiler does with it.