Struct std::collections::BTreeMap

pub struct BTreeMap<K, V, A = Global>where
    A: Allocator + Clone,{ /* private fields */ }

基于 B-Tree 的有序 map。

B 树表示缓存效率与实际最小化搜索中执行的工作量之间的根本折衷。从理论上讲，二元搜索树 (BST) 是排序的 map 的最佳选择，因为完全平衡的 BST 执行查找元素 (log₂n) 所需的理论上最小的比较量。 但是，实际上，完成此操作的方式对于现代计算机体系结构而言效率非常低。 特别是，每个元素都存储在其自己的单独堆分配节点中。 这意味着每个插入都会触发堆分配，并且每个比较都应该是缓存未命中。 由于这些在实践中都是非常昂贵的事情，我们至少不得不重新考虑 BST 策略。

相反，B 树使每个节点在连续数组中包含 B-1 到 2B-1 元素。通过这样做，我们将分配数量减少了 B 倍，并提高了搜索中的缓存效率。但是，这确实意味着平均而言，搜索将不得不进行更多的比较。 比较的精确数量取决于所使用的节点搜索策略。为了获得最佳的缓存效率，可以线性搜索节点。为了进行最佳比较，可以使用二进制搜索来搜索节点。作为一种折衷方案，我们还可以执行线性搜索，最初只检查每个 i^th 元素的某个选择 i.

当前，我们的实现仅执行简单的线性搜索。这在比较便宜的元素的小节点上提供了出色的性能。但是，未来我们将进一步探索基于 B 的选择以及可能的其他因素来选择最佳搜索策略。使用线性搜索，搜索随机元素预计会进行 B * log(n) 次比较，这通常比 BST 差。

但是，实际上，性能非常好。

以某种方式修改键是一种逻辑错误，即，当键在 map 中时，由 Ord trait 决定的键相对于任何其他键的顺序都会改变。通常只有通过 Cell，RefCell，二进制状态，I/O 或不安全代码才能实现此操作。 此类逻辑错误导致的行为未指定，但会封装到观察到逻辑错误的 BTreeMap 中，并且不会导致未定义的行为。这可能包括 panics、不正确的结果、中止、内存泄漏和未中止。

从函数获得的迭代器 (例如 BTreeMap::iter、BTreeMap::values 或 BTreeMap::keys) 按键顺序生成它们的项，并且每个返回的项采用最坏情况对数和摊销特性时间。

Examples

use std::collections::BTreeMap;

// 通过类型推断，我们可以省略显式类型签名 (在本示例中为 `BTreeMap<&str, &str>`)。
let mut movie_reviews = BTreeMap::new();

// 回顾一些电影。
movie_reviews.insert("Office Space",       "Deals with real issues in the workplace.");
movie_reviews.insert("Pulp Fiction",       "Masterpiece.");
movie_reviews.insert("The Godfather",      "Very enjoyable.");
movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");

// 检查一个特定的。
if !movie_reviews.contains_key("Les Misérables") {
    println!("We've got {} reviews, but Les Misérables ain't one.",
             movie_reviews.len());
}

// 糟糕，此评论有很多拼写错误，让我们删除它。
movie_reviews.remove("The Blues Brothers");

// 查找与某些键关联的值。
let to_find = ["Up!", "Office Space"];
for movie in &to_find {
    match movie_reviews.get(movie) {
       Some(review) => println!("{movie}: {review}"),
       None => println!("{movie} is unreviewed.")
    }
}

// 查找某个键的值 (如果找不到该键，就会出现 panic)。
println!("Movie review: {}", movie_reviews["Office Space"]);

// 迭代所有内容。
for (movie, review) in &movie_reviews {
    println!("{movie}: \"{review}\"");
}

可以从数组初始化具有已知项列表的 BTreeMap：

use std::collections::BTreeMap;

let solar_distance = BTreeMap::from([
    ("Mercury", 0.4),
    ("Venus", 0.7),
    ("Earth", 1.0),
    ("Mars", 1.5),
]);

BTreeMap 实现了一个 Entry API，它允许获取、设置、更新和删除键及其值的复杂方法：

use std::collections::BTreeMap;

// 通过类型推断，我们可以省略显式类型签名 (在本示例中为 `BTreeMap<&str, u8>`)。
let mut player_stats = BTreeMap::new();

