Struct std::collections::BTreeSet

pub struct BTreeSet<T, A = Global>where
    A: Allocator + Clone,{ /* private fields */ }

基于 B 树的有序 set。

有关此集合的性能优缺点的详细讨论，请参见 BTreeMap 文档。

以某种方式修改项目是一种逻辑错误，即该项目相对于任何其他项目的排序 (由 Ord trait 确定) 会在其位于集合中时发生变化。

通常只有通过 Cell，RefCell，二进制状态，I/O 或不安全代码才能实现此操作。 此类逻辑错误导致的行为未指定，但会封装到观察到逻辑错误的 BTreeSet 中，并且不会导致未定义的行为。 这可能包括 panics、不正确的结果、中止、内存泄漏和未中止。

BTreeSet::iter 返回的迭代器按顺序生成它们的项，并且每个返回的项目都采用最坏情况的对数和摊销常数时间。

Examples

use std::collections::BTreeSet;

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

// 添加一些书。
books.insert("A Dance With Dragons");
books.insert("To Kill a Mockingbird");
books.insert("The Odyssey");
books.insert("The Great Gatsby");

// 检查一个特定的。
if !books.contains("The Winds of Winter") {
    println!("We have {} books, but The Winds of Winter ain't one.",
             books.len());
}

// 删除一本书。
books.remove("The Odyssey");

// 遍历所有内容。
for book in &books {
    println!("{book}");
}

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

use std::collections::BTreeSet;

let set = BTreeSet::from([1, 2, 3]);

Implementations

impl<T> BTreeSet<T, Global>

pub const fn new() -> BTreeSet<T, Global>

制作一个新的空 BTreeSet。

不会自行分配任何内容。

Examples

use std::collections::BTreeSet;

let mut set: BTreeSet<i32> = BTreeSet::new();

impl<T, A> BTreeSet<T, A>where A: Allocator + Clone,

pub fn new_in(alloc: A) -> BTreeSet<T, A>

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

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

Examples

use std::collections::BTreeSet;
use std::alloc::Global;

let mut set: BTreeSet<i32> = BTreeSet::new_in(Global);

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

在集合中元素的子范围上创建一个双端迭代器。 最简单的方法是使用范围语法 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::BTreeSet;
use std::ops::Bound::Included;

let mut set = BTreeSet::new();
set.insert(3);
set.insert(5);
set.insert(8);
for &elem in set.range((Included(&4), Included(&8))) {
    println!("{elem}");
}
assert_eq!(Some(&5), set.range(4..).next());

pub fn difference<'a>( &'a self, other: &'a BTreeSet<T, A> ) -> Difference<'a, T, A> where T: Ord,

按升序访问表示差异的元素，即在 self 中但不在 other 中的元素。

Examples

use std::collections::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);

let mut b = BTreeSet::new();
b.insert(2);
b.insert(3);

let diff: Vec<_> = a.difference(&b).cloned().collect();
assert_eq!(diff, [1]);

pub fn symmetric_difference<'a>( &'a self, other: &'a BTreeSet<T, A> ) -> SymmetricDifference<'a, T> where T: Ord,

按升序访问表示对称差异的元素，即在 self 或 other 中，但不是两者都有。

Examples

use std::collections::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);

let mut b = BTreeSet::new();
b.insert(2);
b.insert(3);

let sym_diff: Vec<_> = a.symmetric_difference(&b).cloned().collect();
assert_eq!(sym_diff, [1, 3]);

pub fn intersection<'a>( &'a self, other: &'a BTreeSet<T, A> ) -> Intersection<'a, T, A> where T: Ord,

按升序访问表示交集的元素，即 self 和 other 中的元素。

Examples

use std::collections::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);

let mut b = BTreeSet::new();
b.insert(2);
b.insert(3);

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

pub fn union<'a>(&'a self, other: &'a BTreeSet<T, A>) -> Union<'a, T> where T: Ord,

按升序访问代表 union 的元素，即 self 或 other 中的所有元素，无重复。

Examples

