A dictionary retaining orders?


#1

I’m looking for a dictionary / map type that retains insertion orders for the items. Something like this:

let map = SomeMap::new();
map.insert("foo", 17);
map.insert("bar", 42);
map.get("bar"); // returns Some(42)
map.keys(); // Returns iterator containing "foo", "bar"

I have tried some searching at crates.io, but I don’t really know what to seach for.


#2

I think you’d look at linked-hash-map. Maybe ordermap, but that one doesn’t do full insertion order (not after removal).


#3

It sounds like you’re looking for an ordered dictionary/hashmap. I know there are a couple implementations floating around the interwebs, but I can’t seem to find them on crates.io.

Implementing your own is fairly straightforward in that you have a vector alongside the original hashmap that keeps track of insertions and deletions. You can probably make it more memory efficient by storing things in some sort of object arena and have the hashmap and vector both hold pointers to the object.


#4

Thanks for the suggestion! I think I’ll go with ordermap, since linked-hash-map seems to be more or less abandoned. Since it provides a retain method, I can do order-conserving remove using that (it’ll be less efficient, but my dictionaries will rarely contain more than a handfull of entries, so I don’t think that matters).


#5

I think that poses a question, what ordering guarantees does its retain have? We should just get around to implementing the full tombstone and order variant of ordermap at some point.

That said, the linked hash map really is quite a lot more versatile since it allows freshening key-value pairs etc (like an LRU).


#6

I would assume that retain keeps the ordering. If it is possible to provide a more efficient algorithm while not keeping the ordering, maybe implement that separatley with another name?

Anyway, I might not use ordermap after all, since it requires Hash on its keys but does not implement Hash itself, and the type I use for both keys and values is recursive, and may contain another map of the same type. Maybe I’ll just roll my own as @Michael-F-Bryan suggests.


#7

I ended up rolling my own. Since my dictionaries are typically small, my current implementation is just a Vec<(Key, Value)> that I search linearly. I might add some kind of index, or switch to an existing implementation if I find one, later …