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: container/list: add Sort() method #47989

Open
gobwas opened this issue Aug 26, 2021 · 5 comments
Open

proposal: container/list: add Sort() method #47989

gobwas opened this issue Aug 26, 2021 · 5 comments

Comments

@gobwas
Copy link

@gobwas gobwas commented Aug 26, 2021

The current List implementation doesn't support sorting. However, it may be needed to have both sorting possibility and constant-time insertion and deletion for some cases. This proposal suggests adding container/list.List.Sort() method to get such.

Mergesort can be used for initial implementation since it's a classical algorithm to sort linked lists. It does stable sort in constant space and O(n*log(n)) time complexity.

This PR can be used as a reference.

@gopherbot gopherbot added this to the Proposal milestone Aug 26, 2021
@DeedleFake
Copy link

@DeedleFake DeedleFake commented Aug 27, 2021

I don't have a particular problem with this, but might it make more sense to create a new linked list type (list.ListOf? list.Of?) with generics support and focus development on that one? If this proposal is accepted, it'll get added in Go 1.18 at the same time as generics anyways by the current plan.

Loading

@ianlancetaylor ianlancetaylor added this to Incoming in Proposals Sep 8, 2021
@sfllaw
Copy link
Contributor

@sfllaw sfllaw commented Sep 29, 2021

This API should mirror the work done for slices: #47619.

Loading

@carlmjohnson
Copy link
Contributor

@carlmjohnson carlmjohnson commented Sep 29, 2021

  1. Linked lists are bad and should not be used outside of teaching. Deques are good and should be used in nearly every case. IMO, container/list should either be deprecated or it should get a new generic Deque implementation and the documentation should tell users to use that instead of the current List type. Currently, list.List has no Swap(i, j) method because looking up i and j is an O(n) operation. With a deque, it becomes O(1), so you could add Swap and use generic comparables for Less(i, j), but…

  2. If you're sorting your list, you probably actually want a priority queue, which is implemented by container/heap currently. That package should probably be updated for generics by adding some new generic implementation and deprecating the current interface implementation.

Loading

@rsc
Copy link
Contributor

@rsc rsc commented Oct 27, 2021

On hold for generics.

Loading

@rsc
Copy link
Contributor

@rsc rsc commented Oct 27, 2021

Placed on hold.
— rsc for the proposal review group

Loading

@rsc rsc moved this from Incoming to Hold in Proposals Oct 27, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
6 participants