Ordered Hashmap - Iterations

help
1

Hi,
I'm trying to implement a HashMap which preserves insertion order.

struct OrderedMap<Key: Eq + Hash, Value> {
    keys: Vec<Key>,
    data: std::collections::HashMap<Key, Value>,
}

I'm trying to iterate this, but failing (both mutable and immutable:

impl<Key: Eq + Hash, Value> OrderedMap<Key, Value> {
    pub fn iter_mut(&mut self) -> impl Iterator<Item = (&Key, &mut Value)> {
        // self.data.iter_mut() this works, but is not in insertion order
        let Self { keys, data } = self;
        keys.iter().map(|x| (x, data.get_mut(x).unwrap()))
    }
}

Note that I want to keep insertion order after removing elements, so indexmap is not what I want.

I believe the solution might be using an intermediate type, similar to hashmap's IterMut type, but I'm unable to figure out the lifetimes bounds.

Thank you :slight_smile:

Edit: Link to playground

2

The challenge is that you need a way to get a &mut to every Value in the HashMap with a single call to the HashMap, or else the compiler can't prove that no two overlapping &mut Value are returned.

Using unsafe to work around this would be unsound too, e.g. if hashes collide, a value for which a &mut Value was already returned may need examined to test for equality in get_mut, but that would be an aliasing violation. (That's also not as far fetched as you might think.)

I think you'll have to redesign things unless you want to collect all the &mut Value in arbitrary order and then painfully sort them based on your Vec<Key>.

3

Are you aware that indexmap has two removal methods? swap_remove disrupts the order in constant time, and shift_remove preserves total order in linear time.

3 Likes
4

You can rearrange your structure like this:

struct OrderedMap<Key, Value> {
    data: Vec<(Key, Value)>,
    positions: std::collections::HashMap<Key, usize>,
}

The values in positions are indexes into data. Now, your iter_mut() can be implemented in terms of std::slice::IterMut. However, this does mean that the contents of positions have to be updated whenever anything moves in data. You can keep these moves lower by allowing data to be sparse (i.e. Vec<Option<(Key, Value)>>), though that's its own tradeoff.

2 Likes
5

Or another way if cloning Keys is acceptable.

(You want insertion_order to be able to look things up by key, presumably.)

6

No, I didn't know. Maybe this should be stressed in the description?

7

That is a really simple solution, thank you!

8

That's a cool solution, thank you. Cloning is ok for me, but I going with indexmap.

9

By the way, there is no need to make three separate reply posts If you select the text you are responding to and click the "Quote" button that pops up, you can put three linked quotes in one post, and it will be easier to read your responses with context.

1 Like
10

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.