Struct vob::Vob [−][src]
pub struct Vob<T = usize> { /* fields omitted */ }
Expand description
A Vob is a “vector of bits”: a sequence of bits which exposes a Vec
-like interface. Whereas
Vec<bool>
requires 1 byte of storage per bit, Vob
requires only 1 bit of storage per bit.
For larger numbers of bits, Vobs can lead to a significant memory decrease and performance
increase.
Examples
The vob!
macro makes creating small Vob
s easy:
use vob::vob;
let mut v = vob![true, false, true];
assert_eq!(v[1], false);
Operations such as and
ing two Vob
s together are quick; one can also quickly identify which
bits are set:
use vob::Vob;
let mut v1 = Vob::from_elem(false, 256);
let mut v2 = Vob::from_elem(false, 256);
v1.set(67, true);
v2.set(67, true);
v1.set(188, true);
v1.and(&v2);
let num_bits_set = v1.iter_set_bits(..).count();
assert_eq!(num_bits_set, 1);
Storage backing type
Vob
s default to using usize
as a storage backing type. This is generally a substantial win
over using smaller storage types if you use functions such as
or()
. In such cases, usize
on a 64-bit machine is almost
exactly twice as fast as using u32
. If you only ever set and get individual bits, a smaller
data type might be marginally more effective: for such use cases u32
is around 1% faster than
usize
on a 64-bit machine. You can choose your own storage type with the
new_with_storage_type()
constructor. In
general we recommend using the default usize
backing storage unless you have rigorously
benchmarked your particular use case and are sure that a different storage type is superior.
Migrating from Vec<bool>
As far as possible, Vob
is intended to have a superset of Vec<bool>
’s interface, which
should make porting most code fairly simple. However, Vec<bool>
contains several functions
which are not yet implemented in Vob
: these are missing simply due to a lack of a current
use-case rather than because of any fundamental incompatibilities.
There is one missing feature which, currently, is impossible to implement: assignment to an
index. In other words one cannot currently express v[0] = true
for a Vob
v
. Until
IndexGet
/ IndexMove
and equivalents are
implemented in rustc
, this restriction appears to be inevitable. Note that referencing by
index works (though via a hack identical to that used in BitVec
): one can write
println!("{}", v[0])
for a Vob
v
, for example.
Migrating from BitVec
Vob
is directly inspired by the BitVec
, but aims to
provide an interface more closely aligned to Vec<bool>
Several functions in BitVec
have
different names in Vob
, but porting is in general fairly simple. The main semantic difference
is that Vob
s clear()
function empties the Vob
of contents
(i.e. sets its length to 0), whereas BitVec
’s function of the same name unsets all bits
(keeping the length unchanged). The same effect as BitVec
’s clear
can be achieved by using
Vob
’s set_all(false)
function.
Implementations
Constructs a new, empty Vob (with usize
backing storage, which is likely to be the best
choice in nearly all situations).
The Vob will not allocate until elements are pushed onto it.
Constructs a new, empty Vob (with usize
backing storage, which is likely to be the best
choice in nearly all situations) with the specified capacity.
The Vob will be able to hold at least capacity
elements without reallocating. If
capacity
is 0, the vector will not allocate.
Creates a Vob that holds len
elements, setting each element to value
.
Examples
use vob::Vob;
let v = Vob::from_elem(true, 2);
assert_eq!(v.len(), 2);
assert_eq!(v.get(0), Some(true));
Create a Vob from a u8
slice. The most significant bit of each byte comes first in the
resulting Vob.
Examples
use vob::{Vob, vob};
let v = Vob::from_bytes(&[0b10100000, 0b00010010]);
assert_eq!(v, vob![true, false, true, false, false, false, false, false,
false, false, false, true, false, false, true, false]);
Constructs a new, empty Vob (with a user-defined backing storage type) with the given capacity.
Examples
use vob::Vob;
let mut v = Vob::<u32>::new_with_storage_type(0);
v.push(true);
assert_eq!(v[0], true);
Returns the number of bits the Vob can hold without reallocating.
Examples
use vob::Vob;
assert_eq!(Vob::new().capacity(), 0);
assert!(Vob::with_capacity(1).capacity() >= 1);
Reserves capacity for at least additional
more bits to be inserted in the Vob. The Vob
may reserve more space to avoid frequent reallocations. After calling reserve
, capacity
will be greater than or equal to self.len() + additional
. Does nothing if capacity is
already sufficient.
Examples
use vob::Vob;
let mut v = Vob::new();
v.reserve(1);
assert!(v.capacity() >= 1);
Shrinks the capacity of the vector as much as possible.
It will drop down as close as possible to the length but the allocator may still inform the vector that there is space for a few more elements.
Shortens the Vob, keeping the first len
elements and dropping the rest.
If len is greater than the vector’s current length, this has no effect.
The drain method can emulate truncate, but causes the excess elements to be returned instead of dropped.
Note that this method has no effect on the allocated capacity of the vector.
Examples
use vob::vob;
let mut v = vob![true, false, true];
v.truncate(2);
assert_eq!(v, vob![true, false]);
Appends a bool to the back of the Vob.
Examples
use vob::Vob;
let mut v = Vob::new();
v.push(true);
v.push(false);
assert_eq!(v.get(0), Some(true));
assert_eq!(v.get(1), Some(false));
Removes the last element from the Vob and returns it, or None
if it is empty.
Examples
use vob::Vob;
let mut v = Vob::new();
v.push(true);
assert_eq!(v.pop(), Some(true));
assert_eq!(v.pop(), None);
Returns true if the Vob has a length of 0.
Examples
use vob::Vob;
assert_eq!(Vob::from_elem(true, 2).is_empty(), false);
assert_eq!(Vob::new().is_empty(), true);
Splits the collection into two at the given index.
Returns a newly allocated Self. self contains elements [0, at), and the returned Self contains elements [at, len).
Note that the capacity of self does not change.
Examples
use vob::Vob;
let mut v1 = Vob::new();
v1.push(true);
v1.push(false);
let v2 = v1.split_off(1);
assert_eq!(v1, Vob::from_elem(true, 1));
assert_eq!(v2, Vob::from_elem(false, 1));
Returns the value of the element at position index
or None
if out of bounds.
Examples
use vob::Vob;
let mut v = Vob::new();
v.push(false);
assert_eq!(v.get(0), Some(false));
assert_eq!(v.get(1), None);
Sets the value of the element at position index
. Returns true
if this led to a change
in the underlying storage or false
otherwise.
Examples
use vob::Vob;
let mut v = Vob::new();
v.push(false);
v.set(0, true);
assert_eq!(v.get(0), Some(true));
assert_eq!(v.set(0, false), true);
assert_eq!(v.set(0, false), false);
Panics
If index
is out of bounds.
Returns an iterator over the slice.
Examples
use vob::Vob;
let mut v = Vob::new();
v.push(false);
v.push(true);
let mut iterator = v.iter();
assert_eq!(iterator.next(), Some(false));
assert_eq!(iterator.next(), Some(true));
assert_eq!(iterator.next(), None);
pub fn iter_set_bits<R>(&self, range: R) -> IterSetBits<'_, T>ⓘNotable traits for IterSetBits<'a, T>impl<'a, T: Debug + PrimInt> Iterator for IterSetBits<'a, T> type Item = usize;
where
R: RangeBounds<usize>,
pub fn iter_set_bits<R>(&self, range: R) -> IterSetBits<'_, T>ⓘNotable traits for IterSetBits<'a, T>impl<'a, T: Debug + PrimInt> Iterator for IterSetBits<'a, T> type Item = usize;
where
R: RangeBounds<usize>,
impl<'a, T: Debug + PrimInt> Iterator for IterSetBits<'a, T> type Item = usize;
Returns an iterator which efficiently produces the index of each set bit in the specified range. Assuming appropriate support from your CPU, this is much more efficient than checking each bit individually.
Examples
use vob::Vob;
let mut v = Vob::new();
v.push(false);
v.push(true);
let mut iterator = v.iter_set_bits(..);
assert_eq!(iterator.next(), Some(1));
assert_eq!(iterator.next(), None);
pub fn iter_unset_bits<R>(&self, range: R) -> IterUnsetBits<'_, T>ⓘNotable traits for IterUnsetBits<'a, T>impl<'a, T: Debug + PrimInt> Iterator for IterUnsetBits<'a, T> type Item = usize;
where
R: RangeBounds<usize>,
pub fn iter_unset_bits<R>(&self, range: R) -> IterUnsetBits<'_, T>ⓘNotable traits for IterUnsetBits<'a, T>impl<'a, T: Debug + PrimInt> Iterator for IterUnsetBits<'a, T> type Item = usize;
where
R: RangeBounds<usize>,
impl<'a, T: Debug + PrimInt> Iterator for IterUnsetBits<'a, T> type Item = usize;
Returns an iterator which efficiently produces the index of each unset bit in the specified range. Assuming appropriate support from your CPU, this is much more efficient than checking each bit individually.
Examples
use vob::Vob;
let mut v = Vob::new();
v.push(false);
v.push(true);
let mut iterator = v.iter_unset_bits(..);
assert_eq!(iterator.next(), Some(0));
assert_eq!(iterator.next(), None);
pub fn iter_storage(&self) -> StorageIter<'_, T>ⓘNotable traits for StorageIter<'a, T>impl<'a, T: Debug + PrimInt> Iterator for StorageIter<'a, T> type Item = T;
pub fn iter_storage(&self) -> StorageIter<'_, T>ⓘNotable traits for StorageIter<'a, T>impl<'a, T: Debug + PrimInt> Iterator for StorageIter<'a, T> type Item = T;
impl<'a, T: Debug + PrimInt> Iterator for StorageIter<'a, T> type Item = T;
Return an iterator over the underlying storage blocks. The last block is guaranteed to have
“unused” bits (i.e. those past self.len()
) set to 0.
Examples
use vob::Vob;
let v1 = Vob::from_elem(true, 10);
assert_eq!(v1.iter_storage().next(), Some((1 << 10) - 1));
let v2 = Vob::from_elem(true, 129);
assert_eq!(v2.iter_storage().last(), Some(1));
Resizes the Vob in-place so that len
is equal to new_len
.
If new_len
is greater than len
, the Vob is extended by the difference, with each
additional slot filled with value
. If new_len
is less than len
, the vob is simply
truncated.
Examples
use vob::Vob;
let mut v = Vob::new();
v.push(false);
v.resize(129, true);
assert_eq!(v.len(), 129);
assert_eq!(v.get(0), Some(false));
assert_eq!(v.get(128), Some(true));
Appends all elements in a slice to the Vob.
Iterates over the slice other
and appends elements in order.
Note that this function is same as extend except that it is specialized to work with slices instead. If and when Rust gets specialization this function will likely be deprecated (but still available).
Examples
use vob::vob;
let mut v = vob![true];
v.extend_from_slice(&vec![false, true]);
assert_eq!(v, vob![true, false, true]);
Append all elements from a second Vob to this Vob.
Use this instead of extend()
when extending with a Vob, because this method is a lot
faster.
Examples
use vob::vob;
let mut v1 = vob![true];
let v2 = vob![false, false];
v1.extend_from_vob(&v2);
assert_eq!(v1, vob![true, false, false]);
Clears the Vob, removing all values.
Note that this method has no effect on the allocated capacity of the Vob.
Sets all bits in the Vob to value
. Notice that this does not change the number of bits
stored in the Vob.
Examples
use vob::vob;
let mut v = vob![true, false, true];
v.set_all(false);
assert_eq!(v, vob![false, false, false]);
Negates all bits in the Vob.
Examples
use vob::vob;
let mut v = vob![true, false];
v.negate();
assert_eq!(v, vob![false, true]);
For each bit in this Vob, and
it with the corresponding bit in other
, returning true
if this led to any changes or false
otherwise. The two Vobs must have the same number of
bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let mut v1 = vob![true, false, false];
let v2 = vob![true, true, false];
assert_eq!(v1.and(&v2), false);
assert_eq!(v1, vob![true, false, false]);
For each bit in this Vob, or
it with the corresponding bit in other
, returning true
if this led to any changes or false
otherwise. The two Vobs must have the same number of
bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let mut v1 = vob![true, false, false];
let v2 = vob![false, true, false];
assert_eq!(v1.or(&v2), true);
assert_eq!(v1, vob![true, true, false]);
For each bit in this Vob, xor
it with the corresponding bit in other
, returning true
if this led to any changes or false
otherwise. The two Vobs must have the same number of
bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let mut v1 = vob![true, false, true];
let v2 = vob![false, true, true];
assert_eq!(v1.xor(&v2), true);
assert_eq!(v1, vob![true, true, false]);
Trait Implementations
For each bit in this Vob, and
it with the corresponding bit in other
.
Store the result in a clone of self
.
The two Vobs must have the same number of bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let v1 = vob![true, false, true, false];
let v2 = vob![true, true, false, false];
let v3 = &v1 & &v2;
assert_eq!(v3, vob![true, false, false, false]);
For each bit in this Vob, and
it with the corresponding bit in other
.
Store the result in the moved and returned self
.
The two Vobs must have the same number of bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let v1 = vob![true, false, true, false];
let v2 = vob![true, true, false, false];
let v3 = v1 & &v2; // v1 is moved, but reused as v3
assert_eq!(v3, vob![true, false, false, false]);
type Output = Self
type Output = Self
The resulting type after applying the &
operator.
For each bit in this Vob, and
it with the corresponding bit in other
.
Store the result in self
.
The two Vobs must have the same number of bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let mut v1 = vob![true, false, true, false];
let v2 = vob![true, true, false, false];
v1 &= &v2;
assert_eq!(v1, vob![true, false, false, false]);
For each bit in this Vob, or
it with the corresponding bit in other
.
Store the result in clone of self
.
The two Vobs must have the same number of bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let v1 = vob![true, false, true, false];
let v2 = vob![true, true, false, false];
let v3 = &v1 | &v2;
assert_eq!(v3, vob![true, true, true, false]);
For each bit in this Vob, or
it with the corresponding bit in other
.
Store the result in the moved and returned self
.
The two Vobs must have the same number of bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let v1 = vob![true, false, true, false];
let v2 = vob![true, true, false, false];
let v3 = v1 | &v2; // v1 is moved, but reused as v3
assert_eq!(v3, vob![true, true, true, false]);
type Output = Self
type Output = Self
The resulting type after applying the |
operator.
For each bit in this Vob, or
it with the corresponding bit in other
.
Store the result in self
.
The two Vobs must have the same number of bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let mut v1 = vob![true, false, true, false];
let v2 = vob![true, true, false, false];
v1 |= &v2;
assert_eq!(v1, vob![true, true, true, false]);
For each bit in this Vob, xor
it with the corresponding bit in other
.
Store the result in a clone of self
.
The two Vobs must have the same number of bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let v1 = vob![true, true, false, true];
let v2 = vob![true, false, true, true];
let v3 = &v1 ^ &v2;
assert_eq!(v3, vob![false, true, true, false]);
For each bit in this Vob, xor
it with the corresponding bit in other
.
Store the result in the moved and returned self
.
The two Vobs must have the same number of bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let v1 = vob![true, true, false, true];
let v2 = vob![true, false, true, true];
let v3 = v1 ^ &v2; // v1 is moved, but reused as v3
assert_eq!(v3, vob![false, true, true, false]);
type Output = Self
type Output = Self
The resulting type after applying the ^
operator.
For each bit in this Vob, xor
it with the corresponding bit in other
.
Store the result in self
.
The two Vobs must have the same number of bits.
Panics
If the two Vobs are of different length.
Examples
use vob::vob;
let mut v1 = vob![true, true, false, true];
let v2 = vob![true, false, true, true];
v1 ^= &v2;
assert_eq!(v1, vob![false, true, true, false]);
Extends a collection with the contents of an iterator. Read more
extend_one
)Extends a collection with exactly one element.
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
Create a Vob from an iterator.
Examples
use std::iter::FromIterator;
use vob::Vob;
let v = Vob::from_iter(vec![true, false]);
assert_eq!(v, Vob::from_iter(vec![true, false]));
Auto Trait Implementations
impl<T> RefUnwindSafe for Vob<T> where
T: RefUnwindSafe,
impl<T> UnwindSafe for Vob<T> where
T: UnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more