Repository navigation
Open
Labels
A-slice-vecArea: `[T]` and `Vec<T>`Area: `[T]` and `Vec<T>`B-unstableBlocker: Implemented in the nightly compiler and unstable.Blocker: Implemented in the nightly compiler and unstable.C-tracking-issueCategory: An issue tracking the progress of sth. like the implementation of an RFCCategory: An issue tracking the progress of sth. like the implementation of an RFCE-easyCall for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.Call for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.T-libsRelevant to the library team, which will review and decide on the PR/issue.Relevant to the library team, which will review and decide on the PR/issue.
Description
Tracking issue for slice_partition_dedup
Add three methods to the slice type, the partition_dedup, partition_dedup_by and partition_dedup_by_key. The two other methods are based on slice::partition_dedup_by.
API summary
impl<T> [T] {
pub fn partition_dedup(&mut self) -> (&mut [T], &mut [T])
where
T: PartialEq;
pub fn partition_dedup_by<F>(&mut self, mut same_bucket: F) -> (&mut [T], &mut [T])
where
F: FnMut(&mut T, &mut T) -> bool;
pub fn partition_dedup_by_key<K, F>(&mut self, mut key: F) -> (&mut [T], &mut [T])
where
F: FnMut(&mut T) -> K,
K: PartialEq;
}Steps / History
- Implement the feature as a PR (Introduce the partition_dedup/by/by_key methods for slicesΒ #54058)
- Stabilization PR (see instructions on forge)
Unresolved Questions
- Should the methods only return one slice instead of a tuple with two slices? Or only a
usizeto matchpartition_point?(comment) - Annotate it with
#[must_use]? - slice::sort_by_key has more restrictions than slice::sort_byΒ #34162
Reacted by phimuemue, $nyx and Eugene
Reacted by Stanislav Tkach, Jonatan Hatakeyama Zeidler, Martin Junghanns, SDesya74 and Tobias Hillemanns
Metadata
Metadata
Assignees
Labels
A-slice-vecArea: `[T]` and `Vec<T>`Area: `[T]` and `Vec<T>`B-unstableBlocker: Implemented in the nightly compiler and unstable.Blocker: Implemented in the nightly compiler and unstable.C-tracking-issueCategory: An issue tracking the progress of sth. like the implementation of an RFCCategory: An issue tracking the progress of sth. like the implementation of an RFCE-easyCall for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.Call for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.T-libsRelevant to the library team, which will review and decide on the PR/issue.Relevant to the library team, which will review and decide on the PR/issue.
Activity
SimonSapin commentedon Jan 9, 2020
This issue tracks:
The doc-comment of
partition_dedup_by(the others are similar) is:From the implementation PR:
SimonSapin commentedon Jan 9, 2020
These methods feel very niche to me (given we already have the
Vec::dedupfamily of methods), similar to some things we currently have in https://crates.io/crates/itertools rather thenstd::iter. Still, multiple people were involved in the implementation PR and were evidently happy enough to land it. So Iβd be inclined to propose FCPΒ to stabilize.@rust-lang/libs, any thoughts?
Lokathor commentedon Jan 9, 2020
Note that
Vec::dedupis actually implemented in terms of these methods, so it's very important to anyone trying to implement vec-like replacements that these become available on stable.LukasKalbertodt commentedon Jan 9, 2020
@leonardo-m brought up the question of whether the second element of the returned tuple is even used. If not, it would simplify the API to return only one slice instead of a tuple. So it would be really useful to know how people use this feature. If it's merely used as a way to
dedupwithout allocation, then yes, the first slice is sufficient. All usages I was able to find via a quick GH search indeed only used the first returned slice.But as I agree this is pretty niche, I think it's fine if the API is a bit more complicated. Niche APIs have a stronger focus on being powerful than being easy to use, I think.
My initial thought also was that this API is too niche and shouldn't be included, but apparently it is used a lot (even excluding Rust forks, there are quite a few projects using it on the first few pages of the search results). So I'd be fine with stabilizing this as soon as the return type question is resolved.
SimonSapin commentedon Jan 9, 2020
As far as I can tell if the method returns one slice the other behavior can still be achieved by only keeping the length of that returned slice and then using
split_at_muton the original slice.Kerollmops commentedon Jan 9, 2020
I thought that it would be great to also add the
#[must_use]attribute to these functions.kennytm commentedon Jan 9, 2020
The link above gives ~1500 results. Excluding the word "slice_internals" and "fmt_internals" and forcing the language to be Rust leaves only 12 results. So 99% of this "lot" are very likely just rustc clones.
A more accurate search would be:
https://github.com/search?l=Rust&q=partition_dedup+NOT+slice_internals+NOT+fmt_internals+NOT+test_binary_search_implementation_details&type=Code (12 results)
https://github.com/search?l=Rust&q=partition_dedup_by+NOT+slice_internals+NOT+fmt_internals+NOT+test_binary_search_implementation_details+NOT+vec_intoiter_debug&type=Code (10 results)
https://github.com/search?l=Rust&q=partition_dedup_by_key+NOT+slice_internals+NOT+fmt_internals+NOT+vec_intoiter_debug&type=Code (1 result)
Only 3 examples actually try to use the second element:
https://github.com/treuherz/AdventOfCode/blob/152da4d32c4d6a258ec669f2fc175db99a4e1df8/18/rs/src/bin/2.rs#L66-L84 uses the second part of
partition_dedup()to locate the first duplicated element.but I don't think it is a good example, as it's easier to just write
https://github.com/sachaarbonel/poker.rs/blob/1f4ef45872307b1a3c40795ff5b125b6d82cd68f/src/bin.rs uses the second part to determine if the poker hand has pairs/triples/4 of a kind. But the message already shows how unreliable it is for the purpose.
The actual implementation in https://github.com/sachaarbonel/poker.rs/blob/1f4ef45872307b1a3c40795ff5b125b6d82cd68f/src/hand/mod.rs uses two calls of
partition_dedupto distinguish two-pair (AA22) vs triples (AAA) and four-of-a-kind (AAAA) vs full-house (AAA22).IMO
partition_dedupis far from useful as a poker hand classifier since it can't handle flushes or straights.https://github.com/smmalis37/aoc2019/blob/c1015c7d2bba8075176650ac84f4f3c53b63e1d3/src/days/day10.rs#L86-L101 Probably the only legit use case though I can't quite figure out what it's trying to do.
Conclusion: The second element is extremely niche, and encourages bad algorithm. As mentioned in #54279 (comment), the original slice is not destroyed, so the two-element version can be easily reimplemented by the one-element version using
split_at_mut(heck, the current implementation also usessplit_at_mut):There is no reason to keep the second element from the return type.
LukasKalbertodt commentedon Jan 9, 2020
@kennytm Wow, thanks for the research! I clearly didn't put enough time into my comment and was indeed fooled by my search.
In case we change the return type to only return the first part of the slice, maybe we should also think about renaming the methods. Shepmaster suggested the current name partially because of the 2-tuple return type. I don't mind the current name (the algorithm still does some kind of partitioning), but another name might be more appropriate: the return type is different than
Iterator::partitionand as we seem to have established, almost no one is interested in the second bucket. What aboutdedup_in_place?Lokathor commentedon Jan 9, 2020
Note: The side effect of this method is that the input slice is swapped all around on success so that the initial span of the spice is the deduped portion. Thus, must_use would be inappropriate.
smmalis37 commentedon Feb 8, 2020
Oh hey I've been mentioned. Yeah that use case is very much artificial, it was part of the Advent of Code, a series of puzzles. The puzzle for day 10 can be found at https://adventofcode.com/2019/day/10, although you'd need to solve part 1 before it reveals part 2 which this was part of. However as you said i could easily just use
split_at_mutand be fine.dtolnay commentedon Feb 8, 2020
I would be inclined to remove these methods. This is an uncommon use case. The algorithm can be implemented in ~20 lines of safe code if you don't mind the bounds checks. I think the amount of benefit we'd deliver by stabilizing these is much less than what it costs to put these fairly complicated names and signatures in front of everyone in the documentation of slices.
smmalis37 commentedon Feb 8, 2020
I'd vote against removing these methods. Even if their use is uncommon they are genuinely useful. They also fit with other
dedup*methods that are already in std.23 remaining items
safinaskar commentedon Apr 6, 2023
Let me say another way. In my code I often want to dedup vectors of structs, which have
Stringfields. Most of the time I just need to verify that there is no duplicates (i. e. what I really need in most of cases isis_dedupped).Unfortunately the only way I can do this is to
clone()this strings. This is slow. See here:https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=7d753d1967e7413d1fa38d3727acab85
So I want some API that works in this case without cloning. Or at least which give ability to verify
is_deduppedStargateur commentedon Apr 6, 2023
@safinaskar
safinaskar commentedon Apr 6, 2023
@Stargateur , I don't like this solution. I'm big fan of "don't repeat yourself" principle. But, yes, this will go as pragmatic solution
Jules-Bertholet commentedon Sep 26, 2023
The issue with the
by_keyfunctions is tracked in #34162.c410-f3r commentedon Jan 1, 2024
What is the status of this feature?
robertbastian commentedon Feb 26, 2025
Just adding one more use case: we have a
Vecthat is made up of two sorted sequences, and we need to dedupe the tail sequence.Vec::dedupedoes not work for this, but the slice dedupe, followed by atruncatedoes.The author of this code was actually assuming that deduping would be quadratic (because repeated removes are). This to me disproves the statement made above that "the algorithm can be implemented in ~20 lines of safe code if you don't mind the bounds checks". It can, if you realise how to do it, but so can most of the methods on slice. Having an efficient, correct implementation of this seems appropriate for the standard library.
Regarding the return type, it could also be a
usizeof the deduped length. But going from length to slice requires a bounds check, whereas going from slice to length doesn't. However, the current implementation might include this bounds check anyway, as it's usingself.split_at_mutinstead ofself.split_at_mut_unchecked.Demindiro commentedon Sep 4, 2026
It is "only" 20(1) lines of code but I'd rather type 0 lines especially when the necessary functionality is already present in stdlib.
I could perhaps use
Vec::dedupbut I'd rather not as I want to use the code that needs dedup with e.g.memmap2::MmapMut.(1) I did it in 16 lines... and an additional 9 for a small test. Because mistakes can and do happen.
[-]Tracking issue for `slice::partition_dedup/by/by_key`[/-][+]Tracking issue for `slice_partition_dedup`[/+]tgross35 commentedon Sep 4, 2026
Some assorted thoughts:
deduponVec, but is useful enough for providingno_stdcode with a way to deduplicate things.usizefor consistency withpartition_point, which the user can slice orsplit_atas needed. (We shouldassert_unchecked!(res <= len)to make sure future bounds checks are elided, unless the optimizer infers this already)partition_duplicatesrather thanpartition_dedup? Since it doesn't actually deduplicate anything in the way aVecdoes, the duplicates are just pushed to the end.jalil-salame commentedon Nov 17, 2026
I came across this function while looking for an easy way to collect into a
Set<T>and warn about duplicates since the other options aren't great:This came up with
bindgenallowlists hence the name of the variables