Iter(): Vec vs. Hashset question


#1

Hi,
I am trying to understand the difference using iter() between Vec and HashSet.

this is my code:

let mut north_american_cats_set: HashSet<_> = ["Puma", "Canada Lynx", "Bobcat"].iter().cloned().collect();
let mut north_american_cats_vec: Vec<_> = ["Puma", "Canada Lynx", "Bobcat"].iter().cloned().collect();
for cat in &mut north_american_cats_set.iter() {
    println!("Cat in Set: {}", cat);
}
for cat in &mut north_american_cats_vec {
    println!("Cat in Vec {}", cat);
}

My question: Why do I have to call iter() on the HashSet but not on the Vec?
Calling iter() for HashSet is only necessary when using “&mut”. When I use only “&” or no reference at all it works.

Markus


#2

for item in &mut my_collection corresponds to for item in my_collection.iter_mut(), which HashSet doesn’t implement.
Why? Because mutating an item in a set would change its hash, which can’t be done in-place.
Why? Because HashSet is implemented as HashMap<T, ()>, meaning that the item is actually the key, and the key can’t be changed.
Why? I can’t really answer that question, but I suppose there’s some practical reasons, like having to make sure the value is moved to the right place in the table.


#3

The internal structure of a HashSet/HashMap depends on the values of the elements/keys.
To provide in-place mutation of the elements/keys you would need some kind of callback to adapt the internal structure every time an element/key is changed.

And even worse, this could also change the visible structure of the HashSet/HashMap.
Example:
Imagine a set containing the integers [1, 2, 3]. While iterating you change the value 2 to 1. Suddenly the set would become [1, 3], i.e. lose one element, because all elements have to be unique.


#4

Well, this is already a problem due to interior mutability. The “no mut” rule is more of a “don’t do this” than a “you can’t do this”.


#5

Thanks for the answers. That makes sense. Very helpful!


#6

Its actually quite difficult to use interior mutability to break this - you have to write your own Hash impl because the cell types don’t implement Hash. Its easier to break the BTree variants. But its true that its not a hard guarantee.