Struct std::collections::bit_set::BitSet [−] [src]

pub struct BitSet {
    // some fields omitted
}

Unstable
: RFC 509

An implementation of a set using a bit vector as an underlying representation for holding unsigned numerical elements.

It should also be noted that the amount of storage necessary for holding a set of objects is proportional to the maximum of the objects when viewed as a usize.

Examples

#![feature(collections)] fn main() { use std::collections::{BitSet, BitVec}; // It's a regular set let mut s = BitSet::new(); s.insert(0); s.insert(3); s.insert(7); s.remove(&7); if !s.contains(&7) { println!("There is no 7"); } // Can initialize from a `BitVec` let other = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11010000])); s.union_with(&other); // Print 0, 1, 3 in some order for x in s.iter() { println!("{}", x); } // Can convert back to a `BitVec` let bv: BitVec = s.into_bit_vec(); assert!(bv[3]); }

use std::collections::{BitSet, BitVec};

// It's a regular set
let mut s = BitSet::new();
s.insert(0);
s.insert(3);
s.insert(7);

s.remove(&7);

if !s.contains(&7) {
    println!("There is no 7");
}

// Can initialize from a `BitVec`
let other = BitSet::from_bit_vec(BitVec::from_bytes(&[0b11010000]));

s.union_with(&other);

// Print 0, 1, 3 in some order
for x in s.iter() {
    println!("{}", x);
}

// Can convert back to a `BitVec`
let bv: BitVec = s.into_bit_vec();
assert!(bv[3]);

Methods

`impl BitSet`

`fn new() -> BitSet`

Creates a new empty BitSet.

Examples

#![feature(collections)] fn main() { use std::collections::BitSet; let mut s = BitSet::new(); }

use std::collections::BitSet;

let mut s = BitSet::new();

`fn with_capacity(nbits: usize) -> BitSet`

Creates a new BitSet with initially no contents, able to hold nbits elements without resizing.

Examples

#![feature(collections)] fn main() { use std::collections::BitSet; let mut s = BitSet::with_capacity(100); assert!(s.capacity() >= 100); }

use std::collections::BitSet;

let mut s = BitSet::with_capacity(100);
assert!(s.capacity() >= 100);

`fn from_bit_vec(bit_vec: BitVec) -> BitSet`

Unstable

Creates a new BitSet from the given bit vector.

Examples

#![feature(collections)] fn main() { use std::collections::{BitVec, BitSet}; let bv = BitVec::from_bytes(&[0b01100000]); let s = BitSet::from_bit_vec(bv); // Print 1, 2 in arbitrary order for x in s.iter() { println!("{}", x); } }

use std::collections::{BitVec, BitSet};

let bv = BitVec::from_bytes(&[0b01100000]);
let s = BitSet::from_bit_vec(bv);

// Print 1, 2 in arbitrary order
for x in s.iter() {
    println!("{}", x);
}

`fn capacity(&self) -> usize`

Returns the capacity in bits for this bit vector. Inserting any element less than this amount will not trigger a resizing.

Examples

#![feature(collections)] fn main() { use std::collections::BitSet; let mut s = BitSet::with_capacity(100); assert!(s.capacity() >= 100); }

use std::collections::BitSet;

let mut s = BitSet::with_capacity(100);
assert!(s.capacity() >= 100);

`fn reserve_len(&mut self, len: usize)`

Reserves capacity for the given BitSet to contain len distinct elements. In the case of BitSet this means reallocations will not occur as long as all inserted elements are less than len.

The collection may reserve more space to avoid frequent reallocations.

Examples

#![feature(collections)] fn main() { use std::collections::BitSet; let mut s = BitSet::new(); s.reserve_len(10); assert!(s.capacity() >= 10); }

use std::collections::BitSet;

let mut s = BitSet::new();
s.reserve_len(10);
assert!(s.capacity() >= 10);

`fn reserve_len_exact(&mut self, len: usize)`

Reserves the minimum capacity for the given BitSet to contain len distinct elements. In the case of BitSet this means reallocations will not occur as long as all inserted elements are less than len.

Note that the allocator may give the collection more space than it requests. Therefore capacity can not be relied upon to be precisely minimal. Prefer reserve_len if future insertions are expected.

Examples

