Struct scale_info::prelude::collections::BTreeSet

1.0.0 · source · [−]
pub struct BTreeSet<T> { /* private fields */ }
Expand description

An ordered set based on a B-Tree.

See BTreeMap’s documentation for a detailed discussion of this collection’s performance benefits and drawbacks.

It is a logic error for an item to be modified in such a way that the item’s ordering relative to any other item, as determined by the Ord trait, changes while it is in the set. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code. The behavior resulting from such a logic error is not specified (it could include panics, incorrect results, aborts, memory leaks, or non-termination) but will not be undefined behavior.

Iterators returned by BTreeSet::iter produce their items in order, and take worst-case logarithmic and amortized constant time per item returned.

Examples

use std::collections::BTreeSet;

// Type inference lets us omit an explicit type signature (which
// would be `BTreeSet<&str>` in this example).
let mut books = BTreeSet::new();

// Add some books.
books.insert("A Dance With Dragons");
books.insert("To Kill a Mockingbird");
books.insert("The Odyssey");
books.insert("The Great Gatsby");

// Check for a specific one.
if !books.contains("The Winds of Winter") {
    println!("We have {} books, but The Winds of Winter ain't one.",
             books.len());
}

// Remove a book.
books.remove("The Odyssey");

// Iterate over everything.
for book in &books {
    println!("{}", book);
}

A BTreeSet with a known list of items can be initialized from an array:

use std::collections::BTreeSet;

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

Implementations

Makes a new, empty BTreeSet.

Does not allocate anything on its own.

Examples
use std::collections::BTreeSet;

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

Constructs a double-ended iterator over a sub-range of elements in the set. The simplest way is to use the range syntax min..max, thus range(min..max) will yield elements from min (inclusive) to max (exclusive). The range may also be entered as (Bound<T>, Bound<T>), so for example range((Excluded(4), Included(10))) will yield a left-exclusive, right-inclusive range from 4 to 10.

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

Visits the elements representing the difference, i.e., the elements that are in self but not in other, in ascending order.

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

Visits the elements representing the symmetric difference, i.e., the elements that are in self or in other but not in both, in ascending order.

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

Visits the elements representing the intersection, i.e., the elements that are both in self and other, in ascending order.

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

Visits the elements representing the union, i.e., all the elements in self or other, without duplicates, in ascending order.

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

Clears the set, removing all elements.

Examples
use std::collections::BTreeSet;

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

Returns true if the set contains an element equal to the value.

The value may be any borrowed form of the set’s element type, but the ordering on the borrowed form must match the ordering on the element type.

Examples
use std::collections::BTreeSet;

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

Returns a reference to the element in the set, if any, that is equal to the value.

The value may be any borrowed form of the set’s element type, but the ordering on the borrowed form must match the ordering on the element type.

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

Returns true if self has no elements in common with other. This is equivalent to checking for an empty intersection.

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

Returns true if the set is a subset of another, i.e., other contains at least all the elements in 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);

Returns true if the set is a superset of another, i.e., self contains at least all the elements in 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);
🔬 This is a nightly-only experimental API. (map_first_last)

Returns a reference to the first element in the set, if any. This element is always the minimum of all elements in the set.

Examples

Basic usage:

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

Returns a reference to the last element in the set, if any. This element is always the maximum of all elements in the set.

Examples

Basic usage:

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

Removes the first element from the set and returns it, if any. The first element is always the minimum element in the set.

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

Removes the last element from the set and returns it, if any. The last element is always the maximum element in the set.

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

Adds a value to the set.

If the set did not have an equal element present, true is returned.

If the set did have an equal element present, false is returned, and the entry is not updated. See the module-level documentation for more.

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

Adds a value to the set, replacing the existing element, if any, that is equal to the value. Returns the replaced element.

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

If the set contains an element equal to the value, removes it from the set and drops it. Returns whether such an element was present.

The value may be any borrowed form of the set’s element type, but the ordering on the borrowed form must match the ordering on the element type.

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

Removes and returns the element in the set, if any, that is equal to the value.

The value may be any borrowed form of the set’s element type, but the ordering on the borrowed form must match the ordering on the element type.

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

Retains only the elements specified by the predicate.

In other words, remove all elements e such that f(&e) returns false. The elements are visited in ascending order.