fn random_stat_buff() -> u8 {
    // 实际上可以在这里返回一些随机值 - 现在让我们返回一些固定值
    42
}

// 仅在键不存在时才插入
player_stats.entry("health").or_insert(100);

// 仅当一个键不存在时，才使用提供新值的函数插入该键
player_stats.entry("defence").or_insert_with(random_stat_buff);

// 更新键，以防止键可能未被设置
let stat = player_stats.entry("attack").or_insert(100);
*stat += random_stat_buff();

// 使用就地可变的在插入之前修改条目
player_stats.entry("mana").and_modify(|mana| *mana += 200).or_insert(100);

Implementations

impl<K, V> BTreeMap<K, V, Global>

pub const fn new() -> BTreeMap<K, V, Global>

创建一个新的空 BTreeMap。

不会自行分配任何内容。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();

// 条目现在可以插入到空的 map 中
map.insert(1, "a");

impl<K, V, A> BTreeMap<K, V, A>where A: Allocator + Clone,

pub fn clear(&mut self)

清除 map，删除所有元素。

Examples

基本用法：

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.clear();
assert!(a.is_empty());

pub fn new_in(alloc: A) -> BTreeMap<K, V, A>

🔬This is a nightly-only experimental API. (btreemap_alloc #32838)

创建一个新的空 BTreeMap 并为 B 提供合理的选择。

Examples

基本用法：

use std::collections::BTreeMap;
use std::alloc::Global;

let mut map = BTreeMap::new_in(Global);

// 条目现在可以插入到空的 map 中
map.insert(1, "a");

impl<K, V, A> BTreeMap<K, V, A>where A: Allocator + Clone,

pub fn get<Q>(&self, key: &Q) -> Option<&V>where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

返回与键对应的值的引用。

键可以是 map 的键类型的任何借用形式，但是借用形式上的顺序必须与键类型上的顺序匹配。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), None);

pub fn get_key_value<Q>(&self, k: &Q) -> Option<(&K, &V)>where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

返回与提供的键相对应的键值对。

提供的键可以是 map 的键类型的任何借用形式，但是借用形式上的顺序必须与键类型上的顺序匹配。

Examples

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
assert_eq!(map.get_key_value(&2), None);

pub fn first_key_value(&self) -> Option<(&K, &V)>where K: Ord,

返回 map 中的第一个键值对。 该对中的键是 map 中的最小键。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
assert_eq!(map.first_key_value(), None);
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.first_key_value(), Some((&1, &"b")));

pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>where K: Ord,

返回 map 中的第一个条目以进行就地操作。 此项的键是 map 中的最小键。

Examples

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
if let Some(mut entry) = map.first_entry() {
    if *entry.key() > 0 {
        entry.insert("first");
    }
}
assert_eq!(*map.get(&1).unwrap(), "first");
assert_eq!(*map.get(&2).unwrap(), "b");

pub fn pop_first(&mut self) -> Option<(K, V)>where K: Ord,

删除并返回 map 中的第一个元素。 该元素的键是 map 中的最小键。

Examples

Draining 元素以升序排列，同时每次迭代均保持可用的 map。

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
while let Some((key, _val)) = map.pop_first() {
    assert!(map.iter().all(|(k, _v)| *k > key));
}
assert!(map.is_empty());

pub fn last_key_value(&self) -> Option<(&K, &V)>where K: Ord,

返回 map 中的最后一个键值对。 该对中的键是 map 中的最大键。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.last_key_value(), Some((&2, &"a")));

pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>where K: Ord,

返回 map 中的最后一项以进行就地操作。 此项的键是 map 中的最大键。

Examples

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
if let Some(mut entry) = map.last_entry() {
    if *entry.key() > 0 {
        entry.insert("last");
    }
}
assert_eq!(*map.get(&1).unwrap(), "a");
assert_eq!(*map.get(&2).unwrap(), "last");

pub fn pop_last(&mut self) -> Option<(K, V)>where K: Ord,

删除并返回 map 中的最后一个元素。 该元素的键是 map 中的最大键。

Examples

Draining 元素以降序排列，同时每次迭代均保留一个可用的 map。

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
map.insert(2, "b");
while let Some((key, _val)) = map.pop_last() {
    assert!(map.iter().all(|(k, _v)| *k < key));
}
assert!(map.is_empty());

