In Rust std::collections::BTreeMap, will the allocated memory be kept on calling clear()?

Question

In std::vec, the documentation says very clear that clear() has no effect on the allocated capacity of the vector. The doc does not mention that in BTreeMap.

So what will happen to the allocated memory when clear() is called on a BTreeMap?

Also, different to std::vec, there is no shrink_to provided in BTreeMap. Is the allocated memory get released only when the map is dropped?

Answer 1

So what will happen to the allocated memory when clear() is called on a BTreeMap?

It's deallocated. It's actually pretty flagrant in the source:

    pub fn clear(&mut self) {
        // avoid moving the allocator
        drop(BTreeMap {
            root: mem::replace(&mut self.root, None),
            length: mem::replace(&mut self.length, 0),
            alloc: self.alloc.clone(),
            _marker: PhantomData,
        });
    }

So the current map is reinitialised (self.root set to None and self.length to 0), all its data is moved to an other map, and that other map is then dropped.

Also, different to std::vec, there is no shrink_to provided in BTreeMap. Is the allocated memory get released only when the map is dropped?

No, it's released as entries are removed and blocks are emptied.

Vec uses large amortization allocation in order to perform amortized O(1) push, essentially it's a large buffer and when it's full it doubles in size¹, the size of the underlying buffer is the "capacity", and how full it is is the "length". HashMap is the same, with amortised O(1) inserts².

But a btree is a tree of nodes with 6~11 entries³. These nodes are split when they would exceed 11 entries, and they're merged when they fall below 5, so while there is excess capacity, it's local and distributed and it's managed on the fly, you can't influence it globally save by parameterizing the node size bounds.

That is also why Vec and HashMap have with_capacity, but BTreeMap does not.

---

1: in most implementations though a few use a ratio of 1.5

2: and the added wrinkle that a hashmap has "effective" and "actual" capacities, the difference being the load factor, the actual capacity is rarely exposed though

3: IIRC, for the Rust standard library, parameters vary based on use case