Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

introduce SortedMap interface that SplayTreeMap implements? #5611

Closed
jmesserly opened this issue Oct 2, 2012 · 6 comments
Closed

introduce SortedMap interface that SplayTreeMap implements? #5611

jmesserly opened this issue Oct 2, 2012 · 6 comments
Labels
area-core-library SDK core library issues (core, async, ...); use area-vm or area-web for platform specific libraries. closed-obsolete Closed as the reported issue is no longer relevant core-n library-collection P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug

Comments

@jmesserly
Copy link

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
Copy link
Contributor

dgrove commented Jan 11, 2013

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

@lrhn
Copy link
Member

lrhn commented Aug 19, 2013

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
Copy link
Author

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

@lrhn
Copy link
Member

lrhn commented Jan 29, 2014

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 jmesserly added Type-Enhancement area-core-library SDK core library issues (core, async, ...); use area-vm or area-web for platform specific libraries. library-collection labels Jan 29, 2014
@jmesserly jmesserly changed the title rename SplayTreeMap to SortedMap introduce SortedMap interface that SplayTreeMap implements? Jun 3, 2015
@jmesserly
Copy link
Author

updated subject based on #5611 (comment) ... since renaming it won't happen at this point :)

@jmesserly jmesserly mentioned this issue Sep 17, 2015
Closed
@kevmoo kevmoo added P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug and removed triaged labels Feb 29, 2016
@lrhn lrhn added the core-m label Aug 11, 2017
@floitschG floitschG added core-n and removed core-m labels Aug 29, 2017
@matanlurey matanlurey added the closed-obsolete Closed as the reported issue is no longer relevant label Jun 21, 2018
@ghost
Copy link

ghost commented Jul 24, 2022

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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
area-core-library SDK core library issues (core, async, ...); use area-vm or area-web for platform specific libraries. closed-obsolete Closed as the reported issue is no longer relevant core-n library-collection P2 A bug or feature request we're likely to work on type-enhancement A request for a change that isn't a bug
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
6 participants
@kevmoo @matanlurey @jmesserly @dgrove @lrhn @floitschG