Struct std::collections::BTreeMap 1.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
返回 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
删除并返回 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
返回 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
删除并返回 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。
如果 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
pub fn try_insert(
&mut self,
key: K,
value: V
) -> Result<&mut V, OccupiedError<'_, K, V>> where
K: Ord,
[src]
pub fn try_insert(
&mut self,
key: K,
value: V
) -> Result<&mut V, OccupiedError<'_, K, V>> where
K: Ord,
[src]尝试将键值对插入到 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
仅保留谓词指定的元素。
换句话说，删除所有对 (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
在给定的键处将集合拆分为两个。 返回给定键之后的所有内容，包括键。
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
pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F>ⓘNotable traits for DrainFilter<'_, K, V, F>impl<'_, K, V, F> Iterator for DrainFilter<'_, K, V, F> where
F: FnMut(&K, &mut V) -> bool, type Item = (K, V); where
F: FnMut(&K, &mut V) -> bool,
K: Ord,
[src]
pub fn drain_filter<F>(&mut self, pred: F) -> DrainFilter<'_, K, V, F>ⓘNotable traits for DrainFilter<'_, K, V, F>impl<'_, K, V, F> Iterator for DrainFilter<'_, K, V, F> where
F: FnMut(&K, &mut V) -> bool, type Item = (K, V); where
F: FnMut(&K, &mut V) -> bool,
K: Ord,
[src]impl<'_, K, V, F> Iterator for DrainFilter<'_, K, V, F> where
F: FnMut(&K, &mut V) -> bool, type Item = (K, V);创建一个迭代器，该迭代器以升序顺序访问所有元素 (键值对)，并使用闭包确定是否应删除元素。
如果闭包返回 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
pub fn into_values(self) -> IntoValues<K, V>ⓘNotable traits for IntoValues<K, V>impl<K, V> Iterator for IntoValues<K, V> type Item = V;
1.54.0[src]
pub fn into_values(self) -> IntoValues<K, V>ⓘNotable traits for IntoValues<K, V>impl<K, V> Iterator for IntoValues<K, V> type Item = V;
1.54.0[src]impl<K, V> Iterator for IntoValues<K, V> type Item = 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"));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