use std::collections::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);

let mut b = BTreeSet::new();
b.insert(2);

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

pub fn clear(&mut self)where A: Clone,

清空 set，删除所有元素。

Examples

use std::collections::BTreeSet;

let mut v = BTreeSet::new();
v.insert(1);
v.clear();
assert!(v.is_empty());

pub fn contains<Q>(&self, value: &Q) -> boolwhere T: Borrow<Q> + Ord, Q: Ord + ?Sized,

如果集合包含等于该值的元素，则返回 true。

该值可以是集合元素类型的任何借用形式，但借用形式的顺序必须与元素类型的顺序相匹配。

Examples

use std::collections::BTreeSet;

let set = BTreeSet::from([1, 2, 3]);
assert_eq!(set.contains(&1), true);
assert_eq!(set.contains(&4), false);

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

返回对集合中元素的引用，如果有，则等于该值。

该值可以是集合元素类型的任何借用形式，但借用形式的顺序必须与元素类型的顺序相匹配。

Examples

use std::collections::BTreeSet;

let set = BTreeSet::from([1, 2, 3]);
assert_eq!(set.get(&2), Some(&2));
assert_eq!(set.get(&4), None);

pub fn is_disjoint(&self, other: &BTreeSet<T, A>) -> boolwhere T: Ord,

如果 self 与 other 没有共同的元素，则返回 true。 这等效于检查空的交点。

Examples

use std::collections::BTreeSet;

let a = BTreeSet::from([1, 2, 3]);
let mut b = BTreeSet::new();

assert_eq!(a.is_disjoint(&b), true);
b.insert(4);
assert_eq!(a.is_disjoint(&b), true);
b.insert(1);
assert_eq!(a.is_disjoint(&b), false);

pub fn is_subset(&self, other: &BTreeSet<T, A>) -> boolwhere T: Ord,

如果集合是另一个集合的子集，则返回 true，即 other 至少包含 self 中的所有元素。

Examples

use std::collections::BTreeSet;

let sup = BTreeSet::from([1, 2, 3]);
let mut set = BTreeSet::new();

assert_eq!(set.is_subset(&sup), true);
set.insert(2);
assert_eq!(set.is_subset(&sup), true);
set.insert(4);
assert_eq!(set.is_subset(&sup), false);

pub fn is_superset(&self, other: &BTreeSet<T, A>) -> boolwhere T: Ord,

如果该集合是另一个集合的超集，则返回 true，即 self 至少包含 other 中的所有元素。

Examples

use std::collections::BTreeSet;

let sub = BTreeSet::from([1, 2]);
let mut set = BTreeSet::new();

assert_eq!(set.is_superset(&sub), false);

set.insert(0);
set.insert(1);
assert_eq!(set.is_superset(&sub), false);

set.insert(2);
assert_eq!(set.is_superset(&sub), true);

pub fn first(&self) -> Option<&T>where T: Ord,

返回对集合中第一个元素的引用 (如果有)。 该元素始终是集合中所有元素的最小值。

Examples

基本用法：

use std::collections::BTreeSet;

let mut set = BTreeSet::new();
assert_eq!(set.first(), None);
set.insert(1);
assert_eq!(set.first(), Some(&1));
set.insert(2);
assert_eq!(set.first(), Some(&1));

pub fn last(&self) -> Option<&T>where T: Ord,

返回对集合中最后一个元素的引用 (如果有)。 此元素始终是集合中所有元素的最大值。

Examples

基本用法：

use std::collections::BTreeSet;

let mut set = BTreeSet::new();
assert_eq!(set.last(), None);
set.insert(1);
assert_eq!(set.last(), Some(&1));
set.insert(2);
assert_eq!(set.last(), Some(&2));

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

从集合中移除第一个元素并返回它 (如果有)。 第一个元素始终是集合中的最小元素。

Examples

use std::collections::BTreeSet;

let mut set = BTreeSet::new();

set.insert(1);
while let Some(n) = set.pop_first() {
    assert_eq!(n, 1);
}
assert!(set.is_empty());

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

