No DoubleEndedIterator for collections::HashMap?

1

I have a matrix-like data structure where each column is an entry in a HashMap<String,Vec<f64>>. (Bizarre, I know, but just play along for a minute.) I find myself doing column operations by iterating on the values, e.g.

for col in map.values_mut() { ... }

This works great when I am doing doing "forward" iterations, but when I need to do "backwards" iterations, I've found that none of the HashMap iterators implement DoubleEndedIterator, e.g. map.values().rev() does not work. After probing around the HashMap implementation, at face value, there does not appear to be any technical reason for this -- it seems that internally the key/value pairs can be iterated in reverse (https://github.com/rust-lang/rust/blob/master/src/libstd/collections/hash/table.rs#L888), so I wonder if this was just an oversight?

Thanks,
Jason

2

HashMap entries are not ordered in a meaningful way, so there is no such thing as "forward" or "backward" iteration. There is just "some order" that visits every entry but in an unspecified order.

BTreeMap and LinkedHashMap are ordered maps so they have a forward and backward order. Both have DoubleEndedIterator as you would expect.

2 Likes
3

Sure, I don't disagree. But when you call map.iter(), some ordering is induced (albeit arbitrary, as you rightly observed). Furthermore, this ordering remains constant between subsequent calls to map.iter() (provided nothing else has changed in the hash table in the meantime). I am asking why this order cannot be "arbitrarily" reversed, as it apparently is done internally.

4

Probably because arbitrary functionality doesn't belong in std. You're essentially asking why a semantically meaningless operation doesn't exist.

Why do you want to iterate in "reverse" over a HashMap?

5

Hm, here is another way of asking:

let a=map.iter().collect::<Vec<_>>();
let b=map.iter().collect::<Vec<_>>();
assert_eq(a, b);

Given an unchanged hash map, at the moment the order keys and values are visited are invariant between calls to the iterator. This is a simple consequence of how hash tables are internally represented. Is this an invariant that std does not want to guarantee for some possible future modification? (eg randomize the order to so to keep the RandomState secret?) If so, then a lack of DoubleEndedIterator makes total sense. If not, then I don't see why DoubleEndedIterator should remain unimplemented (since the data structure appears to support it), even if it at face-value it seems weird.

6

I think you're letting the implementation dictate what operations to expose rather than the semantics of the abstraction. HashMap has an API and specific properties it provides. Order is not one of them, and so supporting double ended iteration doesn't make semantic sense, irrespective of whether (today's) implementation supports that or not. It's just a meaningless operation for that abstraction. If you're a stdlib maintainer, you most definitely do not want to expose things that you don't want to be on the hook for maintaining, debugging, documenting, testing, and so on. Rust stdlib developers in particular are very keen on keeping stdlib lean (too lean, some would argue).

1 Like
7

Maybe https://crates.io/crates/ordermap would work for what you need?

2 Likes
8

@vitalyd, fair enough. Thanks for your insights! @notriddle, that is a super interesting package, and it is indeed more appropriate for my use-case.