В Rust std::collections::BTreeMap сохранится ли выделенная память при вызове метода Clear()?

BTreeMap::clear() освобождает память, , как видно из кода . Это неизбежно, поскольку структура данных представляет собой дерево, а в дереве нет понятия неиспользуемых элементов.

Кроме того, в отличие от std::vec, в shrink_to нет BTreeMap. Выделенная память освобождается только при удалении карты?

По той же причине. shrink_to нет, потому что он не нужен. В отличие от Vec, карта немедленно освободит неиспользуемые узлы.

Так что же произойдет с выделенной памятью, когда метод Clear() вызывается в BTreeMap?

Он освобожден. На самом деле это довольно вопиюще в исходнике:

    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,
        });
    }

Таким образом, текущая карта повторно инициализируется (self.root устанавливается в None, а self.length в 0), все ее данные перемещаются на другую карту, а затем эта другая карта удаляется.

Кроме того, в отличие от std::vec, в BTreeMap не предусмотрена функцияrink_to. Выделенная память освобождается только при удалении карты?

Нет, он освобождается по мере удаления записей и очистки блоков.

Vec использует большое распределение амортизации для выполнения амортизированной отправки O(1), по сути, это большой буфер, и когда он заполнен, его размер увеличивается вдвое¹, размер базового буфера — это «емкость», а насколько он заполнен — это "длина". HashMap то же самое, с амортизированными вставками O(1)².

Но btree — это дерево узлов с 6–11 записями³. Эти узлы разделяются, когда их количество превышает 11 записей, и объединяются, когда их количество падает ниже 5, поэтому, хотя существует избыточная мощность, она локальна и распределена и управляется на лету, вы не можете влиять на нее глобально, за исключением параметризации. границы размера узла.

Именно поэтому у Vec и HashMap есть with_capacity, а у BTreeMap нет.

1: в большинстве реализаций, хотя некоторые используют коэффициент 1,5.

2: и дополнительная морщина, заключающаяся в том, что хэш-карта имеет «эффективную» и «фактическую» емкость, разница заключается в коэффициенте загрузки, хотя фактическая емкость редко раскрывается.

3: IIRC, для стандартной библиотеки Rust, параметры различаются в зависимости от варианта использования.