util/slicesx: add Deduplicate/DeduplicateFunc #8168
Conversation
|
|
||
| // Deduplicate returns a copy of the provided slice with duplicate elements | ||
| // removed, compared as if using the == operator. | ||
| func Deduplicate[S ~[]T, T comparable](s S) S { |
There was a problem hiding this comment.
The fact that this always allocates O(2*n) is somewhat unfortunate.
I'm not sure how you plan on using this, but anytime I needed to deduplicate elements, I also needed it to be ordered. If ordering is something that is commonly wanted as well, then perhaps an alternative API would be:
func SortDedup[E cmp.Ordered](x []E) int
func SortDedepFunc[E any](x []E, cmp func(E, E) int) int
where it returns the number of remaining elements.
(Alternatively, it could just return the truncated []E).
This of course uses golang/go#60091.
There was a problem hiding this comment.
Switched to an append-style API that reuses the input slice, so we only allocate O(n) for the seen map. These functions are for cases where we specifically don't want to sort; we already have util/uniq which provides functions to deduplicate consecutive elements in a sorted list.
I don't see this being used in particularly allocation-sensitive code, but if we do that, one option would be to allow the user to provide a map to be used to track duplicates so the backing storage can be preallocated and/or shared between invocations of the deduplicate functions.
These functions allow deduplicating elements in a slice, either via direct comparison or via a function that returns a key to be used for comparison. Signed-off-by: Andrew Dunham <andrew@du.nham.ca> Change-Id: Ie6a20acf0431247487ac5ead110d56580dacfee4
7ef7633 to
98b15d4
Compare
These functions allow deduplicating elements in a slic 8000 e, either via direct comparison or via a function that returns a key to be used for comparison.
Change-Id: Ie6a20acf0431247487ac5ead110d56580dacfee4