Difference between Iterating over BTreeMap and &BTreeMap

Question

I am trying to understand the difference between

let rows = Vec::new();
for (k, v) in my_btree { // BTreeMap<i64, String>
    rows.push((&k, &v)) // k and v don't live long enough.
}

and:

let rows = Vec::new();
for (k, v) in &my_btree { // BTreeMap<i64, String>
    rows.push((k, v))
}

Can someone please explain the difference between iterating over &my_btree and iterating over my_btree?

Specifically I would like to understand how ownership changes and what memory is being referred to in both of those examples above

Here is a full example of what I am trying to do (target_function is a library I am working with that has a function signature like it has here, so that can't change):

use std::collections::BTreeMap;

struct SomeStruct {
    x: BTreeMap<i64, String>
}

fn target_function(rows: &[(&i64, &String)]) {
    for row in rows.iter() {
        println!("{:#?}", row);
    }    
}
fn test(ss: SomeStruct) {
    let mut rows = Vec::new();

    for (k, v) in &ss.x {
        rows.push((k, v));
    }
    target_function(&rows[..]);
}

fn main() {
    let mut a = BTreeMap::new();
    a.insert(1, "hello".to_string());
    a.insert(2, "goodbye".to_string());

    let mystruct = SomeStruct{x: a};
    test(mystruct);
}

Answer 1

The subtlety with this is with the double implementation of IntoIterator for BTreeMap (and most collections, actually). You can see it in the documentation, in order:

• impl<K, V> IntoIterator for BTreeMap<K, V>

This is your first case. What you are doing is moving the BTreeMap and consuming it to produce a (K, V) iterator. You can convince yourself of this with the following snippet:

let mut my_btree:BTreeMap<i64, String> = BTreeMap::new();
my_tree.insert(3, "this is a test".to_string());
let mut rows = Vec::new();
for (k, v) in my_btree { // BTreeMap<i64, String>
    rows.push((k, v))
}

This consumes my_btree and yields (K, V) pairs, one by one. Since these pairs are owned, you can safely push them into the Vec you provided. In your snippet, you had &k and &v - and these references would never work seeing as the items would be immediately dropped from scope.

• impl<'a, K, V> IntoIterator for &'a BTreeMap<K, V>

This is your second case. In this case, your iterator is now (&'a K, &'a V) and you can easily convince yourself of this by trying to move the Vec out of scope of the BTreeMap, like so:

fn does_not_work<'a>() -> Vec<(&'a i64, &'a String)> {
    let my_btree:BTreeMap<i64, String> = BTreeMap::new();
    let mut rows = Vec::new();
    for (k, v) in &my_btree { // BTreeMap<i64, String>
        rows.push((k, v))
    }
    rows
}

This will not compile because you inserted a bunch of references to elements in your BTreeMap, and you then drop it (due to it moving out of scope) - all those references would be invalid if the borrow checker didn't come to the rescue.

So, that is the difference - in one case, you are consuming the BTreeMap to operate on owned structs, in the other you are working on references.

Your example functions due to this - you are never actually dereferencing the map due to the &ss.x iterator, which never consumes the map.