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(&self, value: &T) -> bool
Returns true if the set contains a value.
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(&mut self, value: &T) -> bool
Removes a value from the set. Returns true if the value was
present in the set.
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);