从集合中移除最后一个元素并返回它 (如果有)。 最后一个元素始终是集合中的最大元素。

Examples

use std::collections::BTreeSet;

let mut set = BTreeSet::new();

set.insert(1);
while let Some(n) = set.pop_last() {
    assert_eq!(n, 1);
}
assert!(set.is_empty());

pub fn insert(&mut self, value: T) -> boolwhere T: Ord,

向集合中添加一个值。

返回值是否是新插入的。那就是:

• 如果该集合以前不包含相等的值，则返回 true。
• 如果集合已经包含相等的值，则返回 false，并且不更新条目。

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

Examples

use std::collections::BTreeSet;

let mut set = BTreeSet::new();

assert_eq!(set.insert(2), true);
assert_eq!(set.insert(2), false);
assert_eq!(set.len(), 1);

pub fn replace(&mut self, value: T) -> Option<T>where T: Ord,

向集合中添加一个值，替换与该值相等的现有元素 (如果有)。 返回被替换的元素。

Examples

use std::collections::BTreeSet;

let mut set = BTreeSet::new();
set.insert(Vec::<i32>::new());

assert_eq!(set.get(&[][..]).unwrap().capacity(), 0);
set.replace(Vec::with_capacity(10));
assert_eq!(set.get(&[][..]).unwrap().capacity(), 10);

pub fn remove<Q>(&mut self, value: &Q) -> boolwhere T: Borrow<Q> + Ord, Q: Ord + ?Sized,

如果该集合包含等于该值的元素，则将其从集合中删除并丢弃它。返回是否存在这样的元素。

该值可以是集合元素类型的任何借用形式，但借用形式的顺序必须与元素类型的顺序相匹配。

Examples

use std::collections::BTreeSet;

let mut set = BTreeSet::new();

set.insert(2);
assert_eq!(set.remove(&2), true);
assert_eq!(set.remove(&2), false);

pub fn take<Q>(&mut self, value: &Q) -> Option<T>where T: Borrow<Q> + Ord, Q: Ord + ?Sized,

移除并返回集合中与该值相等的元素 (如果有)。

该值可以是集合元素类型的任何借用形式，但借用形式的顺序必须与元素类型的顺序相匹配。

Examples

use std::collections::BTreeSet;

let mut set = BTreeSet::from([1, 2, 3]);
assert_eq!(set.take(&2), Some(2));
assert_eq!(set.take(&2), None);

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

仅保留谓词指定的元素。

换句话说，删除所有 f(&e) 返回 false 的 e 元素。 元素按升序访问。

Examples

use std::collections::BTreeSet;

let mut set = BTreeSet::from([1, 2, 3, 4, 5, 6]);
// 仅保留偶数。
set.retain(|&k| k % 2 == 0);
assert!(set.iter().eq([2, 4, 6].iter()));

pub fn append(&mut self, other: &mut BTreeSet<T, A>)where T: Ord, A: Clone,

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

Examples

use std::collections::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);
a.insert(3);

let mut b = BTreeSet::new();
b.insert(3);
b.insert(4);
b.insert(5);

a.append(&mut b);

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

assert!(a.contains(&1));
assert!(a.contains(&2));
assert!(a.contains(&3));
assert!(a.contains(&4));
assert!(a.contains(&5));

pub fn split_off<Q>(&mut self, value: &Q) -> BTreeSet<T, A>where Q: Ord + ?Sized, T: Borrow<Q> + Ord, A: Clone,

按值将集合拆分为两个。 返回一个新集合，其中所有元素都大于或等于该值。

Examples

基本用法：

use std::collections::BTreeSet;

let mut a = BTreeSet::new();
a.insert(1);
a.insert(2);
a.insert(3);
a.insert(17);
a.insert(41);

let b = a.split_off(&3);

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

assert!(a.contains(&1));
assert!(a.contains(&2));

assert!(b.contains(&3));
assert!(b.contains(&17));
assert!(b.contains(&41));

