Java: SortedMap, TreeMap, Comparable? How to use?

Question

I have a list of objects I need to sort according to properties of one of their fields. I've heard that SortedMap and Comparators are the best way to do this.

1. Do I implement Comparable with the class I'm sorting, or do I create a new class?
2. How do I instantiate the SortedMap and pass in the Comparator?
3. How does the sorting work? Will it automatically sort everything as new objects are inserted?

EDIT: This code is giving me an error:

private TreeMap<Ktr> collection = new TreeMap<Ktr>();

(Ktr implements Comparator<Ktr>). Eclipse says it is expecting something like TreeMap<K, V>, so the number of parameters I'm supplying is incorrect.

Answer 1

1. The simpler way is to implement Comparable with your existing objects, although you could instead create a Comparator and pass it to the SortedMap.
   Note that Comparable and Comparator are two different things; a class implementing Comparable compares this to another object, while a class implementing Comparator compares two other objects.
2. If you implement Comparable, you don't need to pass anything special into the constructor. Just call new TreeMap<MyObject>(). (Edit: Except that of course Maps need two generic parameters, not one. Silly me!)
   If you instead create another class implementing Comparator, pass an instance of that class into the constructor.
3. Yes, according to the TreeMap Javadocs.

---

Edit: On re-reading the question, none of this makes sense. If you already have a list, the sensible thing to do is implement Comparable and then call Collections.sort on it. No maps are necessary.

A little code:

public class MyObject implements Comparable<MyObject> {
    // ... your existing code here ...
    @Override
    public int compareTo(MyObject other) {
        // do smart things here
    }
}

// Elsewhere:
List<MyObject> list = ...;
Collections.sort(list);

As with the SortedMap, you could instead create a Comparator<MyObject> and pass it to Collections.sort(List, Comparator).

Answer 2

My answer assumes you are using the TreeMap implementation of SortedMap.

1.) If using TreeMap, you have a choice. You can either implement Comparable directly on your class or pass a separate Comparator to the constructor.

2.) Example:

Comparator<A> cmp = new MyComparator();
Map<A,B> map = new TreeMap<A,B>(myComparator);

3.) Yes that's correct. Internally TreeMap uses a red-black tree to store elements in order as they are inserted; the time cost of performing an insert (or retrieval) is O(log N).

Answer 3

You make a Comparator<ClassYouWantToSort>. Then the Comparator compares the field that you want to sort on.

When you create the TreeMap, you create a TreeMap<ClassYouWantToSort>, and you pass in the Comparator as an argument. Then, as you insert objects of type ClassYouWantToSort, the TreeMap uses your Comparator to sort them properly.

EDIT: As Adamski notes, you can also make ClassYouWantToSort itself Comparable. The advantage is that you have fewer classes to deal with, the code is simpler, and ClassYouWantToSort gets a convenient default ordering. The disadvantage is that ClassYouWantToSort may not have a single obvious ordering, and so you'll have to implement Comparables for other situations anyway. You also may not be able to change ClassYouWantToSort.

EDIT2: If you only have a bunch of objects that you're throwing into the collection, and it's not a Map (i.e. it's not a mapping from one set of objects to another) then you want a TreeSet, not a TreeMap.

Answer 4

1.

That depends on the situation. Let's say the object A should sort before the object B in your set. If it generally makes sense to consider A less than B, then implementing Comparable would make sense. If the order only makes sense in the context in which you use the set, then you should probably create a Comparator.

2.

new TreeMap(new MyComparator());

Or without creating a MyComparator class:

new TreeMap(new Comparator<MyClass>() {
    int compare(MyClass o1, MyClass o2) { ... }
});

3. Yes.

Answer 5

Since you have a list and get an error because you have one argument on the map I suppose you want a sorted set:

SortedSet<Ktr> set = new TreeSet<Ktr>(comparator);

This will keep the set sorted, i.e. an iterator will return the elements in their sort order. There are also methods specific to SortedSet which you might want to use. If you also want to go backwards you can use NavigableSet.