3
\$\begingroup\$

I'm learning Rust so as an exercise I'm trying to write a datatype wrapping the builtin BTreeMap to allow it to store duplicates. Like the STL multimap type. The functions I have:

fn insert_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32, v: V)
{
    if map.contains_key(&k) {
        map.get_mut(&k).unwrap().push(v);
    } else {
        let mut vec: Vec<V> = Vec::new();
        vec.push(v);
        map.insert(k, vec);
    }
}

fn remove_dup_internal<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) -> usize {
    if map.contains_key(&k) {
        let ref mut vec = map.get_mut(&k).unwrap();
        vec.pop();
        return vec.len();
    }
    return 10;
}

fn remove_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) {
    if remove_dup_internal(map, k) == 0 {
        map.remove(&k);
    }
}

They work, but I would like to be able to parametrize the key too and not just the value. And the remove_dup / remove_dup_internal is because there was a strange compiler error about borrowing I couldn't solve.

\$\endgroup\$
  • \$\begingroup\$ It's worth noting that this is not how std::multimap is implemented. Using a Vec for each entry is going to be much less efficient. \$\endgroup\$ – Timmmm Dec 29 '19 at 23:00
7
\$\begingroup\$
  1. Idiomatic Rust style is to place braces on same line. When the function definition gets longer than one line then the brace lives on the next line all on its own.
  2. Learn and love the entry API. Not only does the code end up clearer, it's faster too.
  3. Don't use magic numbers. What is 10 supposed to mean? Why not 9 or 11 or 42? The very least you can do is to create a name for the magic value that indicates its purpose. However, there are usually better options in Rust. For example, if you need to indicate a potential absence of something, use Option.
  4. It's very rare to use ref in a let pattern binding.
  5. Avoid uses of unwrap, especially when they parallel existing code that ensures that the unwrap cannot fail. Usually there's a way to avoid duplicating the check.
  6. Learn about transformative methods on Option and Result, map being the one used here.
  7. Don't use an explicit return at the end of a function.
use std::collections::BTreeMap;

fn insert_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32, v: V) {
    map.entry(k).or_insert_with(Vec::new).push(v)
}

fn remove_dup_internal<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) -> Option<usize> {
    map.get_mut(&k).map(|vec| {
        vec.pop();
        vec.len()
    })
}

fn remove_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) {
    if remove_dup_internal(map, k) == Some(0) {
        map.remove(&k);
    }
}

Even better, the helper function isn't needed with the Entry API. We can also note that comparing the length against 0 is the same as the is_empty method:

use std::collections::btree_map::Entry;

fn remove_dup<V>(map: &mut BTreeMap<i32, Vec<V>>, k: i32) {
    if let Entry::Occupied(mut entry) = map.entry(k) {
        entry.get_mut().pop();
        if entry.get().is_empty() {
            entry.remove();
        }
    }
}

Now adding and removing a value each only require a single location computation and lookup.

Parameterizing the key can be done by:

  1. Replacing i32 with K.
  2. Adding K to the generic declaration list.
  3. Following the compiler error message to restrict K to types that implement Ord.
use std::collections::{btree_map::Entry, BTreeMap};

fn insert_dup<K, V>(map: &mut BTreeMap<K, Vec<V>>, k: K, v: V)
where
    K: std::cmp::Ord,
{
    map.entry(k).or_insert_with(Vec::new).push(v)
}

fn remove_dup<K, V>(map: &mut BTreeMap<K, Vec<V>>, k: K)
where
    K: Ord,
{
    if let Entry::Occupied(mut entry) = map.entry(k) {
        entry.get_mut().pop();
        if entry.get().is_empty() {
            entry.remove();
        }
    }
}

Any reason you are calling both entry.get and entry.get_mut in remove_dup?

This can be interpreted multiple ways:

  1. "Why not call entry.get in both cases?" — because the chained pop needs a mutable receiver in order to do its work.
  2. "Why not call entry.get_mut in both cases?" — this would compile, but the value doesn't need to be mutable for is_empty, and I find it better to opt-out of as much mutability as possible.
  3. "Why not call entry.get_mut once and store it in variable?" — Now that non-lexical lifetimes are enabled, the straight-forward way works and you should do this. Before that, however,you would run into borrow checker issues because binding the result of get_mut to a variable will cause entry to be borrowed for the rest of the scope. This prevents using entry.remove:

    if let Entry::Occupied(mut entry) = map.entry(k) {
        let vec = entry.get_mut();
        vec.pop();
        if vec.is_empty() {
            entry.remove();
        }
    }
    
    error[E0505]: cannot move out of `entry` because it is borrowed
      --> src/main.rs:17:13
       |
    14 |         let vec = entry.get_mut();
       |                   ----- borrow of `entry` occurs here
    ...
    17 |             entry.remove();
       |             ^^^^^ move out of `entry` occurs here
    

    If get or get_mut were expensive, you could introduce a scope to constrain the borrow:

    if let Entry::Occupied(mut entry) = map.entry(k) {
        let should_remove = {
            let vec = entry.get_mut();
            vec.pop();
            vec.is_empty()
        };
        if should_remove {
            entry.remove();
        }
    }
    

    However, I don't believe that get or get_mut are expensive.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Ord is in the prelude, so it's not necessary to write std::cmp::Ord in full. \$\endgroup\$ – Francis Gagné Nov 7 '16 at 5:55
  • \$\begingroup\$ Any reason you are calling both entry.get and entry.get_mut in remove_dup? \$\endgroup\$ – Björn Lindqvist Nov 7 '16 at 12:35
  • \$\begingroup\$ @BjörnLindqvist oops, forgot to ping you - updated the answer. \$\endgroup\$ – Shepmaster Nov 7 '16 at 16:52
  • \$\begingroup\$ Minor nit: "only require a single hash" BTreeMap doesn't use hashing. \$\endgroup\$ – Timmmm Dec 29 '19 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.