Suppose you have a HashMap<String, usize> where you know by construction that the values are unique integers in the range 0..n where n is the number of entries in the map. What is the most efficient way to invert this mapping, producing Box<[String]> where index i in the slice is the string that was mapped to value i by the original HashMap? You may consume the HashMap. What I have now is

fn invert_string_index(
    mut m: HashMap<String, usize>
) -> Box<[String]> {
    let mut v = m.drain().map(|(k, v)| (v, k)).collect::<Vec<_>>();
    v.sort_unstable();  // unstable sort is OK because indices are unique
    v.into_iter().map(|(_, s)| s).collect::<Vec<_>>().into_boxed_slice()
}

but this involves an intermediate vector that it feels like it ought to be possible to eliminate. The only alternative I can think of is to keep the original map around and use sort_unstable_by_key but I suspect that would actually be slower.

4 posts - 4 participants

Read full topic