Struct std::collections::tree_set::TreeSetExperimental
[-]
[+]
[src]
pub struct TreeSet<T> {
// some fields omitted
}An implementation of the Set trait on top of the TreeMap container. The
only requirement is that the type of the elements contained ascribes to the
Ord trait.
Example
fn main() { use std::collections::TreeSet; let mut set = TreeSet::new(); set.insert(2i); set.insert(1i); set.insert(3i); for i in set.iter() { println!("{}", i) // prints 1, then 2, then 3 } set.remove(&3); if !set.contains(&3) { println!("set does not contain a 3 anymore"); } }use std::collections::TreeSet; let mut set = TreeSet::new(); set.insert(2i); set.insert(1i); set.insert(3i); for i in set.iter() { println!("{}", i) // prints 1, then 2, then 3 } set.remove(&3); if !set.contains(&3) { println!("set does not contain a 3 anymore"); }
The easiest way to use TreeSet with a custom type is to implement Ord.
We must also implement PartialEq, Eq and PartialOrd.
use std::collections::TreeSet; // We need `Eq` and `PartialEq`, these can be derived. #[deriving(Eq, PartialEq)] struct Troll<'a> { name: &'a str, level: uint, } // Implement `Ord` and sort trolls by level. impl<'a> Ord for Troll<'a> { fn cmp(&self, other: &Troll) -> Ordering { // If we swap `self` and `other`, we get descending ordering. self.level.cmp(&other.level) } } // `PartialOrd` needs to be implemented as well. impl<'a> PartialOrd for Troll<'a> { fn partial_cmp(&self, other: &Troll) -> Option<Ordering> { Some(self.cmp(other)) } } let mut trolls = TreeSet::new(); trolls.insert(Troll { name: "Orgarr", level: 2 }); trolls.insert(Troll { name: "Blargarr", level: 3 }); trolls.insert(Troll { name: "Kron the Smelly One", level: 4 }); trolls.insert(Troll { name: "Wartilda", level: 1 }); println!("You are facing {} trolls!", trolls.len()); // Print the trolls, ordered by level with smallest level first for x in trolls.iter() { println!("level {}: {}!", x.level, x.name); } // Kill all trolls trolls.clear(); assert_eq!(trolls.len(), 0);
Methods
impl<T: Ord> TreeSet<T>
fn new() -> TreeSet<T>
Creates an empty TreeSet.
Example
fn main() { use std::collections::TreeSet; let mut set: TreeSet<int> = TreeSet::new(); }use std::collections::TreeSet; let mut set: TreeSet<int> = TreeSet::new();
fn iter(&'a self) -> SetItems<'a, T>
Gets a lazy iterator over the values in the set, in ascending order.
Example
fn main() { use std::collections::TreeSet; let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect(); // Will print in ascending order. for x in set.iter() { println!("{}", x); } }use std::collections::TreeSet; let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect(); // Will print in ascending order. for x in set.iter() { println!("{}", x); }
fn rev_iter(&'a self) -> RevSetItems<'a, T>
Gets a lazy iterator over the values in the set, in descending order.
Example
fn main() { use std::collections::TreeSet; let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect(); // Will print in descending order. for x in set.rev_iter() { println!("{}", x); } }use std::collections::TreeSet; let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect(); // Will print in descending order. for x in set.rev_iter() { println!("{}", x); }
fn into_iter(self) -> Map<'static, (T, ()), T, MoveEntries<T, ()>>
Creates a consuming iterator, that is, one that moves each value out of the set in ascending order. The set cannot be used after calling this.
Example
fn main() { use std::collections::TreeSet; let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect(); // Not possible with a regular `.iter()` let v: Vec<int> = set.into_iter().collect(); assert_eq!(v, vec![1, 2, 3, 4, 5]); }use std::collections::TreeSet; let set: TreeSet<int> = [1i, 4, 3, 5, 2].iter().map(|&x| x).collect(); // Not possible with a regular `.iter()` let v: Vec<int> = set.into_iter().collect(); assert_eq!(v, vec![1, 2, 3, 4, 5]);
fn lower_bound(&'a self, v: &T) -> SetItems<'a, T>
Gets a lazy iterator pointing to the first value not less than v (greater or equal).
If all elements in the set are less than v empty iterator is returned.
Example
fn main() { use std::collections::TreeSet; let set: TreeSet<int> = [2, 4, 6, 8].iter().map(|&x| x).collect(); assert_eq!(set.lower_bound(&4).next(), Some(&4)); assert_eq!(set.lower_bound(&5).next(), Some(&6)); assert_eq!(set.lower_bound(&10).next(), None); }use std::collections::TreeSet; let set: TreeSet<int> = [2, 4, 6, 8].iter().map(|&x| x).collect(); assert_eq!(set.lower_bound(&4).next(), Some(&4)); assert_eq!(set.lower_bound(&5).next(), Some(&6)); assert_eq!(set.lower_bound(&10).next(), None);
fn upper_bound(&'a self, v: &T) -> SetItems<'a, T>
Gets a lazy iterator pointing to the first value greater than v.
If all elements in the set are less than or equal to v an
empty iterator is returned.
Example
fn main() { use std::collections::TreeSet; let set: TreeSet<int> = [2, 4, 6, 8].iter().map(|&x| x).collect(); assert_eq!(set.upper_bound(&4).next(), Some(&6)); assert_eq!(set.upper_bound(&5).next(), Some(&6)); assert_eq!(set.upper_bound(&10).next(), None); }use std::collections::TreeSet; let set: TreeSet<int> = [2, 4, 6, 8].iter().map(|&x| x).collect(); assert_eq!(set.upper_bound(&4).next(), Some(&6)); assert_eq!(set.upper_bound(&5).next(), Some(&6)); assert_eq!(set.upper_bound(&10).next(), None);
fn difference(&'a self, other: &'a TreeSet<T>) -> DifferenceItems<'a, T>
Visits the values representing the difference, in ascending order.
Example
fn main() { use std::collections::TreeSet; let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect(); // Can be seen as `a - b`. for x in a.difference(&b) { println!("{}", x); // Print 1 then 2 } let diff: TreeSet<int> = a.difference(&b).map(|&x| x).collect(); assert_eq!(diff, [1, 2].iter().map(|&x| x).collect()); // Note that difference is not symmetric, // and `b - a` means something else: let diff: TreeSet<int> = b.difference(&a).map(|&x| x).collect(); assert_eq!(diff, [4, 5].iter().map(|&x| x).collect()); }use std::collections::TreeSet; let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect(); // Can be seen as `a - b`. for x in a.difference(&b) { println!("{}", x); // Print 1 then 2 } let diff: TreeSet<int> = a.difference(&b).map(|&x| x).collect(); assert_eq!(diff, [1, 2].iter().map(|&x| x).collect()); // Note that difference is not symmetric, // and `b - a` means something else: let diff: TreeSet<int> = b.difference(&a).map(|&x| x).collect(); assert_eq!(diff, [4, 5].iter().map(|&x| x).collect());
fn symmetric_difference(&'a self, other: &'a TreeSet<T>) -> SymDifferenceItems<'a, T>
Visits the values representing the symmetric difference, in ascending order.
Example
fn main() { use std::collections::TreeSet; let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect(); // Print 1, 2, 4, 5 in ascending order. for x in a.symmetric_difference(&b) { println!("{}", x); } let diff1: TreeSet<int> = a.symmetric_difference(&b).map(|&x| x).collect(); let diff2: TreeSet<int> = b.symmetric_difference(&a).map(|&x| x).collect(); assert_eq!(diff1, diff2); assert_eq!(diff1, [1, 2, 4, 5].iter().map(|&x| x).collect()); }use std::collections::TreeSet; let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect(); // Print 1, 2, 4, 5 in ascending order. for x in a.symmetric_difference(&b) { println!("{}", x); } let diff1: TreeSet<int> = a.symmetric_difference(&b).map(|&x| x).collect(); let diff2: TreeSet<int> = b.symmetric_difference(&a).map(|&x| x).collect(); assert_eq!(diff1, diff2); assert_eq!(diff1, [1, 2, 4, 5].iter().map(|&x| x).collect());
fn intersection(&'a self, other: &'a TreeSet<T>) -> IntersectionItems<'a, T>
Visits the values representing the intersection, in ascending order.
Example
fn main() { use std::collections::TreeSet; let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); let b: TreeSet<int> = [2, 3, 4].iter().map(|&x| x).collect(); // Print 2, 3 in ascending order. for x in a.intersection(&b) { println!("{}", x); } let diff: TreeSet<int> = a.intersection(&b).map(|&x| x).collect(); assert_eq!(diff, [2, 3].iter().map(|&x| x).collect()); }use std::collections::TreeSet; let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); let b: TreeSet<int> = [2, 3, 4].iter().map(|&x| x).collect(); // Print 2, 3 in ascending order. for x in a.intersection(&b) { println!("{}", x); } let diff: TreeSet<int> = a.intersection(&b).map(|&x| x).collect(); assert_eq!(diff, [2, 3].iter().map(|&x| x).collect());
fn union(&'a self, other: &'a TreeSet<T>) -> UnionItems<'a, T>
Visits the values representing the union, in ascending order.
Example
fn main() { use std::collections::TreeSet; let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect(); // Print 1, 2, 3, 4, 5 in ascending order. for x in a.union(&b) { println!("{}", x); } let diff: TreeSet<int> = a.union(&b).map(|&x| x).collect(); assert_eq!(diff, [1, 2, 3, 4, 5].iter().map(|&x| x).collect()); }use std::collections::TreeSet; let a: TreeSet<int> = [1, 2, 3].iter().map(|&x| x).collect(); let b: TreeSet<int> = [3, 4, 5].iter().map(|&x| x).collect(); // Print 1, 2, 3, 4, 5 in ascending order. for x in a.union(&b) { println!("{}", x); } let diff: TreeSet<int> = a.union(&b).map(|&x| x).collect(); assert_eq!(diff, [1, 2, 3, 4, 5].iter().map(|&x| x).collect());
fn len(&self) -> uint
Return the number of elements in the set
Example
fn main() { use std::collections::TreeSet; let mut v = TreeSet::new(); assert_eq!(v.len(), 0); v.insert(1i); assert_eq!(v.len(), 1); }use std::collections::TreeSet; let mut v = TreeSet::new(); assert_eq!(v.len(), 0); v.insert(1i); assert_eq!(v.len(), 1);
fn is_empty(&self) -> bool
Returns true if the set contains no elements
Example
fn main() { use std::collections::TreeSet; let mut v = TreeSet::new(); assert!(v.is_empty()); v.insert(1i); assert!(!v.is_empty()); }use std::collections::TreeSet; let mut v = TreeSet::new(); assert!(v.is_empty()); v.insert(1i); assert!(!v.is_empty());
fn clear(&mut self)
Clears the set, removing all values.
Example
fn main() { use std::collections::TreeSet; let mut v = TreeSet::new(); v.insert(1i); v.clear(); assert!(v.is_empty()); }use std::collections::TreeSet; let mut v = TreeSet::new(); v.insert(1i); v.clear(); assert!(v.is_empty());
fn contains<Q: Ord + BorrowFrom<T>>(&self, value: &Q) -> bool
Returns true if the set contains a value.
The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
Example
fn main() { use std::collections::TreeSet; let set: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); assert_eq!(set.contains(&1), true); assert_eq!(set.contains(&4), false); }use std::collections::TreeSet; let set: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); assert_eq!(set.contains(&1), true); assert_eq!(set.contains(&4), false);
fn is_disjoint(&self, other: &TreeSet<T>) -> bool
Returns true if the set has no elements in common with other.
This is equivalent to checking for an empty intersection.
Example
fn main() { use std::collections::TreeSet; let a: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); let mut b: TreeSet<int> = TreeSet::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); }use std::collections::TreeSet; let a: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); let mut b: TreeSet<int> = TreeSet::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);
fn is_subset(&self, other: &TreeSet<T>) -> bool
Returns true if the set is a subset of another.
Example
fn main() { use std::collections::TreeSet; let sup: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); let mut set: TreeSet<int> = TreeSet::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); }use std::collections::TreeSet; let sup: TreeSet<int> = [1i, 2, 3].iter().map(|&x| x).collect(); let mut set: TreeSet<int> = TreeSet::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);
fn is_superset(&self, other: &TreeSet<T>) -> bool
Returns true if the set is a superset of another.
Example
fn main() { use std::collections::TreeSet; let sub: TreeSet<int> = [1i, 2].iter().map(|&x| x).collect(); let mut set: TreeSet<int> = TreeSet::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); }use std::collections::TreeSet; let sub: TreeSet<int> = [1i, 2].iter().map(|&x| x).collect(); let mut set: TreeSet<int> = TreeSet::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);
fn insert(&mut self, value: T) -> bool
Adds a value to the set. Returns true if the value was not already
present in the set.
Example
fn main() { use std::collections::TreeSet; let mut set = TreeSet::new(); assert_eq!(set.insert(2i), true); assert_eq!(set.insert(2i), false); assert_eq!(set.len(), 1); }use std::collections::TreeSet; let mut set = TreeSet::new(); assert_eq!(set.insert(2i), true); assert_eq!(set.insert(2i), false); assert_eq!(set.len(), 1);
fn remove<Q: Ord + BorrowFrom<T>>(&mut self, value: &Q) -> bool
Removes a value from the set. Returns true if the value was
present in the set.
The value may be any borrowed form of the set's value type, but the ordering on the borrowed form must match the ordering on the value type.
Example
fn main() { use std::collections::TreeSet; let mut set = TreeSet::new(); set.insert(2i); assert_eq!(set.remove(&2), true); assert_eq!(set.remove(&2), false); }use std::collections::TreeSet; let mut set = TreeSet::new(); set.insert(2i); assert_eq!(set.remove(&2), true); assert_eq!(set.remove(&2), false);