Step 6 of 7

dedup, retain, contains and binary_search

Real data is messy: duplicate entries, invalid readings, things you need to look up. Vectors have tools for each.

fn main() {
    let mut visitors = vec![42, 7, 42, 42, 13, 7];
    visitors.dedup();
    println!("{:?}", visitors);
    visitors.sort();
    visitors.dedup();
    println!("{:?}", visitors);

    let mut readings = vec![12, -1, 15, -1, 9];
    readings.retain(|&r| r >= 0);
    println!("{:?}", readings);

    println!("{}", visitors.contains(&13));
    println!("{:?} {:?}", visitors.binary_search(&13), visitors.binary_search(&10));
}

[42, 7, 42, 13, 7]
[7, 13, 42]
[12, 15, 9]
true
Ok(1) Err(1)

Piece by piece:

• dedup() removes consecutive repeats only: the two 42s next to each other became one, but the other repeats stayed. Sort first, so equal values sit next to each other, and then dedup removes every duplicate.
• retain(|&r| r >= 0) keeps only the elements for which the closure returns true, and removes the rest in one pass (correctly, unlike removing inside an index loop). retain hands the closure a reference to each element; the parameter pattern &r copies the number out, so the condition can say r >= 0.
• contains(&13) checks every element until it finds a match. It takes a reference, like most lookups.
• binary_search(&13) works only on a sorted vector. It halves the search range at each step, so it needs about 20 comparisons for a million elements, where contains might need a million. It returns Ok(index) if found, or Err(index) with the position where the value would go to keep the vector sorted, which is exactly what you need to insert it there.

Common mistakes

• dedup on unsorted data removes only adjacent repeats. If you need unique values in their original order, the next module's HashSet does that.
• binary_search on unsorted data doesn't fail, it just gives meaningless answers. Only use it on data you know is sorted.
• Forgetting the &. visitors.contains(13) is a mismatched types error: write contains(&13).

Your task

Write fn clean_log(lines: &mut Vec<String>) that removes every line containing "DEBUG" and then collapses consecutive identical lines into one (a service that retries prints the same line many times in a row).

Challenge 2

A sorted list of user ids must stay sorted and unique. Write fn insert_unique(sorted: &mut Vec<u32>, id: u32) -> bool with binary_search: if the id is already there return false and change nothing; otherwise insert it at the position binary_search reports and return true.

Challenge 3

Build a guest list. Read names, one per line. Trim spaces around each name, ignore blank lines, treat names case-insensitively (store them in lowercase), and print the unique names in alphabetical order, one per line, followed by N unique guests.

Previous: Sorting Next: A Vec of structs