Skip to content

Tracking issue for slice_partition_dedupΒ #54279

Open

Description

@Kerollmops

View all comments

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

Unresolved Questions

Activity

  1. added
    T-libs-api[DEPRECATED; DO NOT USE]
    C-tracking-issueCategory: An issue tracking the progress of sth. like the implementation of an RFC
    on Sep 17, 2018
  2. SimonSapin commented on Jan 9, 2020

    @SimonSapin
    Contributor

    This issue tracks:

    impl<T> [T] {
        pub fn partition_dedup(&mut self) -> (&mut [T], &mut [T])
        where
            T: PartialEq,
        {
            self.partition_dedup_by(|a, b| a == b)
        }
    
        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,
        {
            self.partition_dedup_by(|a, b| key(a) == key(b))
        }
    }

    The doc-comment of partition_dedup_by (the others are similar) is:

    Moves all but the first of consecutive elements to the end of the slice satisfying a given equality relation.

    Returns two slices. The first contains no consecutive repeated elements. The second contains all the duplicates in no specified order.

    The same_bucket function is passed references to two elements from the slice and must determine if the elements compare equal. The elements are passed in opposite order from their order in the slice, so if same_bucket(a, b) returns true, a is moved at the end of the slice.

    If the slice is sorted, the first returned slice contains no duplicates.

    Examples

    #![feature(slice_partition_dedup)]
    
    let mut slice = ["foo", "Foo", "BAZ", "Bar", "bar", "baz", "BAZ"];
    
    let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.eq_ignore_ascii_case(b));
    
    assert_eq!(dedup, ["foo", "BAZ", "Bar", "baz"]);
    assert_eq!(duplicates, ["bar", "Foo", "BAZ"]);

    From the implementation PR:

    The benefits of adding these methods is that it is now possible to:

    • deduplicate a slice without having to allocate and possibly clone elements on the heap, really useful for embedded stuff that can't allocate for example.
    • not loose duplicate elements, because, when using Vec::dedup, duplicates elements are dropped. These methods add more flexibillity to the user.
  3. SimonSapin commented on Jan 9, 2020

    @SimonSapin
    Contributor

    These methods feel very niche to me (given we already have the Vec::dedup family of methods), similar to some things we currently have in https://crates.io/crates/itertools rather then std::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?

  4. Lokathor commented on Jan 9, 2020

    @Lokathor
    Contributor

    Note that Vec::dedup is 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.

  5. LukasKalbertodt commented on Jan 9, 2020

    @LukasKalbertodt
    Contributor

    @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 dedup without 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.

  6. SimonSapin commented on Jan 9, 2020

    @SimonSapin
    Contributor

    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_mut on the original slice.

  7. Kerollmops commented on Jan 9, 2020

    @Kerollmops
    ContributorAuthor

    I thought that it would be great to also add the #[must_use] attribute to these functions.

  8. kennytm commented on Jan 9, 2020

    @kennytm
    Member

    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:

    1. 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.

          let (_, dupes) = working.partition_dedup();
          if !dupes.is_empty() {
              assert_eq!(dupes.len(), 1);
              return dupes.first().unwrap().to_string();
          }

      but I don't think it is a good example, as it's easier to just write

          if let Some(first_dupe) = working.windows(2).find(|(p, q)| p == q) {
              return first_dupe.to_string();
          }
    2. 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.

      let (dedup, _dup) = numbers.partition_dedup();
      println!("dedup {:?} dup {:?}",dedup, _dup );
      match _dup.len() {
           0 => println!("no pair"),
           1 => println!("one pair"),
           2 => println!("three of a kind or two pairs, do an other match"),
           3 => println!("four of a kind"),
           _ => println!("not handled"),
      }

      The actual implementation in https://github.com/sachaarbonel/poker.rs/blob/1f4ef45872307b1a3c40795ff5b125b6d82cd68f/src/hand/mod.rs uses two calls of partition_dedup to distinguish two-pair (AA22) vs triples (AAA) and four-of-a-kind (AAAA) vs full-house (AAA22).

      IMO partition_dedup is far from useful as a poker hand classifier since it can't handle flushes or straights.

    3. 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.

      loop {
          subangles.sort_unstable_by_key(|ad| ad.1);
          subangles.sort_by_key(|ad| ad.0);
          let (left, right) =
              subangles.partition_dedup_by(|&mut ad1, &mut ad2| float_equals(ad1.0, ad2.0));
          if seek < left.len() {
              let (angle, distance) = left[seek];
              let coord = angle_distance_to_coord(part1_coord, angle, distance);
              return (coord, coord.x * 100 + coord.y);
          } else {
              seek -= left.len();
              subangles = right;
          }
      }

    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 uses split_at_mut):

    fn partition_dedup(&mut self) -> (&mut Self, &mut Self) {
        let p = self.dedup_in_place().len();
        self.split_at_mut(p)
    }

    There is no reason to keep the second element from the return type.

  9. LukasKalbertodt commented on Jan 9, 2020

    @LukasKalbertodt
    Contributor

    @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::partition and as we seem to have established, almost no one is interested in the second bucket. What about dedup_in_place?

  10. Lokathor commented on Jan 9, 2020

    @Lokathor
    Contributor

    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.

  11. smmalis37 commented on Feb 8, 2020

    @smmalis37
    Contributor

    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_mut and be fine.

  12. dtolnay commented on Feb 8, 2020

    @dtolnay
    Member

    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.

  13. smmalis37 commented on Feb 8, 2020

    @smmalis37
    Contributor

    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.

  14. 23 remaining items

  15. safinaskar commented on Apr 6, 2023

    @safinaskar
    Contributor

    Let me say another way. In my code I often want to dedup vectors of structs, which have String fields. Most of the time I just need to verify that there is no duplicates (i. e. what I really need in most of cases is is_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_dedupped

  16. Stargateur commented on Apr 6, 2023

    @Stargateur
    Contributor

    @safinaskar

    #![feature(slice_partition_dedup)]
    fn main() {
        struct Foo {
            f: String,
        }
        let mut a: Vec<Foo> = vec![];
        a.partition_dedup_by(|a, b| a.f == b.f);
    }
  17. safinaskar commented on Apr 6, 2023

    @safinaskar
    Contributor

    @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

  18. Jules-Bertholet commented on Sep 26, 2023

    @Jules-Bertholet
    Contributor

    The issue with the by_key functions is tracked in #34162.

  19. c410-f3r commented on Jan 1, 2024

    @c410-f3r
    Contributor

    What is the status of this feature?

  20. robertbastian commented on Feb 26, 2025

    @robertbastian
    Contributor

    Just adding one more use case: we have a Vec that is made up of two sorted sequences, and we need to dedupe the tail sequence. Vec::dedupe does not work for this, but the slice dedupe, followed by a truncate does.

    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 usize of 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 using self.split_at_mut instead of self.split_at_mut_unchecked.

  21. added
    T-libsRelevant to the library team, which will review and decide on the PR/issue.
    and removed
    T-libs-api[DEPRECATED; DO NOT USE]
    on Aug 12, 2026
  22. Demindiro commented on Sep 4, 2026

    @Demindiro
    Contributor

    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::dedup but 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.

  23. changed the title [-]Tracking issue for `slice::partition_dedup/by/by_key`[/-] [+]Tracking issue for `slice_partition_dedup`[/+] on Sep 4, 2026
  24. tgross35 commented on Sep 4, 2026

    @tgross35
    Member

    Some assorted thoughts:

    1. This isn't as needed as dedup on Vec, but is useful enough for providing no_std code with a way to deduplicate things.
    2. It would be fine to just return a usize for consistency with partition_point, which the user can slice or split_at as needed. (We should assert_unchecked!(res <= len) to make sure future bounds checks are elided, unless the optimizer infers this already)
    3. Perhaps a better name is partition_duplicates rather than partition_dedup? Since it doesn't actually deduplicate anything in the way a Vec does, the duplicates are just pushed to the end.
  25. added
    E-easyCall for participation: Easy difficulty. Experience needed to fix: Not much. Good first issue.
    and removed
    Libs-SmallLibs issues that are considered "small" or self-contained
    on Oct 7, 2026
  26. removed
    I-libs-radarLibs issues that are tracked on the team's radar.
    on Oct 22, 2026
  27. jalil-salame commented on Nov 17, 2026

    @jalil-salame
    Contributor

    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:

    use std::collections::BTreeSet;
    const ALLOWED_FUNCTIONS [&str; 4] = ["c_foo", "c_bar", "c_baz", "c_bar];
    
    // *Set::from
    let allowed = BTreeSet::from(ALLOWED_FUNCTIONS); // looses duplicates
    
    // *Set::from with custom fold (Copy types only)
    let mut dupes = Vec::new();
    let allowed = ALLOWED_FUNCTIONS
        .into_iter()
        .fold(BTreeSet::new(), |mut set, func| {
            if !set.insert(func) { dupes.push(func); }
            set
        });
    
    // Custom Type (same as fold but with a more verbose implementation)
    #[derive(Default)]
    struct WithDupes<T> { deduped: BTreeSet<T>, dupes: Vec<T> }
    impl<T: Ord + Copy> std::iter::FromIterator<T> for WithDupes<T> {
        fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
            iter.into_iter()
                .fold(Self::default(), |mut set, func| {
                    if !set.deduped.insert(func) { set.dupes.push(func); }
                    set
                })
        }
    }
    
    let WithDupes { deduped, dupes } = ALLOWED_FUNCTIONS.into_iter().collect()
    
    // With this feature
    let mut list = ALLOWED_FUNCTIONS;
    list.sort_unstable();
    let (allowed, dupes) = list.partition_dedup();

    This came up with bindgen allowlists hence the name of the variables

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    A-slice-vecArea: `[T]` and `Vec<T>`B-unstableBlocker: Implemented in the nightly compiler and unstable.C-tracking-issueCategory: 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.T-libsRelevant to the library team, which will review and decide on the PR/issue.

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions