Why do we need a TreeMap/TreeSet when we have SortedMap/SortedSet?

Question

Ok so SortedMap / SortedSet is an interface, and TreeMap / TreeSet is it's implementation. Both of them keep the elements in sorted order, right? So why do we need TreeMap / TreeSet?

Answer 1

Interfaces do not provide any functionality, they just define the general outline of a class in terms of the methods it provides. But there's no code inside SortedMap/SortedSet that implements how to actually achieve this functionality.

And as a matter of fact, you can often have multiple ways to realize the same functionality. Think of the interface java.util.Set: you could implement it as a TreeSet but also as a HashSet. Usually, there are some trade-offs between different implementations: a hashset might provide faster access times on average, while a tree set may be better at keeping the order of its items.

Often enough, however, a developer doesn't really care about the implementation details, as long as they know that they can store items in a set and retrieve them. That basic idea, but not how to achieve it, is defined by the interface.

This is also the reason you cannot instantiate an interface. If you try the following:

SortedSet<Integer> set = new SortedSet<Integer>();

your compiler will complain. That is because "SortedSet" does not really realize a set itself, it just defines what an implementation of a sorted set must provide in terms of methods.

Here's a contrived example. Imagine you want to offer a functionality to compute the percentage of positive integers in a set. You could define a method:

public double getPercentageOfPositives(Set<Integer> set) {
    if (set.size() == 0) {
        return 0.0;
    }

    int count = 0;

    for (Iterator<Integer> iter = set.iterator(); iter.hasNext();) {
        if (iter.next() > 0) count++;
    }

    return 100.0 * count / set.size();
}

Here, you don't really care whether the user of your method gives you a TreeSet or a HashSet. It doesn't matter which principle the given class uses, because you're just calling the size() method and the iterator() method anyway. All you need is trust in the fact that any set will have these two methods. An interface gives you that trust.

Therefore your method signature only asks for a Set, which is an interface that defines that all classes implementing it must provide (amongst others) a size() and an iterator() method. If you wrote it like this:

public double getPercentageOfPositives(SortedSet<Integer> set) {
    ...
}

and I have an instance of HashSet then I couldn't use your method even though HashSet provides size() and iterator() as well. :-(

In that sense, an interface is like a super-class, it defines the commonalities that all classes must have that implement it. But it does not provide any functionality itself.

Thus to come back to your original example of SortedSet: this interface does not provide any functionality. It merely defines which methods a sorted set implementation must provide. TreeSet is such an implementation.

The same line of thought applies to SortedMap.