Examples
use std::collections::BTreeSet;

let mut set = BTreeSet::from([1, 2, 3, 4, 5, 6]);
// Keep only the even numbers.
set.retain(|&k| k % 2 == 0);
assert!(set.iter().eq([2, 4, 6].iter()));

Moves all elements from other into Self, leaving other empty.

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

Splits the collection into two at the value. Returns a new collection with all elements greater than or equal to the value.

Examples

Basic usage:

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));
🔬 This is a nightly-only experimental API. (btree_drain_filter)

Creates an iterator that visits all elements in ascending order and uses a closure to determine if an element should be removed.

If the closure returns true, the element is removed from the set and yielded. If the closure returns false, or panics, the element remains in the set and will not be yielded.

If the iterator is only partially consumed or not consumed at all, each of the remaining elements is still subjected to the closure and removed and dropped if it returns true.

It is unspecified how many more elements will be subjected to the closure if a panic occurs in the closure, or if a panic occurs while dropping an element, or if the DrainFilter itself is leaked.

Examples

Splitting a set into even and odd values, reusing the original set:

#![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]);

Gets an iterator that visits the elements in the BTreeSet in ascending order.

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

Values returned by the iterator are returned in ascending order:

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

Returns the number of elements in the set.

Examples
use std::collections::BTreeSet;

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

Returns true if the set contains no elements.

Examples
use std::collections::BTreeSet;

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

Trait Implementations

Returns the intersection of self and rhs as a new 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;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [2, 3]);

The resulting type after applying the & operator.

Returns the union of self and rhs as a new 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;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [1, 2, 3, 4, 5]);

The resulting type after applying the | operator.

Returns the symmetric difference of self and rhs as a new 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;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [1, 4]);

The resulting type after applying the ^ operator.

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

Formats the value using the given formatter. Read more

Attempt to deserialise the value from input.

Attempt to skip the encoded value from input. Read more

Returns the fixed encoded size of the type. Read more

Return the number of elements in self_encoded.

Creates an empty BTreeSet.

Deserialize this value from the given Serde deserializer. Read more

If possible give a hint of expected size of the encoding. Read more

Convert self to a slice and append it to the destination.

Convert self to an owned vector.

Convert self to a slice and then invoke the given closure with it.

Calculates the encoded size. Read more

Extends a collection with the contents of an iterator. Read more

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

Extends a collection with exactly one element.

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

Reserves capacity in a collection for the given number of additional elements. Read more

Extends a collection with the contents of an iterator. Read more

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

Extends a collection with exactly one element.

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

Reserves capacity in a collection for the given number of additional elements. Read more

use std::collections::BTreeSet;

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

Creates a value from an iterator. Read more

Feeds this value into the given Hasher. Read more

Feeds a slice of this type into the given Hasher. Read more

The type of the deserializer being converted into.

Convert this value into a deserializer.

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more

Gets an iterator for moving out the BTreeSet’s contents.

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

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

This method returns an Ordering between self and other. Read more

Compares and returns the maximum of two values. Read more

Compares and returns the minimum of two values. Read more

Restrict a value to a certain interval. Read more

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

This method returns an ordering between self and other values if one exists. Read more

This method tests less than (for self and other) and is used by the < operator. Read more

This method tests less than or equal to (for self and other) and is used by the <= operator. Read more

This method tests greater than (for self and other) and is used by the > operator. Read more

This method tests greater than or equal to (for self and other) and is used by the >= operator. Read more

Serialize this value into the given Serde serializer. Read more

Returns the difference of self and rhs as a new 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;
let result_vec: Vec<_> = result.into_iter().collect();
assert_eq!(result_vec, [1, 2]);

The resulting type after applying the - operator.

The type identifying for which type info is provided. Read more

Returns the static type identifier for Self.

Auto Trait Implementations

Blanket Implementations

Gets the TypeId of self. Read more

Immutably borrows from an owned value. Read more

Mutably borrows from an owned value. Read more

Converts self into T using Into<T>. Read more

Converts self into a target type. Read more

Decode Self and consume all of the given input data. Read more

Decode Self and consume all of the given input data. Read more

Decode Self and advance input by the number of bytes consumed. Read more

Decode Self with the given maximum recursion depth. Read more

