The Cursor API for Rust's BTreeMap

For a little experiment I recently tried to efficiently mutate a specific key range in an ordered map in C++. I then tried the same thing in rust and discovered an API I did not know about and that I really like.

The task

While not getting into the details, what I was trying to do involved finding a specific range of keys in an ordered map and moving some values around, removing some and inserting some in that range. I wanted to do this with the best possible performance, so specifically I wanted to

• search the map only once (which is O(log(n)) over the size of the map)

• use move semantics over copy semantics where possible on both keys and values

With std::map

In C++ the standard ordered map is std::map. The way to approach this task in C++ is to get an iterator to the start or end of the targeted range using the methods

std::map::lower_bound(key) // largest entry that is not smaller than key
std::map::upper_bound(key) // smallest entry greater then key

and then use the iterator-based overloads for mutations and std::map::extract to efficiently move elements around without copying.

The problem with this approach ist that while std::map takes great care to keep iterators valid as much as possible, mutations, especially extract, actually invalidate the iterator you pass to them (which is unavoidable when removing the element it points to) so you really have to take care to not dereference invalid iterators at some point.

Another thing that I found complicated (but I'm also not a C++ expert by any means) is to keep track of the many different overloads of methods such as insert that actually behave differently and return different kinds of values.

With BTreeMap

Rust's standard ordered map is std::collections::BTreeMap. While C++'s std::map uses a Red-Black-Tree under the hood rust uses (as the name suggests) a B-Tree but that should be considered an implementation detail for the sake of this post as the two serve the same purpose and provide very similar performance guarantees.

First I was surprised to learn that almost all of BTreeMap's methods just accept a key and return or mutate elements after a lookup (which always takes O(log(n))). Then I discovered that there are two new APIs added in (at the time of writing) nightly rust, obviously inspired by std::map, called

BTreeMap::lower_bound
BTreeMap::upper_bound
// and the mutable equivalents
BTreeMap::lower_bound_mut
BTreeMap::upper_bound_mut

that actually return something called a Cursor (or CursorMut, its mutable equivalent) that do exactly what I need.

Cursors are like iterators but they do not point at an element but between two elements so I can use them to obtain a mutable Cursor that points before the first element of my range.

Then I can use this mutable Cursor to

• efficiently insert elements into the gap that my cursor points at and have the cursor point either before or after the inserted element afterwards depending on where I want to continue with the next operation

• remove elements left and right of the cursor and have the cursor safely point at the gap that my removal operation left

• move the removed keys and values to another place efficiently because rust uses move-semantics by default

• get references to keys and values left and right of the cursor using it's peek-methods

• freely move the cursor left and right by one element at a time using next and prev.

This API feels extremely natural for the job and makes it super easy to do this whole class of operations in an efficient and safe-by-default way.