pub fn drain_filter<'a, F>(&'a mut self, pred: F) -> DrainFilter<'a, T, F, A> where T: Ord, F: 'a + FnMut(&T) -> bool,

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

创建一个按升序访问所有元素的迭代器，并使用闭包来确定是否应删除元素。

如果闭包返回 true，则该元素将从集合中移除并产生。如果闭包返回 false 或 panics，则该元素保留在集合中，并且不会被产生。

如果迭代器只被部分消耗或者根本没有被消耗，剩余的每个元素仍然会被闭包处理，如果返回 true, 就会被移除和丢弃。

如果在闭包中出现 panic，或者如果在丢弃一个元素时出现 panic，或者如果 DrainFilter 本身被泄露，则未指定多少个元素会受到闭包的影响。

Examples

将一个集合分为偶数和奇数值，重新使用原始集合：

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

let mut set: BTreeSet<i32> = (0..8).collect();
let evens: BTreeSet<_> = set.drain_filter(|v| v % 2 == 0).collect();
let odds = set;
assert_eq!(evens.into_iter().collect::<Vec<_>>(), vec![0, 2, 4, 6]);
assert_eq!(odds.into_iter().collect::<Vec<_>>(), vec![1, 3, 5, 7]);

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

获取按升序访问 BTreeSet 中元素的迭代器。

Examples

use std::collections::BTreeSet;

let set = BTreeSet::from([1, 2, 3]);
let mut set_iter = set.iter();
assert_eq!(set_iter.next(), Some(&1));
assert_eq!(set_iter.next(), Some(&2));
assert_eq!(set_iter.next(), Some(&3));
assert_eq!(set_iter.next(), None);

迭代器返回的值以升序返回：

use std::collections::BTreeSet;

let set = BTreeSet::from([3, 1, 2]);
let mut set_iter = set.iter();
assert_eq!(set_iter.next(), Some(&1));
assert_eq!(set_iter.next(), Some(&2));
assert_eq!(set_iter.next(), Some(&3));
assert_eq!(set_iter.next(), None);

pub fn len(&self) -> usize

返回集合中的元素数。

Examples

use std::collections::BTreeSet;

let mut v = BTreeSet::new();
assert_eq!(v.len(), 0);
v.insert(1);
assert_eq!(v.len(), 1);

pub fn is_empty(&self) -> bool

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

Examples

use std::collections::BTreeSet;

let mut v = BTreeSet::new();
assert!(v.is_empty());
v.insert(1);
assert!(!v.is_empty());

Trait Implementations

impl<T, A> BitAnd<&BTreeSet<T, A>> for &BTreeSet<T, A>where T: Ord + Clone, A: Allocator + Clone,

