BTreeMap - rust-course

The BTreeMap is a B-tree data structure that stores key/value pairs in an ordered way. See Program 1. The main features of a BTreeMap are:

The keys must implement the Ord trait.
Each node of a B-tree has a maximum of $K$ keys.
Iteration is made in key order, and has 𝒪( $\log(n)$ ) complexity.

                     ┌──────┬──────┬──────┬──────┐
                     │10/"a"│16/"r"│23/"z"│      │
                     └──────┴──────┴──────┴──────┘
                    ╱               ╲      ╲
                   ╱                 ╲      ╲
┌──────┬──────┬──────┬──────┐         ▏     ┌──────┬──────┬──────┬──────┐
│ 2/"t"│ 5/"e"│      │      │         ▏     │25/"w"│29/"o"│      │      │
└──────┴──────┴──────┴──────┘         ▏     └──────┴──────┴──────┴──────┘
                        ┌──────┬──────┬──────┬──────┐
                        │17/"w"│19/"o"│21/"j"│22/"v"│
                        └──────┴──────┴──────┴──────┘

Program 1:A BTreeMap with integer keys and string values, using a maximum of 4 keys per node.

The main methods of the BTreeMap are presented in Table 1.

Table 1:Some methods of BTreeMap

Method	Description
`append(&other)`	Moves the elements of another map into this map.
`clear()`	Removes all elements.
`contains_key(k)`	Returns `true` if this map contains the key `k`.
`entry(k)`	Gives access to key/value pair.
`get(k)`	Returns a reference to the value, if any. The returned type is `Option<&V>`.
`insert(k, v)`	Inserts a new key/value pair.
`is_empty()`	Returns `true` if this map contains no elements.
`iter()`	Returns an iterator on all key/value pairs.
`keys()`	Returns an iterator over the keys. Order is arbitrary.
`len()`	Returns the number of elements.
`new()`	Creates a new map.
`range(r)`	Returns a double-ended iterator over a range of elements in the map.
`remove(k)`	Removes the specified key from the map.
`split_off(k)`	Splits the map into two at the given key. The current map is modified to contain all elements with a key lower than the given key. Remaining elements are returned into a new map.
`values()`	Returns an iterator over the values. Order is arbitrary.

29.1.1Creating a new instance¶

To create a new hash map BTreeMap<K, V>, an easy way, like for the Vec type, is to let the compiler infer the type. Inserting at least one key/value pair will give the compiler the information it needs:

use std::collections::BTreeMap;

let mut scores = BTreeMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

Couldn't automatically determine type of variable `scores`.
Please give it an explicit type.

Ownership of keys and values

When inserted inside a map, the keys and values may be copied or moved, depending on their type. Types that implement the Copy trait are copied (e.g.: basic types), other types are moved. For those last types, we may wish to clone them before passing them:

let k = String::from("Red");
scores.insert(k.clone(), 23);
k

29.1.2Getting a value¶

Getting a value from the map is done using the get() method, which returns an Option<V>:

let team_name = String::from("Blue");
match scores.get(&team_name) {
  Some(score) => println!("The score of team {team_name} is {score}."),
  None => println!("No score for team {team_name}"),
}

BTreeMap implements the Index trait, and thus provides the indexing operator ([]) for retrieving a value. Example:

scores["Blue"]

29.1.3Iterating¶

Using a for loop we can loop onto the key/value pairs:

for (k, v) in &scores {
  println!("{k}: {v}");
}

29.1.4Replacing an existing value¶

Inserting a key/value pair, replaces the eventual existing key:

scores.insert(String::from("Blue"), 34);
scores

29.1.5Adding a value if no key present¶

The or_insert() of the Entry structure, allows to insert a key/value only if the key is not already defined:

scores.entry(String::from("Green")).or_insert(18)

29.1.6Updating an existing value¶

We suppose we want to increment the score of a team. We retrieve a reference on the current score of team "Red", using the or_insert() method in case the team is not declared, and increment it by dereferencing it with the * operator. The or_insert() method returns a &mut V:

{
  let count = scores.entry("Red".to_string()).or_insert(0);
  *count += 1;
  println!("count is now {count}");
}

Here is the result:

scores