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.

`HashMap`s are inherently unordered collections, and `BTree`s are inherently ordered by their keys. It doesn't actually make sense to talk about ordering either type by insertion order. — Jason Watkins, May 14 '15 at 17:20
@JasonWatkins There are variants of `HashMap` that natively retain insertion order as a consequence of their design. For example, Python 3.6 made hash tables more compact by splitting the table into a dense array of entries and a sparse array of indices. This saves space, speeds up iteration, and [maintains insertion order](http://stackoverflow.com/questions/39980323/dictionaries-are-ordered-in-cpython-3-6), although the latter is still considered an implementation detail. — user4815162342, Mar 25 '17 at 11:47

Ibraheem Ahmed · Answer 1 · 2022-07-16T21:28:33.527

11

None of the standard library collections maintain insertion order. You can instead use IndexMap from the indexmap crate, which preserves insertion order as long as you don't call remove.

use indexmap::indexmap;

let map = indexmap! {
    "Z" => 1,
    "T" => 2,
    "R" => 3,
    "P" => 4,
    "K" => 5,
    "W" => 6,
};
    
for (k, v) in map {
    println!("{}: {}", k, v);
}

// Z: 1
// T: 2
// R: 3
// P: 4
// K: 5
// W: 6

It accomplishes this by storing a hash table where the iteration order of the key-value pairs is independent of the hash values of the keys. This mean that lookups may be slower than the standard HashMap, but iteration and removal is very fast.

edited Jul 16 '22 at 21:28

answered Mar 29 '21 at 17:27

Ibraheem Ahmed

11,652
2
48
54

Extra context: the slower lookups are still O(1) average, but worse memory locality. – Mark Dec 18 '21 at 22:57
1

I thought I'd add: While true that calling `remove` breaks the preservation of the insertion-order, you can just call [shift_remove](https://docs.rs/indexmap/latest/indexmap/map/struct.IndexMap.html#method.shift_remove) instead, which will preserve the insertion order. (slower obviously, but for many use-cases that's perfectly fine) – Venryx Jan 14 '23 at 09:20

score 10 · Accepted Answer · answered May 14 '15 at 17:10

10

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.

answered May 14 '15 at 17:10

Shepmaster

388,571
95
1,107
1,366

8

If external crates are allowed, the [linked-hash-map](https://crates.io/crates/linked-hash-map) crate is such a collection tracking insertion order. – kennytm Apr 25 '16 at 14:20
@nalply and what happens when you try that? I expect you won't be able to add more than one item to the map before you run into an error. – Shepmaster Jul 02 '21 at 12:56
@Shepmaster, yeah, problably only possible for immutable things if at all, didn't try out. Retired my comment. – nalply Jul 02 '21 at 18:46
@nalply my point was that using `entry` to add to the hashmap *mutates the hashmap* and then the `Entry` is tied to the hashmap via a lifetime. This means you can only have one existing `Entry`at a time to prevent memory unsafety. – Shepmaster Jul 02 '21 at 18:50

score 6 · Answer 3 · answered May 14 '15 at 17:46

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.

How do I sort a map by order of insertion?

3 Answers3

Linked

Related