pub fn contains_key<Q>(&self, key: &Q) -> boolwhere K: Borrow<Q> + Ord, Q: Ord + ?Sized,

如果 map 包含指定键的值，则返回 true。

键可以是 map 的键类型的任何借用形式，但是借用形式上的顺序必须与键类型上的顺序匹配。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

返回与键对应的值的可变引用。

键可以是 map 的键类型的任何借用形式，但是借用形式上的顺序必须与键类型上的顺序匹配。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
if let Some(x) = map.get_mut(&1) {
    *x = "b";
}
assert_eq!(map[&1], "b");

pub fn insert(&mut self, key: K, value: V) -> Option<V>where K: Ord,

将键值对插入 map。

如果 map 不存在此键，则返回 None。

如果 map 确实存在此键，则更新值，并返回旧值。 但是，键不会更新。对于不能相同的 == 类型来说，这一点很重要。

有关更多信息，请参见 模块级文档。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
assert_eq!(map.insert(37, "a"), None);
assert_eq!(map.is_empty(), false);

map.insert(37, "b");
assert_eq!(map.insert(37, "c"), Some("b"));
assert_eq!(map[&37], "c");

pub fn try_insert( &mut self, key: K, value: V ) -> Result<&mut V, OccupiedError<'_, K, V, A>>where K: Ord,

🔬This is a nightly-only experimental API. (map_try_insert #82766)

尝试将键值对插入到 map 中，并向条目中的值返回变量引用。

如果 map 已经存在此键，则不进行任何更新，并返回包含占用项和值的错误。

Examples

基本用法：

#![feature(map_try_insert)]

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
assert_eq!(map.try_insert(37, "a").unwrap(), &"a");

let err = map.try_insert(37, "b").unwrap_err();
assert_eq!(err.entry.key(), &37);
assert_eq!(err.entry.get(), &"a");
assert_eq!(err.value, "b");

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

从 map 中删除一个键，如果该键以前在 map 中，则返回该键的值。

键可以是 map 的键类型的任何借用形式，但是借用形式上的顺序必须与键类型上的顺序匹配。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.remove(&1), Some("a"));
assert_eq!(map.remove(&1), None);

pub fn remove_entry<Q>(&mut self, key: &Q) -> Option<(K, V)>where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

从 map 中删除一个键，如果该键以前在 map 中，则返回存储的键和值。

键可以是 map 的键类型的任何借用形式，但是借用形式上的顺序必须与键类型上的顺序匹配。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.remove_entry(&1), Some((1, "a")));
assert_eq!(map.remove_entry(&1), None);

pub fn retain<F>(&mut self, f: F)where K: Ord, F: FnMut(&K, &mut V) -> bool,

仅保留谓词指定的元素。

换句话说，删除所有 f(&k, &mut v) 返回 false 的 (k, v) 对。 元素按升序键顺序访问。

Examples

use std::collections::BTreeMap;

let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x*10)).collect();
// 仅保留带有偶数键的元素。
map.retain(|&k, _| k % 2 == 0);
assert!(map.into_iter().eq(vec![(0, 0), (2, 20), (4, 40), (6, 60)]));

pub fn append(&mut self, other: &mut BTreeMap<K, V, A>)where K: Ord, A: Clone,

将所有元素从 other 移动到 self，使 other 为空。

如果 other 中的键已经存在于 self 中，则 self 中的相应值将被 other 中的相应值覆盖。

Examples

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c"); // Note: 密钥 (3) 也出现在 b.

let mut b = BTreeMap::new();
b.insert(3, "d"); // Note: 密钥 (3) 也出现在 a.
b.insert(4, "e");
b.insert(5, "f");

a.append(&mut b);

assert_eq!(a.len(), 5);
assert_eq!(b.len(), 0);

assert_eq!(a[&1], "a");
assert_eq!(a[&2], "b");
assert_eq!(a[&3], "d"); // Note: "c" 已被覆盖。
assert_eq!(a[&4], "e");
assert_eq!(a[&5], "f");

pub fn range<T, R>(&self, range: R) -> Range<'_, K, V> where T: Ord + ?Sized, K: Borrow<T> + Ord, R: RangeBounds<T>,

在 map 中的子元素范围上创建一个双端迭代器。 最简单的方法是使用范围语法 min..max，因此 range(min..max) 将产生从最小 (inclusive) 到最大 (exclusive) 的元素。 也可以将范围输入为 (Bound<T>, Bound<T>)，例如 range((Excluded(4), Included(10))) 将产生一个左排他的，范围从 4 到 10。

Panics

如果范围 start > end，就会出现 panics。 如果范围 start == end 和两个边界均为 Excluded，就会出现 panics。

Examples

基本用法：

use std::collections::BTreeMap;
use std::ops::Bound::Included;

let mut map = BTreeMap::new();
map.insert(3, "a");
map.insert(5, "b");
map.insert(8, "c");
for (&key, &value) in map.range((Included(&4), Included(&8))) {
    println!("{key}: {value}");
}
assert_eq!(Some((&5, &"b")), map.range(4..).next());

pub fn range_mut<T, R>(&mut self, range: R) -> RangeMut<'_, K, V> where T: Ord + ?Sized, K: Borrow<T> + Ord, R: RangeBounds<T>,

在 map 中的子元素范围上创建一个可变的双端迭代器。 最简单的方法是使用范围语法 min..max，因此 range(min..max) 将产生从最小 (inclusive) 到最大 (exclusive) 的元素。 也可以将范围输入为 (Bound<T>, Bound<T>)，例如 range((Excluded(4), Included(10))) 将产生一个左排他的，范围从 4 到 10。

Panics

如果范围 start > end，就会出现 panics。 如果范围 start == end 和两个边界均为 Excluded，就会出现 panics。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map: BTreeMap<&str, i32> =
    [("Alice", 0), ("Bob", 0), ("Carol", 0), ("Cheryl", 0)].into();
for (_, balance) in map.range_mut("B".."Cheryl") {
    *balance += 100;
}
for (name, balance) in &map {
    println!("{name} => {balance}");
}

pub fn entry(&mut self, key: K) -> Entry<'_, K, V, A>where K: Ord,

在 map 中获取给定键的对应项，以进行就地操作。

Examples

基本用法：

use std::collections::BTreeMap;

let mut count: BTreeMap<&str, usize> = BTreeMap::new();

// 计算 vec 中字母出现的次数
for x in ["a", "b", "a", "c", "a", "b"] {
    count.entry(x).and_modify(|curr| *curr += 1).or_insert(1);
}

assert_eq!(count["a"], 3);
assert_eq!(count["b"], 2);
assert_eq!(count["c"], 1);

pub fn split_off<Q>(&mut self, key: &Q) -> BTreeMap<K, V, A>where Q: Ord + ?Sized, K: Borrow<Q> + Ord, A: Clone,

在给定的键处将集合拆分为两个。 返回给定键之后的所有内容，包括键。

Examples

基本用法：

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");
a.insert(17, "d");
a.insert(41, "e");

let b = a.split_off(&3);

assert_eq!(a.len(), 2);
assert_eq!(b.len(), 3);

assert_eq!(a[&1], "a");
assert_eq!(a[&2], "b");

assert_eq!(b[&3], "c");
assert_eq!(b[&17], "d");
assert_eq!(b[&41], "e");

pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F, A> where K: Ord, F: FnMut(&K, &mut V) -> bool,

🔬This is a nightly-only experimental API. (btree_drain_filter #70530)

创建一个迭代器，该迭代器以升序顺序访问所有元素 (键值对)，并使用闭包确定是否应删除元素。 如果闭包返回 true，则将元素从 map 中移除并产生。 如果闭包返回 false 或 panics，则该元素保留在 map 中，并且不会产生。

迭代器还允许您更改闭包中每个元素的值，而不管您是选择保留还是删除它。

如果迭代器仅被部分消耗或根本没有消耗，则其余每个元素仍将受到闭包的影响，闭包可能会更改其值，并通过返回 true 来丢弃该元素。

如果在闭包中出现 panic，或者在丢弃元素时发生 panic，或者 DrainFilter 值泄漏，将有多少个元素受到该闭包的影响，这是不确定的。

Examples

将 map 分为偶数和奇数键，重新使用原始的 map：

#![feature(btree_drain_filter)]
use std::collections::BTreeMap;

let mut map: BTreeMap<i32, i32> = (0..8).map(|x| (x, x)).collect();
let evens: BTreeMap<_, _> = map.drain_filter(|k, _v| k % 2 == 0).collect();
let odds = map;
assert_eq!(evens.keys().copied().collect::<Vec<_>>(), [0, 2, 4, 6]);
assert_eq!(odds.keys().copied().collect::<Vec<_>>(), [1, 3, 5, 7]);

pub fn into_keys(self) -> IntoKeys<K, V, A>

创建一个消费的迭代器，按顺序访问所有键。 调用后不能使用 map。 迭代器元素类型为 K。

Examples

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(2, "b");
a.insert(1, "a");

let keys: Vec<i32> = a.into_keys().collect();
assert_eq!(keys, [1, 2]);

pub fn into_values(self) -> IntoValues<K, V, A>

创建一个消费迭代器，按键顺序访问所有值。 调用后不能使用 map。 迭代器元素类型为 V。

Examples

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "hello");
a.insert(2, "goodbye");

let values: Vec<&str> = a.into_values().collect();
assert_eq!(values, ["hello", "goodbye"]);

impl<K, V, A> BTreeMap<K, V, A>where A: Allocator + Clone,

pub fn iter(&self) -> Iter<'_, K, V>

获取对 map 的条目进行迭代的迭代器，按键排序。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(3, "c");
map.insert(2, "b");
map.insert(1, "a");

for (key, value) in map.iter() {
    println!("{key}: {value}");
}

let (first_key, first_value) = map.iter().next().unwrap();
assert_eq!((*first_key, *first_value), (1, "a"));

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

在 map 的条目上获取一个可变迭代器，按键排序。

Examples

基本用法：

use std::collections::BTreeMap;

let mut map = BTreeMap::from([
   ("a", 1),
   ("b", 2),
   ("c", 3),
]);

// 如果键不是 "a"，则将值加 10
for (key, value) in map.iter_mut() {
    if key != &"a" {
        *value += 10;
    }
}

pub fn keys(&self) -> Keys<'_, K, V>

以排序顺序在 map 的键上获取一个迭代器。

Examples

基本用法：

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(2, "b");
a.insert(1, "a");

let keys: Vec<_> = a.keys().cloned().collect();
assert_eq!(keys, [1, 2]);

pub fn values(&self) -> Values<'_, K, V>

按键顺序获取 map 值的迭代器。

Examples

基本用法：

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "hello");
a.insert(2, "goodbye");

let values: Vec<&str> = a.values().cloned().collect();
assert_eq!(values, ["hello", "goodbye"]);

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

按键顺序获取 map 值的可变迭代器。

Examples

基本用法：

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, String::from("hello"));
a.insert(2, String::from("goodbye"));

for value in a.values_mut() {
    value.push_str("!");
}

let values: Vec<String> = a.values().cloned().collect();
assert_eq!(values, [String::from("hello!"),
                    String::from("goodbye!")]);

pub fn len(&self) -> usize

返回 map 中的元素数。

Examples

基本用法：

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
assert_eq!(a.len(), 0);
a.insert(1, "a");
assert_eq!(a.len(), 1);

pub fn is_empty(&self) -> bool

如果 map 不包含任何元素，则返回 true。

Examples

基本用法：

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
assert!(a.is_empty());
a.insert(1, "a");
assert!(!a.is_empty());

pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>where K: Borrow<Q> + Ord, Q: Ord,

