# BTreeMap as a multimap in Rust

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.

• 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. Dec 29, 2019 at 23:00

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.

• Ord is in the prelude, so it's not necessary to write std::cmp::Ord in full. Nov 7, 2016 at 5:55
• Any reason you are calling both entry.get and entry.get_mut in remove_dup? Nov 7, 2016 at 12:35
• @BjörnLindqvist oops, forgot to ping you - updated the answer. Nov 7, 2016 at 16:52
• Minor nit: "only require a single hash" BTreeMap doesn't use hashing. Dec 29, 2019 at 22:59