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

proposal: Add a sorting function for map #39291

Closed
QiangHeisenberg opened this issue May 28, 2020 · 11 comments
Closed

proposal: Add a sorting function for map #39291

QiangHeisenberg opened this issue May 28, 2020 · 11 comments
Labels
Projects
Milestone

Comments

@QiangHeisenberg
Copy link
Contributor

@QiangHeisenberg QiangHeisenberg commented May 28, 2020

hello

Usually, I often need to sort the map conveniently, sorting by key or value. I don't know if this function can be added, or for what reason not to increase this function? If you want, I can add this function.

What version of Go are you using (go version)?

$ go version
go version go1.14.2 windows/amd64

Does this issue reproduce with the latest release?

yes

@gopherbot gopherbot added this to the Proposal milestone May 28, 2020
@gopherbot gopherbot added the Proposal label May 28, 2020
@davecheney
Copy link
Contributor

@davecheney davecheney commented May 28, 2020

Maps in go are not sorted, even if it was possible to sort a maps keys, it wouldn’t store them, and iteration order over a map is not defined.

@dsnet
Copy link
Member

@dsnet dsnet commented May 28, 2020

If Go had generics (#15292), one could imagine something like:

func SortedKeys(type K ordered, V)(m map[K]V) []K {
    keys := make([]K)
    for k := range m {
        keys = append(keys, k)
    }
    sort.Slice(keys, func(i, j int) bool {
        return keys[i] < keys[j]
    })
    return keys
}

Obviously, this will incur O(n*log(n)) runtime cost and O(n) memory given that we only have unordered maps to work with.

Barring generics, I don't think anything like this should be considered yet.

@robpike
Copy link
Contributor

@robpike robpike commented May 28, 2020

You can see something about how hard this problem is by looking at the implementation that the fmt package uses to provide a stable sorted output when printing a map.

@martisch
Copy link
Contributor

@martisch martisch commented May 28, 2020

The code for fmt stable sorting of a map for reference: https://github.com/golang/go/blob/master/src/internal/fmtsort/sort.go

@ianlancetaylor ianlancetaylor added this to Incoming in Proposals May 28, 2020
@ianlancetaylor
Copy link
Contributor

@ianlancetaylor ianlancetaylor commented May 28, 2020

I'm not sure what this proposal is asking for. Do you want a way to keep a map in sorted order? That would be a significant language change and is very unlikely to be accepted. Or do you want a way to take a map and return the elements sorted by key? That is easy to write for any specific map and easy to write if we have generics.

In order to evaluate this proposal, you need to suggest an API.

Thanks.

@QiangHeisenberg
Copy link
Contributor Author

@QiangHeisenberg QiangHeisenberg commented May 29, 2020

Maps in go are not sorted, even if it was possible to sort a maps keys, it wouldn’t store them, and iteration order over a map is not defined.

I'm sorry, but you seem to misunderstand what I mean.I'm not asking the map is already sorted.I want to add a function is used to sort the map.

@davecheney
Copy link
Contributor

@davecheney davecheney commented May 29, 2020

Thank you for explaining. Where are you going to store the output of sorting the map? If its another variable then this is already possible

https://play.golang.org/p/wHZ4LnEvhx_6

If you want the map to become sorted, that is the order of keys in the map is sorted, this is not possible.

@nikolaydubina
Copy link

@nikolaydubina nikolaydubina commented May 29, 2020

@QiangHeisenberg

You want to add sorted map? This goes against golang design. In fact, golang randomizes order of map on every run.

Taking into account that golang does not have this container for 10 years and just general philosophy of go is to keep core code minimal, I don't think this idea will get accepted.

You have better chances submitting proposal to this repo that contains enough stars and containers already.

@QiangHeisenberg
Copy link
Contributor Author

@QiangHeisenberg QiangHeisenberg commented May 30, 2020

@QiangHeisenberg

You want to add sorted map? This goes against golang design. In fact, golang randomizes order of map on every run.

Taking into account that golang does not have this container for 10 years and just general philosophy of go is to keep core code minimal, I don't think this idea will get accepted.

You have better chances submitting proposal to this repo that contains enough stars and containers already.

okay, Thanks for your explanation, I get it.

@QiangHeisenberg
Copy link
Contributor Author

@QiangHeisenberg QiangHeisenberg commented May 30, 2020

I'm not sure what this proposal is asking for. Do you want a way to keep a map in sorted order? That would be a significant language change and is very unlikely to be accepted. Or do you want a way to take a map and return the elements sorted by key? That is easy to write for any specific map and easy to write if we have generics.

In order to evaluate this proposal, you need to suggest an API.

Thanks.

It seems that this proposal will not be accepted, thank you for your reply.

@QiangHeisenberg
Copy link
Contributor Author

@QiangHeisenberg QiangHeisenberg commented May 30, 2020

Thank you for explaining. Where are you going to store the output of sorting the map? If its another variable then this is already possible

https://play.golang.org/p/wHZ4LnEvhx_6

If you want the map to become sorted, that is the order of keys in the map is sorted, this is not possible.

Oh well, I understand what you mean, thank you for your reply.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Proposals
Declined
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
8 participants
You can’t perform that action at this time.