That's an interesting perspective on the matter. I had intended SortedMap as "I internally maintain an ordering of the elements, and therefore it is relatively cheap to perform operations associated with ordering". So your idea is to e.g. allow HashMap to impl a very inefficient SortMap? Or are there some structures you know of that support fast order-based operations that don't maintain an internal sorting?