How do I sort a map by order of insertion?

Question

I have tried using HashMap and BTreeMap for this but neither have worked:

use std::collections::{BTreeMap, HashMap};

fn main() {
    let mut btreemap = BTreeMap::new();
    println!("BTreeMap");
    btreemap.insert("Z", "1");
    btreemap.insert("T", "2");
    btreemap.insert("R", "3");
    btreemap.insert("P", "4");
    btreemap.insert("K", "5");
    btreemap.insert("W", "6");
    btreemap.insert("G", "7");
    btreemap.insert("C", "8");
    btreemap.insert("A", "9");
    btreemap.insert("D", "0");
    for (key, value) in btreemap {
        println!("{} {}", key, value);
    }
    println!("Hash Map");
    let mut hashmap = HashMap::new();
    hashmap.insert("Z", "1");
    hashmap.insert("T", "2");
    hashmap.insert("R", "3");
    hashmap.insert("P", "4");
    hashmap.insert("K", "5");
    hashmap.insert("W", "6");
    hashmap.insert("G", "7");
    hashmap.insert("C", "8");
    hashmap.insert("A", "9");
    hashmap.insert("D", "0");
    for (key, value) in hashmap {
        println!("{} {}", key, value);
    }
}

When I run this via the Rust playground, I get a result that is not sorted by order of insertion; BTreeMap appears to be ordered alphabetically (prints A C D G K P R T W Z, along with the numbers) and HashMap seems to be ordered randomly (prints Z A C D R P T G WK ).

I've looked through the Rust standard library documentation and I don't see any other maps.

Answer 1

Associative containers (containers that map a key to a value) usually use one of two strategies to be able to look-up a key efficiently:

• either they sort the keys according to some comparison operation
• or they hash the keys according to some hashing operation

Here, you have the two archetypes: BTree sorts the key and HashMap hashes them.

---

If you solely wish to track the order of insertion, then an associative container is the wrong choice of container, what you wish for is a sequence container such as std::vec::Vec: always push the items at the end, and you can iterate over them in the order they were inserted.

Note: I advice writing a wrapper to prevent unwanted insertions anywhere else.

---

If, on the other hand, you want to have an associative container which also tracks insertion order, then what you are asking for does not exist yet in Rust as far as I know.

In C++, the go-to solution is called Boost.MultiIndex which allows you to create a container which you can query in multiple different ways; it is a quite complex piece of software, as you can see yourself if you browse its source. It might come to Rust, in time, but if you need something now you will have to hand-roll your own solution I fear; you can use the Boost code as a lean-to, although from experience it can be hard to read/understand.

Answer 2

The default collections do not track order of insertion. If you wish to sort by that, you will need to either find a different collection that does track it, or track it yourself.