Collect sorted keys and build a last-value index

Turn key-value pairs into an index and a sorted list of its keys.

pub fn index_and_dedup(pairs: Vec<(String, i64)>) -> (Vec<String>, BTreeMap<String, i64>)

Return each distinct key exactly once in the vector, sorted by Rust's string ordering. The map must contain the last value associated with each key in the input. For [("a", 1), ("b", 2), ("a", 9)], return keys ["a", "b"] and a map containing a: 9 and b: 2.

Empty input produces an empty vector and map. Empty strings and Unicode keys are valid, as is every i64 value. Keys are compared exactly, without trimming, case folding or Unicode normalization. String ordering is lexicographic by UTF-8 bytes, not locale-aware dictionary order.

Decide the duplicate policy explicitly

BTreeMap::insert replaces the value for an existing equal key and returns the previous value. Inserting pairs in input order therefore implements the requested last-value policy. In contrast, entry(key).or_insert(value) keeps an existing value, which gives a first-value policy in this loop:

use std::collections::BTreeMap;

fn main() {
    let pairs = [("a", 1), ("a", 9)];
    let mut last = BTreeMap::new();
    let mut first = BTreeMap::new();
    for (key, value) in pairs {
        last.insert(key, value);
        first.entry(key).or_insert(value);
    }
    assert_eq!(last.get("a"), Some(&9));
    assert_eq!(first.get("a"), Some(&1));
}

Maps also implement FromIterator, so collecting pairs is convenient when keys are distinct. However, the documented FromIterator contracts for BTreeMap and HashMap do not specify which value survives equal keys. Use explicit insertion order when a particular survivor is part of your API.

Collect the keys from the finished map

A BTreeMap visits keys in sorted order and stores each distinct key once. Its keys() method yields borrowed &String values. To return a separate Vec<String> while retaining the map, clone those strings with map.keys().cloned().collect().

The starter instead collects references directly into an owned vector, causing E0277. Adding .cloned() repairs that type mismatch, but its original input iterator still contains duplicates and is not necessarily sorted. The starter's or_insert also keeps the wrong value for repeated keys.

Cloning here creates independently owned key strings for the second output. It costs work proportional to the copied contents, along with collection storage; it is not a fixed allocation count for every possible key.

A HashSet also removes duplicates, but iteration order is arbitrary. It may appear consistent in a particular run without being sorted or guaranteed across runs. Use a BTreeSet, sort the resulting vector, or take the already ordered keys from the map you need to return.

Other useful collect targets

collect builds a type implementing FromIterator for the iterator's item type. The destination determines how those items are combined:

use std::collections::{BTreeSet, VecDeque};

fn main() {
    let numbers = [3, 1, 3, 2];
    let queue: VecDeque<_> = numbers.into_iter().collect();
    let unique: BTreeSet<_> = numbers.into_iter().collect();
    let text: String = ['r', 'u', 's', 't'].into_iter().collect();
    assert_eq!(queue.into_iter().collect::<Vec<_>>(), [3, 1, 3, 2]);
    assert_eq!(unique.into_iter().collect::<Vec<_>>(), [1, 2, 3]);
    assert_eq!(text, "rust");
}

You can also collect into Result or Option. These stop at the first Err or None, respectively, rather than collecting every success and failure:

fn main() {
    let parsed: Result<Vec<i32>, _> = ["1", "bad", "3"]
        .into_iter().map(str::parse).collect();
    assert!(parsed.is_err());
    let missing: Option<Vec<i32>> = [Some(1), None, Some(3)].into_iter().collect();
    assert_eq!(missing, None);
    let complete: Option<Vec<i32>> = [Some(1), Some(2)].into_iter().collect();
    assert_eq!(complete, Some(vec![1, 2]));
}

If inference cannot select a destination, add a binding annotation or write the type explicitly, such as collect::<Vec<_>>().

Standard map collection does not return a separate duplicate report. When you need one, inspect the values returned by insert, or design a custom collector that stores the report alongside the map. FromIterator does not require every destination to discard the same information.