porting C++ sort function to Java

Question

I have a problem porting c++ code to Java. I have a list of pair as follows

vector<pair<pair<int,int>,int> > M;

I wrote the equivalent in Java as follows

List<Pair<Pair<Integer,Integer>,Integer>> pairList = new ArrayList<>();

Now in c++ code , M is filled with values and correspondingly I did the same in Java. Now down the line, c++ has a sort functionality as follows

sort(M.begin(), M.end());

Here is my problem, what is the equivalent comparator I need to write in Java? How do I use it ? I am assuming something of the following lines

Collections.sort(pairList, new MyComparator())

Could anyone help me understand what would be MyComparator ?

Pair class is as follows

class Pair<K,V>{

    K k;
    V v;

    public void makePair(K k, V v){     
        this.k = k;
        this.v = v;
    }
}

Solution

I ended up implmenting MyComparator as follows

static class MyComparator implements Comparator<Pair<Pair<Integer,Integer>,Integer>>{

    @Override
    public int compare(Pair<Pair<Integer,Integer>,Integer> p1,Pair<Pair<Integer,Integer>,Integer> p2){

        int a = p1.k.v.compareTo(p2.k.v);
        if(a==0) return a;
        else return p1.k.k.compareTo(p2.k.k);
    }
 }

Thank you all.

Where does the Java side `Pair` come from (it's not standard)? If it does compare lexicographically (like the C++ pair), the comparator is unnecessary. — dhke, Jul 06 '15 at 10:42
possible duplicate of [How to use Comparator in Java to sort](http://stackoverflow.com/questions/2839137/how-to-use-comparator-in-java-to-sort) — Rodolfo, Jul 06 '15 at 10:48
Be careful, your makePair method should be a constructor with the name Pair. — Sébastien Doncker, Jul 06 '15 at 10:51
Looks like you're misusing pairs, so you should create the new structure instead of this `triple`. — Dmitry Ginzburg, Jul 06 '15 at 10:55

score 1 · Answer 1 · answered Jul 06 '15 at 10:50

Your Comparator should be a class implementing the interface Comparator<T>. T is the generic type associated with your collection.

For you it's Pair<Pair<Integer,Integer>,Integer>.

So you should have a class like that :

public Class MyComparator implements Comparator<Pair<Pair<Integer,Integer>,Integer>> {

    @Override
    public int compare(Pair<Pair<Integer,Integer>,Integer> o1, Pair<Pair<Integer,Integer>,Integer> o2) {
        // Here you should put your comparison code :
        // return 0 if the 2 objects are the same
        // return -1 (or another negative int) if the o2 > o1
        // return 1 (or another positive int) if o2 < o1

    }

}

score 0 · Answer 2 · edited Jul 06 '15 at 10:53

0

MyComparator needs to implement Comparator so that Java knows how to compare the elements on your list. It can be done in two forms Comparator or Comparable.

A pretty good example is here.

edited Jul 06 '15 at 10:53

Mr. Polywhirl

42,981
12
84
132

answered Jul 06 '15 at 10:52

Rodolfo

1,091
3
13
35

Thanks @mr-polywhirl, I were about to insert the links for the Javadoc like you did so. – Rodolfo Jul 06 '15 at 11:03

score 0 · Answer 3 · answered Jul 06 '15 at 10:58

You can avoid the comparator altogether by making the java Pair class behave like the C++ std::pair. Apache Commons Lang has a Pair that does what you want.

However: Why not use a proper custom data class instead of nested pairs? I already consider the C++ version quite cumbersome.

If you don't want to use it, roll your own:

class Pair<K extends Comparable<K>,V extends Comparable<V>>
   implements Comparable<Pair<K, V>> 
{
   // have a immutable pairs
   final K k;
   final V v;

   Pair(final K k, final V v)
   {
       this.k = k;
       this.v = v;
   }

   // factory function, the same as in C++ 
   // (where it exists because template syntax is akward)
   // (as is generics syntax)
   public static <K extends Comparable<K>, V extends Comparable<V>> Pair<K, V> makePair(K k, V v)
   {     
         return new Pair(k, v);
   }

   @override
   public int compareTo(final Pair<K, V> other)
   {
        int compare = this.k.compareTo(other.k);
        if (compare == 0) {
            compare = this.v.compareTo(other.v);
        }
        return compare;
   }

   // NOTE: we also need equals() and hashCode() for a proper class.
}

I'd try to refrain from writing an implicit Comparator and pass it to the sort function, unless you need special cased sort.

porting C++ sort function to Java

3 Answers3