When to use a SortedMap interface?

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.