Skip to content

Vec::dedup

Vec methods · Collections

Level: reference · for working programmers

One line: Collapse runs of consecutive equal elements to one.

pub fn dedup(&mut self)

Stable since 1.0.0.

Consecutive is the whole trap. [1, 2, 2, 3, 3, 3, 1] dedups to [1, 2, 3, 1] — the trailing 1 survives, because it is not next to the first one. dedup is a run-length pass, not a set operation.

Two ways to remove every duplicate:

  • Sort first. v.sort(); v.dedup(); — O(n log n), and the result is sorted.
  • Keep the original order with a set in a retain closure: let mut seen = HashSet::new(); v.retain(|x| seen.insert(*x));

The element kept from each run is the first one, which matters as soon as T's equality ignores some of its fields.

T: PartialEq. For a custom notion of sameness use dedup_by; to compare on one derived value use dedup_by_key. dedup() is exactly dedup_by(|a, b| a == b).

Empty and single-element vectors are no-ops. Capacity is untouched.

Example

vec_dedup.rs in full — pasted here by tools/run_examples.py from the file CI compiles and runs.

fn main() {
    // CONSECUTIVE duplicates only. This is the whole trap.
    let mut v = vec![1, 2, 2, 3, 3, 3, 1];
    v.dedup();
    println!("{v:?}");        // the trailing 1 survives: it is not next to the first

    // To remove every duplicate, sort first — then equal values are adjacent.
    let mut v = vec![3, 1, 3, 2, 1, 3];
    v.sort();
    v.dedup();
    println!("sorted then deduped: {v:?}");

    // Or keep the original order with a set, which dedup cannot do.
    let mut seen = std::collections::HashSet::new();
    let mut v = vec![3, 1, 3, 2, 1, 3];
    v.retain(|n| seen.insert(*n));
    println!("first occurrence, original order: {v:?}");

    // It is O(n) and in place, which is why it is worth the "consecutive"
    // restriction: a run-length pass over already-grouped data.
    let mut log = vec!["open", "open", "read", "read", "read", "close"];
    log.dedup();
    println!("collapsed run: {log:?}");

    // The kept element of each run is the FIRST one.
    #[derive(Debug, PartialEq)]
    struct Entry { key: u8, note: &'static str }
    impl Entry { fn new(key: u8, note: &'static str) -> Self { Entry { key, note } } }
    let mut v = vec![Entry::new(1, "first"), Entry::new(1, "second")];
    // PartialEq here compares both fields, so nothing is equal and nothing goes.
    v.dedup();
    println!("full-struct equality keeps both: {}", v.len());
    println!("  keys {:?}", v.iter().map(|e| (e.key, e.note)).collect::<Vec<_>>());

    // Comparing on one field is what dedup_by_key is for.
    let mut v = vec![Entry::new(1, "first"), Entry::new(1, "second")];
    v.dedup_by_key(|e| e.key);
    println!("dedup_by_key keeps the first: {:?}", v[0]);

    // Empty and single-element vectors are no-ops.
    let mut e: Vec<u8> = vec![];
    e.dedup();
    let mut one = vec![7];
    one.dedup();
    println!("{e:?} {one:?}");
}

Verified output of vec_dedup.rs — regenerated by tools/run_examples.py, never hand-typed.

[1, 2, 3, 1]
sorted then deduped: [1, 2, 3]
first occurrence, original order: [3, 1, 2]
collapsed run: ["open", "read", "close"]
full-struct equality keeps both: 2
  keys [(1, "first"), (1, "second")]
dedup_by_key keeps the first: Entry { key: 1, note: "first" }
[] [7]

See also

Vec::dedup in the standard library ↗