fn bitand(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A>

将 self 和 rhs 的交集返回为新的 BTreeSet<T>。

Examples

use std::collections::BTreeSet;

let a = BTreeSet::from([1, 2, 3]);
let b = BTreeSet::from([2, 3, 4]);

let result = &a & &b;
assert_eq!(result, BTreeSet::from([2, 3]));

type Output = BTreeSet<T, A>

应用 & 运算符后的结果类型。

impl<T, A> BitOr<&BTreeSet<T, A>> for &BTreeSet<T, A>where T: Ord + Clone, A: Allocator + Clone,

fn bitor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A>

返回 self 和 rhs 的并集作为新的 BTreeSet<T>。

Examples

use std::collections::BTreeSet;

let a = BTreeSet::from([1, 2, 3]);
let b = BTreeSet::from([3, 4, 5]);

let result = &a | &b;
assert_eq!(result, BTreeSet::from([1, 2, 3, 4, 5]));

type Output = BTreeSet<T, A>

应用 | 运算符后的结果类型。

impl<T, A> BitXor<&BTreeSet<T, A>> for &BTreeSet<T, A>where T: Ord + Clone, A: Allocator + Clone,

fn bitxor(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A>

返回 self 和 rhs 的对称差作为新的 BTreeSet<T>。

Examples

use std::collections::BTreeSet;

let a = BTreeSet::from([1, 2, 3]);
let b = BTreeSet::from([2, 3, 4]);

let result = &a ^ &b;
assert_eq!(result, BTreeSet::from([1, 4]));

type Output = BTreeSet<T, A>

应用 ^ 运算符后的结果类型。

impl<T, A> Clone for BTreeSet<T, A>where T: Clone, A: Allocator + Clone,

fn clone(&self) -> BTreeSet<T, A>

返回值的副本。

fn clone_from(&mut self, other: &BTreeSet<T, A>)

从 source 执行复制分配。

impl<T, A> Debug for BTreeSet<T, A>where T: Debug, A: Allocator + Clone,

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

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

impl<T> Default for BTreeSet<T, Global>

fn default() -> BTreeSet<T, Global>

创建一个空的 BTreeSet。

impl<'a, T, A> Extend<&'a T> for BTreeSet<T, A>where T: 'a + Ord + Copy, A: Allocator + Clone,

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

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

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

🔬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<T, A> Extend<T> for BTreeSet<T, A>where T: Ord, A: Allocator + Clone,

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

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

fn extend_one(&mut self, elem: T)

🔬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<T, const N: usize> From<[T; N]> for BTreeSet<T, Global>where T: Ord,

fn from(arr: [T; N]) -> BTreeSet<T, Global>

将 [T; N] 转换为 BTreeSet<T>。

use std::collections::BTreeSet;

let set1 = BTreeSet::from([1, 2, 3, 4]);
let set2: BTreeSet<_> = [1, 2, 3, 4].into();
assert_eq!(set1, set2);

impl<T> FromIterator<T> for BTreeSet<T, Global>where T: Ord,

fn from_iter<I>(iter: I) -> BTreeSet<T, Global>where I: IntoIterator<Item = T>,

从迭代器创建一个值。

impl<T, A> Hash for BTreeSet<T, A>where T: 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<'a, T, A> IntoIterator for &'a BTreeSet<T, A>where A: Allocator + Clone,

type Item = &'a T

被迭代的元素的类型。

type IntoIter = Iter<'a, T>

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

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

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

impl<T, A> IntoIterator for BTreeSet<T, A>where A: Allocator + Clone,

fn into_iter(self) -> IntoIter<T, A>

获取用于移出 BTreeSet 内容的迭代器。

Examples

use std::collections::BTreeSet;

let set = BTreeSet::from([1, 2, 3, 4]);

let v: Vec<_> = set.into_iter().collect();
assert_eq!(v, [1, 2, 3, 4]);

type Item = T

被迭代的元素的类型。

type IntoIter = IntoIter<T, A>

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

impl<T, A> Ord for BTreeSet<T, A>where T: Ord, A: Allocator + Clone,

fn cmp(&self, other: &BTreeSet<T, 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<T, A> PartialEq<BTreeSet<T, A>> for BTreeSet<T, A>where T: PartialEq<T>, A: Allocator + Clone,

fn eq(&self, other: &BTreeSet<T, A>) -> bool

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

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

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

impl<T, A> PartialOrd<BTreeSet<T, A>> for BTreeSet<T, A>where T: PartialOrd<T>, A: Allocator + Clone,

fn partial_cmp(&self, other: &BTreeSet<T, 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<T, A> Sub<&BTreeSet<T, A>> for &BTreeSet<T, A>where T: Ord + Clone, A: Allocator + Clone,

fn sub(self, rhs: &BTreeSet<T, A>) -> BTreeSet<T, A>

将 self 和 rhs 之差作为新的 BTreeSet<T> 返回。

Examples

use std::collections::BTreeSet;

let a = BTreeSet::from([1, 2, 3]);
let b = BTreeSet::from([3, 4, 5]);

let result = &a - &b;
assert_eq!(result, BTreeSet::from([1, 2]));

type Output = BTreeSet<T, A>

应用 - 运算符后的结果类型。

impl<T, A> Eq for BTreeSet<T, A>where T: Eq, A: Allocator + Clone,