search

dart-lang / sdk

The Dart SDK, including the VM, JS and Wasm compilers, analysis, core libraries, and more.
https://dart.dev
BSD 3-Clause "New" or "Revised" License
10.06k stars 1.56k forks source link

introduce SortedMap interface that SplayTreeMap implements? #5611

Closed jmesserly closed 6 years ago

jmesserly commented 11 years ago

It would be really nice to have "SortedSet" and "SortedMap". SplayTreeMap works great, but the name contains implementation details. It we decide at some time down the road that we want to implement it with some other kind of binary search tree, it won't be very good.

Also as a user, I find myself frequently adding comments like "using SplayTreeMap to keep this sorted so we iterate in a stable order". Whereas "SortedMap" would be a self documenting name.

dgrove commented 11 years ago

Removed Library-Collections label. Added Library-Collection label.

lrhn commented 11 years ago

We probably want a different sorted map too, with more predictable performance. If that happens, we could add SortedMap as superclass for those.

Removed Type-Defect label. Added Type-Enhancement label.

jmesserly commented 10 years ago

+1, nice idea. out of curiosity, what data structure were you thinking? classic RB-tree?

lrhn commented 10 years ago

Never answered this. It'll most likely be an AVL tree - it's simple to implement and usually at least as efficient as a Red/Black tree.

jmesserly commented 9 years ago

updated subject based on https://github.com/dart-lang/sdk/issues/5611#issuecomment-108333802 ... since renaming it won't happen at this point :)

ghost commented 2 years ago

I feel that introducing OrderedMap, SortedMap, OrderedSet, and SortedSet would benefit the language since they allow developers to be more expressive with their code by using abstract data types as opposed to using data structures like SplayTreeMap to express the usage of a Sorted Map, or even worse, using Map as a catch-all.

Also, this would allow Map and Set to use HashMap and Hashset data structures, respectively, by default instead of their current default LinkedHashMap and LinkedHashSet implementations which are less efficient and unnecessarily ordered (since a Map is an unordered abstract data type).