What data structure should I use that preserves insertion order and allows multiple values per key?

user_12103188 0
Viewed 49

I have code that looks more or less like this:

use std::collections::BTreeMap;

#[derive(Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
pub enum ObjectType {
    TypeOne = 1,
    TypeTwo = 2
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ObjectOne {
    pub length: usize,
    pub width: usize
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ObjectTwo {
    pub circumference: f64
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub struct ObjectWrapper {
    ObjectOne(ObjectOne),
    ObjectTwo(ObjectTwo)
}

fn main() {
    let mut tree: BTreeMap<ObjectType, Vec<ObjectWrapper>> = BTreeMap::new();

    tree.insert(ObjectType::TypeOne, vec![/*first*/]);
    tree.insert(ObjectType::TypeTwo, vec![/*second*/]);
    tree.insert(ObjectType::TypeOne, vec![/*third*/]);

    for (key, value) in tree {
        println!("{}: {}");
    }
}

Currently would print:

TypeOne: [/*third*/]
TypeTwo: [/*second*/]

My issue is that BTreeMap is by default ordered by key, but I want to iterate over elements in the order they were inserted. And I want to be able to add multiple elements with the same key. I would like the above to print:

TypeOne: [/*first*/]
TypeTwo: [/*second*/]
TypeOne: [/*third*/]

Is there any data structure that can achieve that?

rust data-structures
1 Answers

For this problem, you can use two maps together:

  • one with arbitrary keys which preserves insertion order (for example, a BTreeMap with serial-numbers for keys), and
  • another which maps the ObjectType to a vector or set of the arbitrary keys in the first map.

This way you can iterate over items by insertion order (using the first map) but also find them by ObjectType (using the second map).

Exactly which data structures to use for this will depend on what operations you want to be able to perform efficiently. For example, if you want to delete items, then the second map's values must be a set, not a vector, so finding a specific arbitrary-key in it is not a linear search. But if you never remove items, then a vector is cheaper.

user_996920
Related