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

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

Closed
ianlancetaylor opened this issue Dec 22, 2022 · 16 comments
Closed

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

ianlancetaylor opened this issue Dec 22, 2022 · 16 comments
Labels
generics Issue is related to generics Proposal Proposal-Accepted
Milestone

Comments

@ianlancetaylor
Copy link
Contributor

ianlancetaylor commented Dec 22, 2022

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

Isn’t Clear obsoleted by the new clear builtin?

@ianlancetaylor
Copy link
Contributor Author

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

@iamemilio
Copy link

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

@iamemilio Seems out of scope for this proposal.

References:

@earthboundkid
Copy link
Contributor

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.

@leighmcculloch

This comment was marked as resolved.

@rsc
Copy link
Contributor

rsc commented Jan 4, 2023

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

rsc commented Jan 11, 2023

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

rsc commented Jan 18, 2023

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

rsc commented Jan 25, 2023

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

@ainar-g
Copy link
Contributor

ainar-g commented Jan 25, 2023

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

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

Of course examples are always welcome.

@rsc
Copy link
Contributor

rsc commented Feb 1, 2023

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

@rsc rsc changed the title proposal: maps: new standard library package based on x/exp/maps maps: new standard library package based on x/exp/maps Feb 1, 2023
@rsc rsc modified the milestones: Proposal, Backlog Feb 1, 2023
@gopherbot
Copy link

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

johanbrandhorst pushed a commit to Pryz/go that referenced this issue Feb 12, 2023
This copies x/exp/maps into the standard library (except for the Clear
function which is now available as the clear builtin.)

Fixes golang#57436

Change-Id: I30dd470c2f7ae34c7c82b4c1025a7582d61fabaa
Reviewed-on: https://go-review.googlesource.com/c/go/+/464343
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Reviewed-by: Eli Bendersky <eliben@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
@gopherbot
Copy link

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

@dmitshur dmitshur removed this from the Backlog milestone May 30, 2023
@dmitshur dmitshur added this to the Go1.21 milestone May 30, 2023
gopherbot pushed a commit that referenced this issue May 30, 2023
For #57436

Change-Id: I99e8b0819c76f1ccf12154a894c9c4c9d68124d4
Reviewed-on: https://go-review.googlesource.com/c/go/+/498602
Reviewed-by: Eli Bendersky <eliben@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Auto-Submit: Ian Lance Taylor <iant@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Nasfame pushed a commit to golangFame/go that referenced this issue Jun 4, 2023
For golang#57436

Change-Id: I99e8b0819c76f1ccf12154a894c9c4c9d68124d4
Reviewed-on: https://go-review.googlesource.com/c/go/+/498602
Reviewed-by: Eli Bendersky <eliben@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Auto-Submit: Ian Lance Taylor <iant@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
@jdemeyer
Copy link

Keys and Values were removed: #61538

eric pushed a commit to fancybits/go that referenced this issue Sep 7, 2023
This copies x/exp/maps into the standard library (except for the Clear
function which is now available as the clear builtin.)

Fixes golang#57436

Change-Id: I30dd470c2f7ae34c7c82b4c1025a7582d61fabaa
Reviewed-on: https://go-review.googlesource.com/c/go/+/464343
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Reviewed-by: Eli Bendersky <eliben@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
eric pushed a commit to fancybits/go that referenced this issue Sep 7, 2023
This copies x/exp/maps into the standard library (except for the Clear
function which is now available as the clear builtin.)

Fixes golang#57436

Change-Id: I30dd470c2f7ae34c7c82b4c1025a7582d61fabaa
Reviewed-on: https://go-review.googlesource.com/c/go/+/464343
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Michael Knyszek <mknyszek@google.com>
Reviewed-by: Eli Bendersky <eliben@google.com>
Run-TryBot: Ian Lance Taylor <iant@google.com>
Auto-Submit: Ian Lance Taylor <iant@google.com>
Run-TryBot: Ian Lance Taylor <iant@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
generics Issue is related to generics Proposal Proposal-Accepted
Projects
None yet
Development

No branches or pull requests