#![feature(collections)] fn main() { use std::collections::BitSet; let mut s = BitSet::new(); s.reserve_len_exact(10); assert!(s.capacity() >= 10); }

use std::collections::BitSet;

let mut s = BitSet::new();
s.reserve_len_exact(10);
assert!(s.capacity() >= 10);

`fn into_bit_vec(self) -> BitVec`

Unstable

Consumes this set to return the underlying bit vector.

Examples

#![feature(collections)] fn main() { use std::collections::BitSet; let mut s = BitSet::new(); s.insert(0); s.insert(3); let bv = s.into_bit_vec(); assert!(bv[0]); assert!(bv[3]); }

use std::collections::BitSet;

let mut s = BitSet::new();
s.insert(0);
s.insert(3);

let bv = s.into_bit_vec();
assert!(bv[0]);
assert!(bv[3]);

`fn get_ref(&self) -> &BitVec`

Unstable

Returns a reference to the underlying bit vector.

Examples

#![feature(collections)] fn main() { use std::collections::BitSet; let mut s = BitSet::new(); s.insert(0); let bv = s.get_ref(); assert_eq!(bv[0], true); }

use std::collections::BitSet;

let mut s = BitSet::new();
s.insert(0);

let bv = s.get_ref();
assert_eq!(bv[0], true);

`fn shrink_to_fit(&mut self)`

Truncates the underlying vector to the least length required.

Examples

#![feature(collections)] fn main() { use std::collections::BitSet; let mut s = BitSet::new(); s.insert(32183231); s.remove(&32183231); // Internal storage will probably be bigger than necessary println!("old capacity: {}", s.capacity()); // Now should be smaller s.shrink_to_fit(); println!("new capacity: {}", s.capacity()); }

use std::collections::BitSet;

let mut s = BitSet::new();
s.insert(32183231);
s.remove(&32183231);

// Internal storage will probably be bigger than necessary
println!("old capacity: {}", s.capacity());

// Now should be smaller
s.shrink_to_fit();
println!("new capacity: {}", s.capacity());

`fn iter(&self) -> SetIter`

Iterator over each usize stored in the BitSet.

Examples

#![feature(collections)] fn main() { use std::collections::{BitVec, BitSet}; let s = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01001010])); // Print 1, 4, 6 in arbitrary order for x in s.iter() { println!("{}", x); } }

use std::collections::{BitVec, BitSet};

let s = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01001010]));

// Print 1, 4, 6 in arbitrary order
for x in s.iter() {
    println!("{}", x);
}

`fn union(&'a self, other: &'a BitSet) -> Union<'a>`

Iterator over each usize stored in self union other. See union_with for an efficient in-place version.

Examples

#![feature(collections)] fn main() { use std::collections::{BitVec, BitSet}; let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); // Print 0, 1, 2, 4 in arbitrary order for x in a.union(&b) { println!("{}", x); } }

use std::collections::{BitVec, BitSet};

let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));

// Print 0, 1, 2, 4 in arbitrary order
for x in a.union(&b) {
    println!("{}", x);
}

`fn intersection(&'a self, other: &'a BitSet) -> Intersection<'a>`

Iterator over each usize stored in self intersect other. See intersect_with for an efficient in-place version.

Examples

#![feature(collections)] fn main() { use std::collections::{BitVec, BitSet}; let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); // Print 2 for x in a.intersection(&b) { println!("{}", x); } }

use std::collections::{BitVec, BitSet};

let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));

// Print 2
for x in a.intersection(&b) {
    println!("{}", x);
}

`fn difference(&'a self, other: &'a BitSet) -> Difference<'a>`

Iterator over each usize stored in the self setminus other. See difference_with for an efficient in-place version.

Examples

#![feature(collections)] fn main() { use std::collections::{BitSet, BitVec}; let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); // Print 1, 4 in arbitrary order for x in a.difference(&b) { println!("{}", x); } // Note that difference is not symmetric, // and `b - a` means something else. // This prints 0 for x in b.difference(&a) { println!("{}", x); } }

use std::collections::{BitSet, BitVec};

let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));

// Print 1, 4 in arbitrary order
for x in a.difference(&b) {
    println!("{}", x);
}

// Note that difference is not symmetric,
// and `b - a` means something else.
// This prints 0
for x in b.difference(&a) {
    println!("{}", x);
}

