358 Intermediate

358: IndexMap Ordered (Insertion-Order Map)

Functional Programming

Tutorial

The Problem

HashMap iterates in arbitrary order; BTreeMap iterates in key-sorted order. But sometimes you need to iterate in insertion order — preserving the sequence in which entries were added. This is how Python dicts work since 3.7, how JSON objects are commonly expected to behave, and how HTTP headers must be processed. The indexmap crate provides this natively; this example demonstrates the pattern using a HashMap + Vec<K> combination to illustrate the mechanism, which you can replace with the real IndexMap crate in production.

🎯 Learning Outcomes

• Build an insertion-order-preserving map using HashMap<K, V> + Vec<K> for order tracking

• Insert maintaining both the hash map (O(1) lookup) and the order vector (O(1) push)

• Iterate in insertion order by walking the Vec<K> and looking up values

• Understand why skipping the order vector loses insertion order guarantees

• Recognize that the indexmap crate is the production-quality solution

• Know the cost: remove is O(n) due to Vec compaction (use swap_remove for O(1))

Code Example

#![allow(clippy::all)]
//! # IndexMap Ordered
//! HashMap that preserves insertion order (simulated without external crate).

use std::collections::HashMap;

pub struct OrderedMap<K, V> {
    map: HashMap<K, V>,
    order: Vec<K>,
}

impl<K: Clone + Eq + std::hash::Hash, V> OrderedMap<K, V> {
    pub fn new() -> Self {
        Self {
            map: HashMap::new(),
            order: Vec::new(),
        }
    }

    pub fn insert(&mut self, key: K, value: V) {
        if self.map.insert(key.clone(), value).is_none() {
            self.order.push(key);
        }
    }

    pub fn get(&self, key: &K) -> Option<&V> {
        self.map.get(key)
    }

    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
        self.order
            .iter()
            .filter_map(|k| self.map.get(k).map(|v| (k, v)))
    }

    pub fn len(&self) -> usize {
        self.map.len()
    }
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }
}

impl<K: Clone + Eq + std::hash::Hash, V> Default for OrderedMap<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn preserves_order() {
        let mut m = OrderedMap::new();
        m.insert("b", 2);
        m.insert("a", 1);
        m.insert("c", 3);
        let keys: Vec<_> = m.iter().map(|(k, _)| *k).collect();
        assert_eq!(keys, vec!["b", "a", "c"]);
    }
    #[test]
    fn get_works() {
        let mut m = OrderedMap::new();
        m.insert("k", 42);
        assert_eq!(m.get(&"k"), Some(&42));
    }
}

(* OCaml: ordered association list *)

module OrderedMap = struct
  type ('k,'v) t = { pairs: ('k*'v) list ref; compare: 'k->'k->int }
  let make cmp = { pairs=ref []; compare=cmp }
  let insert m k v =
    m.pairs := (k,v) :: List.filter (fun (k2,_) -> m.compare k k2 <> 0) !(m.pairs)
  let find m k = List.assoc_opt k !(m.pairs)
  let to_list m = List.rev !(m.pairs)
end

let () =
  let m = OrderedMap.make compare in
  OrderedMap.insert m "b" 2; OrderedMap.insert m "a" 1; OrderedMap.insert m "c" 3;
  List.iter (fun (k,v) -> Printf.printf "%s: %d\n" k v) (OrderedMap.to_list m)

Key Differences

Aspect	Rust `HashMap` + `Vec`	OCaml assoc list
Lookup	O(1)	O(n)
Insertion	O(1) amortized	O(1) prepend
Iteration	Insertion order	Insertion order (reversed)
Remove	O(n) for ordered remove	O(n) filter
Production solution	`indexmap` crate	`orderedhashtbl` package

OCaml Approach

OCaml's association lists ((key * value) list) naturally preserve insertion order:

(* Association list: insertion-ordered, O(n) lookup *)
let insert lst k v = (k, v) :: lst  (* prepends — reverse insertion order *)
let get lst k = List.assoc_opt k lst
let iter lst f = List.iter (fun (k, v) -> f k v) (List.rev lst)

(* For production: use the ordered-hashtbl or sequence package *)

Association lists are the OCaml idiom for small ordered maps. For larger maps, the orderedhashtbl package or CCHashtbl.Poly with order tracking mirrors the HashMap+Vec approach.

Full Source

#![allow(clippy::all)]
//! # IndexMap Ordered
//! HashMap that preserves insertion order (simulated without external crate).

use std::collections::HashMap;

pub struct OrderedMap<K, V> {
    map: HashMap<K, V>,
    order: Vec<K>,
}

impl<K: Clone + Eq + std::hash::Hash, V> OrderedMap<K, V> {
    pub fn new() -> Self {
        Self {
            map: HashMap::new(),
            order: Vec::new(),
        }
    }

    pub fn insert(&mut self, key: K, value: V) {
        if self.map.insert(key.clone(), value).is_none() {
            self.order.push(key);
        }
    }

    pub fn get(&self, key: &K) -> Option<&V> {
        self.map.get(key)
    }

    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
        self.order
            .iter()
            .filter_map(|k| self.map.get(k).map(|v| (k, v)))
    }

    pub fn len(&self) -> usize {
        self.map.len()
    }
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }
}

impl<K: Clone + Eq + std::hash::Hash, V> Default for OrderedMap<K, V> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn preserves_order() {
        let mut m = OrderedMap::new();
        m.insert("b", 2);
        m.insert("a", 1);
        m.insert("c", 3);
        let keys: Vec<_> = m.iter().map(|(k, _)| *k).collect();
        assert_eq!(keys, vec!["b", "a", "c"]);
    }
    #[test]
    fn get_works() {
        let mut m = OrderedMap::new();
        m.insert("k", 42);
        assert_eq!(m.get(&"k"), Some(&42));
    }
}

(* OCaml: ordered association list *)

module OrderedMap = struct
  type ('k,'v) t = { pairs: ('k*'v) list ref; compare: 'k->'k->int }
  let make cmp = { pairs=ref []; compare=cmp }
  let insert m k v =
    m.pairs := (k,v) :: List.filter (fun (k2,_) -> m.compare k k2 <> 0) !(m.pairs)
  let find m k = List.assoc_opt k !(m.pairs)
  let to_list m = List.rev !(m.pairs)
end

let () =
  let m = OrderedMap.make compare in
  OrderedMap.insert m "b" 2; OrderedMap.insert m "a" 1; OrderedMap.insert m "c" 3;
  List.iter (fun (k,v) -> Printf.printf "%s: %d\n" k v) (OrderedMap.to_list m)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn preserves_order() {
        let mut m = OrderedMap::new();
        m.insert("b", 2);
        m.insert("a", 1);
        m.insert("c", 3);
        let keys: Vec<_> = m.iter().map(|(k, _)| *k).collect();
        assert_eq!(keys, vec!["b", "a", "c"]);
    }
    #[test]
    fn get_works() {
        let mut m = OrderedMap::new();
        m.insert("k", 42);
        assert_eq!(m.get(&"k"), Some(&42));
    }
}

Deep Comparison

OCaml vs Rust: Indexmap Ordered

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

**remove with order**: Implement remove(&mut self, key: &K) -> Option<V> that removes the key from both the HashMap and the Vec<K>; use Vec::retain for correctness or swap_remove for O(1) (unordered removal).

JSON object ordering: Use OrderedMap<String, String> to represent a JSON object and serialize it with keys in insertion order; compare output with HashMap-based serialization.

Indexmap crate: Replace OrderedMap with the indexmap::IndexMap crate; verify that get_index(0) returns the first inserted key-value pair, and that iteration order matches insertion order.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust