Struct alloc::collections::btree_map::BTreeMap1.0.0[−][src]

pub struct BTreeMap<K, V> { /* fields omitted */ }
Expand description

基于 B-Tree 的 map。

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

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

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

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

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

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!("{} is unreviewed.", movie)
    }
}

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

// 遍历一切。
for (movie, review) in &movie_reviews {
    println!("{}: \"{}\"", movie, review);
}
Run

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();
Run

Implementations

创建一个新的空 BTreeMap。

不自行分配任何内容。

Examples

基本用法:

use std::collections::BTreeMap;

let mut map = BTreeMap::new();

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

清除 map，删除所有元素。

Examples

基本用法:

use std::collections::BTreeMap;

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

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

键可以是 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);
Run

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

提供的键可以是 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);
Run
🔬 This is a nightly-only experimental API. (map_first_last #62924)

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

Examples

基本用法:

#![feature(map_first_last)]
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")));
Run

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

[src]
🔬 This is a nightly-only experimental API. (map_first_last #62924)

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

Examples

#![feature(map_first_last)]
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");
Run
🔬 This is a nightly-only experimental API. (map_first_last #62924)

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

Examples

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

#![feature(map_first_last)]
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());
Run
🔬 This is a nightly-only experimental API. (map_first_last #62924)

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

Examples

基本用法:

#![feature(map_first_last)]
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")));
Run

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

[src]
🔬 This is a nightly-only experimental API. (map_first_last #62924)

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

Examples

#![feature(map_first_last)]
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");
Run
🔬 This is a nightly-only experimental API. (map_first_last #62924)

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

Examples

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

#![feature(map_first_last)]
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());
Run

如果 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);
Run

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

键可以是 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");
Run

将键值对插入 map。

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

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

有关更多信息，请参见 module-level documentation。

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");
Run
🔬 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");
Run

从 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);
Run

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

1.45.0[src]

从 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);
Run

仅保留谓词指定的元素。

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

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)]));
Run

将所有元素从 other 移到 Self，将 other 留空。

Examples

use std::collections::BTreeMap;

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

let mut b = BTreeMap::new();
b.insert(3, "d");
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");
assert_eq!(a[&4], "e");
assert_eq!(a[&5], "f");
Run

在 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());
Run

在 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", "Bob", "Carol", "Cheryl"]
    .iter()
    .map(|&s| (s, 0))
    .collect();
for (_, balance) in map.range_mut("B".."Cheryl") {
    *balance += 100;
}
for (name, balance) in &map {
    println!("{} => {}", name, balance);
}
Run

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

Examples

基本用法:

use std::collections::BTreeMap;

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

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

assert_eq!(count["a"], 3);
Run

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

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");
Run
🔬 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<_>>(), vec![0, 2, 4, 6]);
assert_eq!(odds.keys().copied().collect::<Vec<_>>(), vec![1, 3, 5, 7]);
Run

创建一个消费的迭代器，按顺序访问所有键。 调用后不能使用 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]);
Run

创建一个消费迭代器，按键顺序访问所有值。 调用后不能使用 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"]);
Run

获取对 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"));
Run

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

Examples

基本用法:

use std::collections::BTreeMap;

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

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

以排序顺序在 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]);
Run

按键顺序获取 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"]);
Run

按键顺序获取 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!")]);
Run

返回 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);
Run

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

Examples

基本用法:

use std::collections::BTreeMap;

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

Trait Implementations

返回值的副本。 Read more

从 source 执行复制分配。 Read more

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

创建一个空的 BTreeMap。

执行此类型的析构函数。 Read more

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

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

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

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

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

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

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

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

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

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

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

将该值输入给定的 Hasher。 Read more

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

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

Panics

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

索引后返回的类型。

被迭代的元素的类型。

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

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

被迭代的元素的类型。

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

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

被迭代的元素的类型。

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

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

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

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

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

将值限制为一定的时间间隔。 Read more

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

此方法测试 !=。

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

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

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

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

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

Auto Trait Implementations

Blanket Implementations

获取 self 的 TypeId。 Read more

从拥有的值中一成不变地借用。 Read more

从拥有的值中借用。 Read more

执行转换。

执行转换。

获得所有权后的结果类型。

通常通过克隆从借用数据中创建拥有的数据。 Read more

🔬 This is a nightly-only experimental API. (toowned_clone_into #41263)

recently added

使用借来的数据来替换拥有的数据，通常是通过克隆。 Read more

发生转换错误时返回的类型。

执行转换。

发生转换错误时返回的类型。

执行转换。