`fn symmetric_difference(&'a self, other: &'a BitSet) -> SymmetricDifference<'a>`

Iterator over each usize stored in the symmetric difference of self and other. See symmetric_difference_with for an efficient in-place version.

Examples

#![feature(collections)] fn main() { use std::collections::{BitSet, BitVec}; let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000])); let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000])); // Print 0, 1, 4 in arbitrary order for x in a.symmetric_difference(&b) { println!("{}", x); } }

use std::collections::{BitSet, BitVec};

let a = BitSet::from_bit_vec(BitVec::from_bytes(&[0b01101000]));
let b = BitSet::from_bit_vec(BitVec::from_bytes(&[0b10100000]));

// Print 0, 1, 4 in arbitrary order
for x in a.symmetric_difference(&b) {
    println!("{}", x);
}

`fn union_with(&mut self, other: &BitSet)`

Unstable

Unions in-place with the specified other bit vector.

Examples

#![feature(collections)] fn main() { use std::collections::{BitSet, BitVec}; let a = 0b01101000; let b = 0b10100000; let res = 0b11101000; let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res])); a.union_with(&b); assert_eq!(a, res); }

use std::collections::{BitSet, BitVec};

let a   = 0b01101000;
let b   = 0b10100000;
let res = 0b11101000;

let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));

a.union_with(&b);
assert_eq!(a, res);

`fn intersect_with(&mut self, other: &BitSet)`

Unstable

Intersects in-place with the specified other bit vector.

Examples

#![feature(collections)] fn main() { use std::collections::{BitSet, BitVec}; let a = 0b01101000; let b = 0b10100000; let res = 0b00100000; let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res])); a.intersect_with(&b); assert_eq!(a, res); }

use std::collections::{BitSet, BitVec};

let a   = 0b01101000;
let b   = 0b10100000;
let res = 0b00100000;

let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));

a.intersect_with(&b);
assert_eq!(a, res);

`fn difference_with(&mut self, other: &BitSet)`

Unstable

Makes this bit vector the difference with the specified other bit vector in-place.

Examples

#![feature(collections)] fn main() { use std::collections::{BitSet, BitVec}; let a = 0b01101000; let b = 0b10100000; let a_b = 0b01001000; // a - b let b_a = 0b10000000; // b - a let mut bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); let bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); let bva_b = BitSet::from_bit_vec(BitVec::from_bytes(&[a_b])); let bvb_a = BitSet::from_bit_vec(BitVec::from_bytes(&[b_a])); bva.difference_with(&bvb); assert_eq!(bva, bva_b); let bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); let mut bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); bvb.difference_with(&bva); assert_eq!(bvb, bvb_a); }

use std::collections::{BitSet, BitVec};

let a   = 0b01101000;
let b   = 0b10100000;
let a_b = 0b01001000; // a - b
let b_a = 0b10000000; // b - a

let mut bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
let bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
let bva_b = BitSet::from_bit_vec(BitVec::from_bytes(&[a_b]));
let bvb_a = BitSet::from_bit_vec(BitVec::from_bytes(&[b_a]));

bva.difference_with(&bvb);
assert_eq!(bva, bva_b);

let bva = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
let mut bvb = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));

bvb.difference_with(&bva);
assert_eq!(bvb, bvb_a);

`fn symmetric_difference_with(&mut self, other: &BitSet)`

Unstable

Makes this bit vector the symmetric difference with the specified other bit vector in-place.

Examples

#![feature(collections)] fn main() { use std::collections::{BitSet, BitVec}; let a = 0b01101000; let b = 0b10100000; let res = 0b11001000; let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a])); let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b])); let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res])); a.symmetric_difference_with(&b); assert_eq!(a, res); }

use std::collections::{BitSet, BitVec};

let a   = 0b01101000;
let b   = 0b10100000;
let res = 0b11001000;

let mut a = BitSet::from_bit_vec(BitVec::from_bytes(&[a]));
let b = BitSet::from_bit_vec(BitVec::from_bytes(&[b]));
let res = BitSet::from_bit_vec(BitVec::from_bytes(&[res]));

a.symmetric_difference_with(&b);
assert_eq!(a, res);

`fn append(&mut self, other: &mut BitSet)`

Unstable
: recently added as part of collections reform 2

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

Examples

#![feature(collections, bit_set_append_split_off)] fn main() { use std::collections::{BitVec, BitSet}; let mut a = BitSet::new(); a.insert(2); a.insert(6); let mut b = BitSet::new(); b.insert(1); b.insert(3); b.insert(6); a.append(&mut b); assert_eq!(a.len(), 4); assert_eq!(b.len(), 0); assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01110010]))); }

use std::collections::{BitVec, BitSet};

let mut a = BitSet::new();
a.insert(2);
a.insert(6);

let mut b = BitSet::new();
b.insert(1);
b.insert(3);
b.insert(6);

a.append(&mut b);

assert_eq!(a.len(), 4);
assert_eq!(b.len(), 0);
assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01110010])));

`fn split_off(&mut self, at: usize) -> BitSet`

Unstable
: recently added as part of collections reform 2

Splits the BitSet into two at the given key including the key. Retains the first part in-place while returning the second part.

Examples

#![feature(collections, bit_set_append_split_off)] fn main() { use std::collections::{BitSet, BitVec}; let mut a = BitSet::new(); a.insert(2); a.insert(6); a.insert(1); a.insert(3); let b = a.split_off(3); assert_eq!(a.len(), 2); assert_eq!(b.len(), 2); assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100000]))); assert_eq!(b, BitSet::from_bit_vec(BitVec::from_bytes(&[0b00010010]))); }

use std::collections::{BitSet, BitVec};
let mut a = BitSet::new();
a.insert(2);
a.insert(6);
a.insert(1);
a.insert(3);

let b = a.split_off(3);

assert_eq!(a.len(), 2);
assert_eq!(b.len(), 2);
assert_eq!(a, BitSet::from_bit_vec(BitVec::from_bytes(&[0b01100000])));
assert_eq!(b, BitSet::from_bit_vec(BitVec::from_bytes(&[0b00010010])));

`fn len(&self) -> usize`

Returns the number of set bits in this set.

`fn is_empty(&self) -> bool`

Returns whether there are no bits set in this set

`fn clear(&mut self)`

Clears all bits in this set

`fn contains(&self, value: &usize) -> bool`

Returns true if this set contains the specified integer.

`fn is_disjoint(&self, other: &BitSet) -> bool`

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

`fn is_subset(&self, other: &BitSet) -> bool`

Returns true if the set is a subset of another.

`fn is_superset(&self, other: &BitSet) -> bool`

Returns true if the set is a superset of another.

`fn insert(&mut self, value: usize) -> bool`

Adds a value to the set. Returns true if the value was not already present in the set.

`fn remove(&mut self, value: &usize) -> bool`

Removes a value from the set. Returns true if the value was present in the set.

Struct std::collections::bit_set::BitSet [−] [src]

Methods

impl BitSet

fn new() -> BitSet

fn with_capacity(nbits: usize) -> BitSet

fn from_bit_vec(bit_vec: BitVec) -> BitSet

fn capacity(&self) -> usize

fn reserve_len(&mut self, len: usize)

fn reserve_len_exact(&mut self, len: usize)

fn into_bit_vec(self) -> BitVec

fn get_ref(&self) -> &BitVec

fn shrink_to_fit(&mut self)

fn iter(&self) -> SetIter

fn union(&'a self, other: &'a BitSet) -> Union<'a>

fn intersection(&'a self, other: &'a BitSet) -> Intersection<'a>

fn difference(&'a self, other: &'a BitSet) -> Difference<'a>

fn symmetric_difference(&'a self, other: &'a BitSet) -> SymmetricDifference<'a>

fn union_with(&mut self, other: &BitSet)

fn intersect_with(&mut self, other: &BitSet)

fn difference_with(&mut self, other: &BitSet)

fn symmetric_difference_with(&mut self, other: &BitSet)

fn append(&mut self, other: &mut BitSet)

fn split_off(&mut self, at: usize) -> BitSet

fn len(&self) -> usize

fn is_empty(&self) -> bool

fn clear(&mut self)

fn contains(&self, value: &usize) -> bool

fn is_disjoint(&self, other: &BitSet) -> bool

fn is_subset(&self, other: &BitSet) -> bool

