Struct std::collections::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.

fn main() { 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); }
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::BTreeSet; let mut set = BTreeSet::new(); assert_eq!(set.insert(2i), true); assert_eq!(set.insert(2i), false); assert_eq!(set.len(), 1); }
use std::collections::BTreeSet;

let mut set = BTreeSet::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::BTreeSet; let mut set = BTreeSet::new(); set.insert(2i); assert_eq!(set.remove(&2), true); assert_eq!(set.remove(&2), false); }
use std::collections::BTreeSet;

let mut set = BTreeSet::new();

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

Trait Implementations

impl<T: PartialEq + Ord> PartialEq for TreeSet<T>

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

fn ne(&self, &TreeSet<T>) -> bool

impl<T: Eq + Ord> Eq for TreeSet<T>

fn assert_receiver_is_total_eq(&self)

impl<T: Ord> PartialOrd for TreeSet<T>

fn partial_cmp(&self, other: &TreeSet<T>) -> Option<Ordering>

fn lt(&self, &TreeSet<T>) -> bool

fn le(&self, &TreeSet<T>) -> bool

fn gt(&self, &TreeSet<T>) -> bool

fn ge(&self, &TreeSet<T>) -> bool

impl<T: Ord> Ord for TreeSet<T>

fn cmp(&self, other: &TreeSet<T>) -> Ordering

impl<T: Ord + Show> Show for TreeSet<T>

fn fmt(&self, f: &mut Formatter) -> Result<(), FormatError>

impl<T: Ord> Default for TreeSet<T>

fn default() -> TreeSet<T>

impl<T: Ord> FromIterator<T> for TreeSet<T>

fn from_iter<Iter: Iterator<T>>(iter: Iter) -> TreeSet<T>

impl<T: Ord> Extendable<T> for TreeSet<T>

fn extend<Iter: Iterator<T>>(&mut self, iter: Iter)

impl<S: Writer, T: Hash<S> + Ord> Hash<S> for TreeSet<T>

fn hash(&self, state: &mut S)

Derived Implementations

impl<T: Clone> Clone for TreeSet<T>

fn clone(&self) -> TreeSet<T>

fn clone_from(&mut self, &TreeSet<T>)