🔬This is a nightly-only experimental API. (btree_cursors #107540)

返回指向第一个高于给定边界的元素的 Cursor。

如果不存在这样的元素，则返回指向 “ghost” 非元素的游标。

传递 Bound::Unbounded 将返回指向 map 的第一个元素的游标。

Examples

基本用法：

#![feature(btree_cursors)]

use std::collections::BTreeMap;
use std::ops::Bound;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");
a.insert(4, "c");
let cursor = a.lower_bound(Bound::Excluded(&2));
assert_eq!(cursor.key(), Some(&3));

pub fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A>where K: Borrow<Q> + Ord, Q: Ord,

🔬This is a nightly-only experimental API. (btree_cursors #107540)

返回指向第一个高于给定边界的元素的 CursorMut。

如果不存在这样的元素，则返回指向 “ghost” 非元素的游标。

传递 Bound::Unbounded 将返回指向 map 的第一个元素的游标。

Examples

基本用法：

#![feature(btree_cursors)]

use std::collections::BTreeMap;
use std::ops::Bound;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");
a.insert(4, "c");
let cursor = a.lower_bound_mut(Bound::Excluded(&2));
assert_eq!(cursor.key(), Some(&3));

pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>where K: Borrow<Q> + Ord, Q: Ord,

🔬This is a nightly-only experimental API. (btree_cursors #107540)

返回指向低于给定界限的最后一个元素的 Cursor。

如果不存在这样的元素，则返回指向 “ghost” 非元素的游标。

传递 Bound::Unbounded 将返回指向 map 的最后一个元素的游标。

Examples

基本用法：

#![feature(btree_cursors)]

use std::collections::BTreeMap;
use std::ops::Bound;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");
a.insert(4, "c");
let cursor = a.upper_bound(Bound::Excluded(&3));
assert_eq!(cursor.key(), Some(&2));

pub fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A>where K: Borrow<Q> + Ord, Q: Ord,

🔬This is a nightly-only experimental API. (btree_cursors #107540)

返回指向低于给定界限的最后一个元素的 CursorMut。

如果不存在这样的元素，则返回指向 “ghost” 非元素的游标。

传递 Bound::Unbounded 将返回指向 map 的最后一个元素的游标。

Examples

基本用法：

#![feature(btree_cursors)]

use std::collections::BTreeMap;
use std::ops::Bound;

let mut a = BTreeMap::new();
a.insert(1, "a");
a.insert(2, "b");
a.insert(3, "c");
a.insert(4, "c");
let cursor = a.upper_bound_mut(Bound::Excluded(&3));
assert_eq!(cursor.key(), Some(&2));

Trait Implementations

impl<K, V, A> Clone for BTreeMap<K, V, A>where K: Clone, V: Clone, A: Allocator + Clone,

fn clone(&self) -> BTreeMap<K, V, A>

返回值的副本。

fn clone_from(&mut self, source: &Self)

从 source 执行复制分配。

impl<K, V, A> Debug for BTreeMap<K, V, A>where K: Debug, V: Debug, A: Allocator + Clone,

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

使用给定的格式化程序格式化该值。

impl<K, V> Default for BTreeMap<K, V, Global>

fn default() -> BTreeMap<K, V, Global>

创建一个空的 BTreeMap。

impl<K, V, A> Drop for BTreeMap<K, V, A>where A: Allocator + Clone,

fn drop(&mut self)

执行此类型的析构函数。

impl<'a, K, V, A> Extend<(&'a K, &'a V)> for BTreeMap<K, V, A>where K: Ord + Copy, V: Copy, A: Allocator + Clone,

fn extend<I>(&mut self, iter: I)where I: IntoIterator<Item = (&'a K, &'a V)>,

使用迭代器的内容扩展集合。

fn extend_one(&mut self, _: (&'a K, &'a V))

🔬This is a nightly-only experimental API. (extend_one #72631)

用一个元素扩展一个集合。

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)

在集合中为给定数量的附加元素保留容量。

impl<K, V, A> Extend<(K, V)> for BTreeMap<K, V, A>where K: Ord, A: Allocator + Clone,

fn extend<T>(&mut self, iter: T)where T: IntoIterator<Item = (K, V)>,

使用迭代器的内容扩展集合。

fn extend_one(&mut self, _: (K, V))

🔬This is a nightly-only experimental API. (extend_one #72631)

用一个元素扩展一个集合。

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)

在集合中为给定数量的附加元素保留容量。

impl<K, V, const N: usize> From<[(K, V); N]> for BTreeMap<K, V, Global>where K: Ord,

fn from(arr: [(K, V); N]) -> BTreeMap<K, V, Global>

将 [(K, V); N] 转换为 BTreeMap<(K, V)>。

use std::collections::BTreeMap;

let map1 = BTreeMap::from([(1, 2), (3, 4)]);
let map2: BTreeMap<_, _> = [(1, 2), (3, 4)].into();
assert_eq!(map1, map2);

impl<K, V> FromIterator<(K, V)> for BTreeMap<K, V, Global>where K: Ord,

fn from_iter<T>(iter: T) -> BTreeMap<K, V, Global>where T: IntoIterator<Item = (K, V)>,

从迭代器创建一个值。

impl<K, V, A> Hash for BTreeMap<K, V, A>where K: Hash, V: Hash, A: Allocator + Clone,

fn hash<H>(&self, state: &mut H)where H: Hasher,

将该值输入给定的 Hasher。

fn hash_slice<H>(data: &[Self], state: &mut H)where H: Hasher, Self: Sized,

将这种类型的切片送入给定的 Hasher 中。

impl<K, Q, V, A> Index<&Q> for BTreeMap<K, V, A>where A: Allocator + Clone, K: Borrow<Q> + Ord, Q: Ord + ?Sized,

fn index(&self, key: &Q) -> &V

返回与提供的键对应的值的引用。

Panics

如果键不存在于 BTreeMap 中，就会出现 panic。

type Output = V

索引后返回的类型。

impl<'a, K, V, A> IntoIterator for &'a BTreeMap<K, V, A>where A: Allocator + Clone,

type Item = (&'a K, &'a V)

被迭代的元素的类型。

type IntoIter = Iter<'a, K, V>

我们将其变成哪种迭代器？

fn into_iter(self) -> Iter<'a, K, V>

从一个值创建一个迭代器。

impl<'a, K, V, A> IntoIterator for &'a mut BTreeMap<K, V, A>where A: Allocator + Clone,

type Item = (&'a K, &'a mut V)

被迭代的元素的类型。

type IntoIter = IterMut<'a, K, V>

我们将其变成哪种迭代器？

fn into_iter(self) -> IterMut<'a, K, V>

从一个值创建一个迭代器。

impl<K, V, A> IntoIterator for BTreeMap<K, V, A>where A: Allocator + Clone,

type Item = (K, V)

被迭代的元素的类型。

type IntoIter = IntoIter<K, V, A>

我们将其变成哪种迭代器？

fn into_iter(self) -> IntoIter<K, V, A>

从一个值创建一个迭代器。

impl<K, V, A> Ord for BTreeMap<K, V, A>where K: Ord, V: Ord, A: Allocator + Clone,

fn cmp(&self, other: &BTreeMap<K, V, A>) -> Ordering

此方法返回 self 和 other 之间的 Ordering。

fn max(self, other: Self) -> Selfwhere Self: Sized,

比较并返回两个值中的最大值。

fn min(self, other: Self) -> Selfwhere Self: Sized,

比较并返回两个值中的最小值。

fn clamp(self, min: Self, max: Self) -> Selfwhere Self: Sized + PartialOrd<Self>,

将值限制在某个时间间隔内。

impl<K, V, A> PartialEq<BTreeMap<K, V, A>> for BTreeMap<K, V, A>where K: PartialEq<K>, V: PartialEq<V>, A: Allocator + Clone,

fn eq(&self, other: &BTreeMap<K, V, A>) -> bool

此方法测试 self 和 other 值是否相等，并由 == 使用。

fn ne(&self, other: &Rhs) -> bool

此方法测试 !=。 默认实现几乎总是足够的，并且不应在没有充分理由的情况下被覆盖。

impl<K, V, A> PartialOrd<BTreeMap<K, V, A>> for BTreeMap<K, V, A>where K: PartialOrd<K>, V: PartialOrd<V>, A: Allocator + Clone,

fn partial_cmp(&self, other: &BTreeMap<K, V, A>) -> Option<Ordering>

如果存在，则此方法返回 self 和 other 值之间的顺序。

fn lt(&self, other: &Rhs) -> bool

此方法测试的内容少于 (对于 self 和 other)，并且由 < 操作员使用。

fn le(&self, other: &Rhs) -> bool

此方法测试小于或等于 (对于 self 和 other)，并且由 <= 运算符使用。

fn gt(&self, other: &Rhs) -> bool

此方法测试大于 (对于 self 和 other)，并且由 > 操作员使用。

fn ge(&self, other: &Rhs) -> bool

此方法测试是否大于或等于 (对于 self 和 other)，并且由 >= 运算符使用。

impl<K, V, A> Eq for BTreeMap<K, V, A>where K: Eq, V: Eq, A: Allocator + Clone,

impl<K, V, A> UnwindSafe for BTreeMap<K, V, A>where A: Allocator + Clone + UnwindSafe, K: RefUnwindSafe, V: RefUnwindSafe,