fn is_superset(&self, other: &BitSet) -> bool

fn insert(&mut self, value: usize) -> bool

fn remove(&mut self, value: &usize) -> bool

Trait Implementations

impl Default for BitSet

fn default() -> BitSet

impl FromIterator<usize> for BitSet

fn from_iter<I>(iter: I) -> BitSet where I: IntoIterator<Item=usize>

impl Extend<usize> for BitSet

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

impl PartialOrd<BitSet> for BitSet

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

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

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

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

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

impl Ord for BitSet

fn cmp(&self, other: &BitSet) -> Ordering

impl PartialEq<BitSet> for BitSet

fn eq(&self, other: &BitSet) -> bool

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

impl Eq for BitSet

impl Debug for BitSet

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

impl Hash for BitSet

fn hash<H>(&self, state: &mut H) where H: Hasher

fn hash_slice<H>(data: &[Self], state: &mut H) where H: Hasher

impl<'a> IntoIterator for &'a BitSet

type Item = usize

type IntoIter = SetIter<'a>

fn into_iter(self) -> SetIter<'a>

Derived Implementations

impl Clone for BitSet

fn clone(&self) -> BitSet

fn clone_from(&mut self, source: &Self)

Keyboard shortcuts

Search tricks

`impl BitSet`

`fn new() -> BitSet`

`fn with_capacity(nbits: usize) -> BitSet`

`fn from_bit_vec(bit_vec: BitVec) -> BitSet`

`fn capacity(&self) -> usize`

`fn reserve_len(&mut self, len: usize)`

`fn reserve_len_exact(&mut self, len: usize)`

`fn into_bit_vec(self) -> BitVec`

`fn get_ref(&self) -> &BitVec`

`fn shrink_to_fit(&mut self)`

`fn iter(&self) -> SetIter`

`fn union(&'a self, other: &'a BitSet) -> Union<'a>`

`fn intersection(&'a self, other: &'a BitSet) -> Intersection<'a>`

`fn difference(&'a self, other: &'a BitSet) -> Difference<'a>`

`fn symmetric_difference(&'a self, other: &'a BitSet) -> SymmetricDifference<'a>`

`fn union_with(&mut self, other: &BitSet)`

`fn intersect_with(&mut self, other: &BitSet)`

`fn difference_with(&mut self, other: &BitSet)`

`fn symmetric_difference_with(&mut self, other: &BitSet)`

`fn append(&mut self, other: &mut BitSet)`

`fn split_off(&mut self, at: usize) -> BitSet`

`fn len(&self) -> usize`

`fn is_empty(&self) -> bool`

`fn clear(&mut self)`

`fn contains(&self, value: &usize) -> bool`

`fn is_disjoint(&self, other: &BitSet) -> bool`

`fn is_subset(&self, other: &BitSet) -> bool`

`fn is_superset(&self, other: &BitSet) -> bool`

`fn insert(&mut self, value: usize) -> bool`

`fn remove(&mut self, value: &usize) -> bool`

`impl Default for BitSet`

`fn default() -> BitSet`

`impl FromIterator<usize> for BitSet`

`fn from_iter<I>(iter: I) -> BitSet where I: IntoIterator<Item=usize>`

`impl Extend<usize> for BitSet`

`fn extend<I>(&mut self, iter: I) where I: IntoIterator<Item=usize>`

`impl PartialOrd<BitSet> for BitSet`

`fn partial_cmp(&self, other: &BitSet) -> Option<Ordering>`

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

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

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

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

`impl Ord for BitSet`

`fn cmp(&self, other: &BitSet) -> Ordering`

`impl PartialEq<BitSet> for BitSet`

`fn eq(&self, other: &BitSet) -> bool`

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

`impl Eq for BitSet`

`impl Debug for BitSet`

`fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error>`

`impl Hash for BitSet`

`fn hash<H>(&self, state: &mut H) where H: Hasher`

`fn hash_slice<H>(data: &[Self], state: &mut H) where H: Hasher`

`impl<'a> IntoIterator for &'a BitSet`

`type Item = usize`

`type IntoIter = SetIter<'a>`

`fn into_iter(self) -> SetIter<'a>`

`impl Clone for BitSet`

`fn clone(&self) -> BitSet`

`fn clone_from(&mut self, source: &Self)`