Causes self to use its Binary implementation when Debug-formatted.

Causes self to use its Display implementation when Debug-formatted. Read more

Causes self to use its LowerExp implementation when Debug-formatted. Read more

Causes self to use its LowerHex implementation when Debug-formatted. Read more

Causes self to use its Octal implementation when Debug-formatted.

Causes self to use its Pointer implementation when Debug-formatted. Read more

Causes self to use its UpperExp implementation when Debug-formatted. Read more

Causes self to use its UpperHex implementation when Debug-formatted. Read more

Performs the conversion.

Performs the conversion.

Append encoding of value to Self.

Return an encoding of Self prepended by given slice.

Pipes by value. This is generally the method you want to use. Read more

Borrows self and passes that borrow into the pipe function. Read more

Mutably borrows self and passes that borrow into the pipe function. Read more

Borrows self, then passes self.borrow() into the pipe function. Read more

Mutably borrows self, then passes self.borrow_mut() into the pipe function. Read more

Borrows self, then passes self.as_ref() into the pipe function.

Mutably borrows self, then passes self.as_mut() into the pipe function. Read more

Borrows self, then passes self.deref() into the pipe function.

Mutably borrows self, then passes self.deref_mut() into the pipe function. Read more

Pipes a value into a function that cannot ordinarily be called in suffix position. Read more

Pipes a trait borrow into a function that cannot normally be called in suffix position. Read more

Pipes a trait mutable borrow into a function that cannot normally be called in suffix position. Read more

Pipes a trait borrow into a function that cannot normally be called in suffix position. Read more

Pipes a trait mutable borrow into a function that cannot normally be called in suffix position. Read more

Pipes a dereference into a function that cannot normally be called in suffix position. Read more

Pipes a mutable dereference into a function that cannot normally be called in suffix position. Read more

Pipes a reference into a function that cannot ordinarily be called in suffix position. Read more

Pipes a mutable reference into a function that cannot ordinarily be called in suffix position. Read more

Immutable access to a value. Read more

Mutable access to a value. Read more

Immutable access to the Borrow<B> of a value. Read more

Mutable access to the BorrowMut<B> of a value. Read more

Immutable access to the AsRef<R> view of a value. Read more

Mutable access to the AsMut<R> view of a value. Read more

Immutable access to the Deref::Target of a value. Read more

Mutable access to the Deref::Target of a value. Read more

Calls .tap() only in debug builds, and is erased in release builds.

Calls .tap_mut() only in debug builds, and is erased in release builds. Read more

Calls .tap_borrow() only in debug builds, and is erased in release builds. Read more

Calls .tap_borrow_mut() only in debug builds, and is erased in release builds. Read more

Calls .tap_ref() only in debug builds, and is erased in release builds. Read more

Calls .tap_ref_mut() only in debug builds, and is erased in release builds. Read more

Calls .tap_deref() only in debug builds, and is erased in release builds. Read more

Calls .tap_deref_mut() only in debug builds, and is erased in release builds. Read more

Provides immutable access for inspection. Read more

Calls tap in debug builds, and does nothing in release builds.

Provides mutable access for modification. Read more

Calls tap_mut in debug builds, and does nothing in release builds.

Provides immutable access to the reference for inspection.

Calls tap_ref in debug builds, and does nothing in release builds.

Provides mutable access to the reference for modification.

Calls tap_ref_mut in debug builds, and does nothing in release builds.

Provides immutable access to the borrow for inspection. Read more

Calls tap_borrow in debug builds, and does nothing in release builds.

Provides mutable access to the borrow for modification.

Calls tap_borrow_mut in debug builds, and does nothing in release builds. Read more

Immutably dereferences self for inspection.

Calls tap_deref in debug builds, and does nothing in release builds.

Mutably dereferences self for modification.

Calls tap_deref_mut in debug builds, and does nothing in release builds. Read more

The resulting type after obtaining ownership.

Creates owned data from borrowed data, usually by cloning. Read more

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

Uses borrowed data to replace owned data, usually by cloning. Read more

Attempts to convert self into T using TryInto<T>. Read more

Attempts to convert self into a target type. Read more

The type returned in the event of a conversion error.

Performs the conversion.

The type returned in the event of a conversion error.

Performs the conversion.