-
Notifications
You must be signed in to change notification settings - Fork 17.9k
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
proposal: Go 2: add native type for map that maintains key order #41289
Comments
For language change proposals, please fill out the template at https://go.googlesource.com/proposal/+/refs/heads/master/go2-language-changes.md . When you are done, please reply to the issue with @gopherbot please remove label WaitingForInfo. Thanks! |
|
@gopherbot please remove label WaitingForInfo |
It seems to me that the right approach here is to use generics if they are added to the language. For example, there is a simplistic possible implementation at https://go.googlesource.com/go/+/refs/heads/dev.go2go/src/cmd/go2go/testdata/go2path/src/orderedmap/orderedmap.go2 . If we do add generics to the language, I don't see any reason to also add an ordered map type. |
I agree this could be done using generics. The specific implementation pointed to above would not work though as it does not maintain order of initialisation and I couldn't think if a way to do this programmatically. There are more disadvantages:
|
Could you explain why not? I dont think the std lib is prohibited from using generics once the compiler supports them. Changing the stdlib API if a type is exposed would need to be done with generics and with a new map type and both times break backward compatibility. |
I guess it wouldn't, but stdlib would need to chose the specific implementation that provides the behaviour described. Changing the default map implementation would give that for free wherever it is used today. Is there a particular reason why the standard map implementation should retains its per-default indeterministic range behaviour? |
Sorted maps are slower. Changing the default map type to be sorted would penalise everyone who does not need a sorted map implementation or has already written code to sort keys when required. |
In addition, not all keys have orderable types. For example, in what order do |
Based on the discussion above, this is a likely decline. Perhaps if we do not accept generics into the language we can revisit this idea. Leaving open for four weeks for final comments. |
@randall77 I did not request a map with orderable ytpes. I did request a map than maintains given key order where order is order of initialization. |
Ah, sorry, I misunderstood. |
Simple wrapper with combination double-linked list of keys (to preserve order of insertion) and map[key]value solves this problem quite well. You can even make map[key](value, pointer-to-key-in-list) so it would be actually cheap to delete elements. It's quite simple in implementation With generics it may be reasonable to have some sort of pkg "collections" with this and others map included. Currently I don't see any reason to have new builtin type or changing the semantics of existing. |
I understand this is gonna be declined. The downside with all "do it yourself" responses is that stdlib will not profit from such approaches. If you see the examples initially given ( Thank you for the insightful discussion! |
Currently, Go maps are unordered, i.e. ranging over a map happens in unspecified order. There are several use cases that could profit from an ordered map type. Examples are #27179, #27050, #6244, #24375.
An additional example is
url.Values.Encode()
which is a native map and sorts keys when encoding which makes it unusable with certain apis.While it is possible to created custom ordered map types, initialisation is cumbersome and they are not used by core types like
url.Values
(e.g. https://github.com/mickep76/mapslice-json).I'm proposing to either:
a) make the native map type maintain keys in order of initialisation or
b) add an ordered map type that maintains key order and use that map type in the standard library where applicable
Both approaches would break the compatibility promise as- in order to reap the benefit- additional changes to the standard library would be necessary.
The text was updated successfully, but these errors were encountered: