maps: new standard library package based on x/exp/maps

[ianlancetaylor]

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)

[hherman1]

Isn’t Clear obsoleted by the new clear builtin?

[ianlancetaylor]

Thanks. I think you're right. I've edited the proposal to remove Clear.

[iamemilio]

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.

[mooijtech]

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

[earthboundkid]

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.

[rsc]

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

[rsc]

@carlmjohnson if you feel strongly about Equivalent being in the package that should be a separate proposal. It seems a little niche to me.

[rsc]

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?

[rsc]

Based on the discussion above, this proposal seems like a likely accept.
— rsc for the proposal review group

[ainar-g]

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.

[ianlancetaylor]

I don't think that anything has changed regarding #56621.

Of course examples are always welcome.

[rsc]

No change in consensus, so accepted. 🎉
This issue now tracks the work of implementing the proposal.
— rsc for the proposal review group

[gopherbot]

Change https://go.dev/cl/464343 mentions this issue: maps: new package

[gopherbot]

Change https://go.dev/cl/498602 mentions this issue: doc/go1.21: mention maps package

[jdemeyer]

Keys and Values were removed: #61538