go
go copied to clipboard
golang
proposal: maps: new standard library package based on x/exp/maps
In #47649 @rsc proposed a new maps package in the standard library based on discussion in #47330. After we settled on an API we added the experimental package golang.org/x/exp/maps.
We now have experience with this package in practice. pkg.go.dev reports that it is imported by 615 other packages. I propose that it is now time to move this package into the standard library for the 1.21 release.
Doing this doesn't mean that we can't add more functions to the standard library maps package later. Any such additions should be suggested in their own separate proposal. (There are some existing proposals that would move from x/exp/maps to maps: at least #54012, #54454, #57191).
The specific API that we will put into the standard library is as follows.
// Keys returns the keys of the map m.
// The keys will be in an indeterminate order.
func Keys[M ~map[K]V, K comparable, V any](m M) []K
// Values returns the values of the map m.
// The values will be in an indeterminate order.
func Values[M ~map[K]V, K comparable, V any](m M) []V
// Equal reports whether two maps contain the same key/value pairs.
// Values are compared using ==.
func Equal[M1, M2 ~map[K]V, K, V comparable](m1 M1, m2 M2) bool
// EqualFunc is like Equal, but compares values using eq.
// Keys are still compared with ==.
func EqualFunc[M1 ~map[K]V1, M2 ~map[K]V2, K comparable, V1, V2 any](m1 M1, m2 M2, eq func(V1, V2) bool) bool
// Clone returns a copy of m. This is a shallow clone:
// the new keys and values are set using ordinary assignment.
func Clone[M ~map[K]V, K comparable, V any](m M) M
// Copy copies all key/value pairs in src adding them to dst.
// When a key in src is already present in dst,
// the value in dst will be overwritten by the value associated
// with the key in src.
func Copy[M1 ~map[K]V, M2 ~map[K]V, K comparable, V any](dst M1, src M2)
// DeleteFunc deletes any key/value pairs from m for which del returns true.
func DeleteFunc[M ~map[K]V, K comparable, V any](m M, del func(K, V) bool)
Thanks. I think you're right. I've edited the proposal to remove Clear.
I would love to see either a new type sortedMap, or the option to implement sorting/searching of maps by value on put/delete. This is a builtin type in a handful of other popular programming languages, and since I don't see many people being willing to implement red/black trees on their own, they will have to implement their own linked hash map with a sorted slice, which is generally less efficient in space complexity.
@iamemilio Seems out of scope for this proposal.
References:
- https://github.com/tidwall/btree
- https://github.com/google/btree
- https://youtu.be/4ELJDEjDpqk (Modern B-Tree techniques)
A concern I've had with EqualFunc before is it compares length first, so you can't use it if you want to consider m1 and m2 the same if any keys missing from one or the other have zero values. E.g., these two maps might be considered equivalent for some applications:
var m1 = map[string]int {
"a": 0,
"b": 0,
"c": 0,
}
var m2 = map[string]int {
"b": 0,
"c": 0,
"d": 0,
}
eq := true
for k := range m1 {
if m1[k] != m2[k] {
eq = false
}
}
for k := range m2 {
if m1[k] != m2[k] {
eq = false
}
}
fmt.Println(eq) // true
Maybe the solution is to add a looser but slower function with a name like Equivalent.
~I think EqualFunc could skip checking the length, instead of introducing another function that skips it.~
~If a developer is providing their own equal function then EqualFunc should make the least assumptions possible so that the function has utility in a wider range of custom situations.~
~It's not difficult for a developer to add their add their own length check before calling EqualFunc if they need the optimization.~
[Edit: I realize my comment doesn't make much sense. Since EqualFunc compares only existing values in each map.]
This proposal has been added to the active column of the proposals project and will now be reviewed at the weekly proposal review meetings. — rsc for the proposal review group
@carlmjohnson if you feel strongly about Equivalent being in the package that should be a separate proposal. It seems a little niche to me.
Given that we already reviewed this API before it went into x/exp, it is not surprising there's not much discussion here. The proposal is exactly x/exp/maps minus Clear.
Does anyone object to accepting this proposal?
Based on the discussion above, this proposal seems like a likely accept. — rsc for the proposal review group
I would like to bring up #56621 again, now that x/exp/maps is on its way to the standard library. I feel like there should at least be an example showing this behaviour.
Other than that, the API would be a welcome addition to the stdlib.
I don't think that anything has changed regarding #56621.
Of course examples are always welcome.
No change in consensus, so accepted. 🎉 This issue now tracks the work of implementing the proposal. — rsc for the proposal review group
Change https://go.dev/cl/498602 mentions this issue: doc/go1.21: mention maps package
