When to use a SortedMap interface?

Question

The rule in programming is to use the most general interface possible. But the difference between Map and SortedMap is more subtle.

• They compile to the same bytecode [I think]
• No additional safety is provided since the compiler can't tell any of the differences between the two
• SortedMap does offer an extra non-compiler-checked post condition, namely that the iterator is sorted

I would prefer code to write

SortedMap<K, V> m = new TreeMap<>();

if the sorted-ness is used. But I'm not sure if this rule only makes sense when there's compiler checks.

I'm hoping for a somewhat rigorous (e.g. type-theoretical) answer, but since this pertains to a real code review I'm doing right now, how this applies in practice is definitely important. I've yet to find an effective example of why one matters, besides a readability bump that circularly depends on programmers following this theory.

Answer 1

You use it when you want to guarantee that you are getting sorted data in a parameter, or when you want to assure the consumer of your method that you are providing sorted data.

Parameters

If you need your data to be sorted, ask for it to be sorted by asking for the interface that matches what you need. It is likely less expensive for the method sending you the data to give it to you sorted (they get it from a database and can trivially order it, but instead tossed it in a HashMap because thats what everyone uses) than it is for you to take the Map and then add it to a SortedMap.

If you need it to be sorted, ask for it to be sorted.

Return values

This one is a bit more controversial... there are differing schools of thought here.

If you are producing sorted data by the nature of your method and don't have a reason not to, return back the interface that lets the consumers of your data work with it in the most ways without giving them a concrete implementation (that locks you down).

That 'that locks you down' is part of the controversial bit. Some people will argue that you should return the least constraining (most general) interface when possible (Map rather than SortedMap and Collection rather than Set or List).

I'd go with return the most useful thing for the consumers.

I will put the caveat here that if this is something that will always be sorted, its one thing... if someone might want to subclass it later and not have it be sorted... thats another story. So you need to consider this as part of designing for extension. If it isn't going to be extended ever you get one answer from this deliberation... if it may be extended, there's another possible answer.

why is this bit above a mess and people say things about it in code review?

Well, Liskov substitution principle points out that this would make it harder to subclass later. Method parameters cannot be strengthened by a subtype and return values cannot be relaxed.

By returning a SortedMap one cannot make a later subclass of the class return a weaker type. Furthermore, if you decide to return a weaker type later for some reason it makes it a major refactoring (changing all of the SortedMaps out there to Maps and possibly changing the calls that make use of that interface into code that has to deal with the weaker type).

Your internals

It really doesn't matter what you are doing inside your own code. Use a sorted map whenever you've got sorted data and want it in a sorted order. Especially if you are doing put calls on it at various times and want it to remain in sorted order.

Now, you might be tempted to use a LinkedHashMap instead if you get all the sorted data in one go, insert it in sorted order, and then only do remove calls against it if you do any modifications. It's not wrong, and it has some advantages (O(1) lookups rather than O(log n) lookups). But, its rather inflexible only providing the get and put and none of the other fun method calls that SortedMap can give you.

Btw, NavigableMap

Actually, SortedMap doesn't give you that much more over Map. But there is something else...

SortedMap has been replaced by NavigableMap since Java 1.6 (the two standard classes that implement SortedMap also implement NavigableMap). NavigableMap has all sorts of fun method calls that are often quite useful.

Answer 2

While it is true that in programming it is a good idea to always

"use the most general interface possible"

it is even more true that

"everything should be as simple as possible --but not simpler".

So, if your code only needs to work with a Map, then your code should be given a Map and nothing more specific than that. This way, your code will work when either a Map or a SortedMap is passed to it, and the code which uses your code will be able to pass it whichever best suits its own needs.

However, if your code needs to work with a SortedMap, then you cannot somehow work around that and continue using a Map under the false pretense of keeping things simple; your code will, of course, need to be given a SortedMap. This will happen if your code needs to make use of any methods which are specific to SortedMap (do not exist in Map) i.e. comparator(), subMap(), headMap(), tailMap(), firstKey(), and lastKey().

The above was fairly self-explanatory, so I suspect that the reason why you are asking the question is because you have misunderstood what SortedMap is. So, here are a few notes about your question:

They compile to the same bytecode [I think]

SortedMap is an interface without any default methods, it does not really compile into bytecode. The .class file of that interface contains nothing but function declarations. Now, some of the methods declared by SortedMap are also declared by Map, and the reason why these declarations were duplicated in SortedMap was probably to add new documentation to them, but many methods of SortedMap do not exist in Map.

(Useful reading: What is the difference between declaration and definition in Java?)

No additional safety is provided since the compiler can't tell any of the differences between the two

Huh? This does not make any sense. I am not sure what you are thinking, but whatever it is, it is probably wrong.

SortedMap does offer an extra non-compiler-checked post condition, namely that the iterator is sorted

SortedMap begins with a doc comment which is about 4 kilobytes long, explaining what it is and how it differs from Map. I am not sure it is a good idea to summarize this as "does offer an extra non-compiler-checked post condition". Perhaps you should read the documentation.