#bits #usize #performance #api #vec #backing #sequence

vob

Vector of Bits with Vec-like API and usize backing storage

17 stable releases (3 major)

3.0.3 Aug 2, 2023
3.0.2 Jul 25, 2022
3.0.1 Oct 22, 2021
2.0.6 Jan 25, 2021
0.1.0 Feb 1, 2018

#107 in Data structures

Download history 1265/week @ 2023-12-07 1335/week @ 2023-12-14 1069/week @ 2023-12-21 1004/week @ 2023-12-28 1298/week @ 2024-01-04 1053/week @ 2024-01-11 1082/week @ 2024-01-18 1045/week @ 2024-01-25 865/week @ 2024-02-01 767/week @ 2024-02-08 885/week @ 2024-02-15 915/week @ 2024-02-22 1134/week @ 2024-02-29 1797/week @ 2024-03-07 1738/week @ 2024-03-14 886/week @ 2024-03-21

5,723 downloads per month
Used in 20 crates (13 directly)

Apache-2.0/MIT

67KB
1K SLoC

Build Status Latest version Documentation

Vector of Bits (Vob)

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. Vob is broadly similar to BitVec, but has an API more closely aligned to Vec<bool> and allows non-32-bit backing storage. On 64-bit systems this can lead to a substantial performance increase, particularly when functions such as iter_set_bits are used.

Usage

use vob::vob;

let mut v = vob![false, true, false];
assert_eq!(v[2], false);
v.set(2, true);
assert_eq!(v[2], true);
assert_eq!(v.iter_set_bits(..).collect::<Vec<_>>(), vec![1, 2]);

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 crate, 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 Vobs 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.

Dependencies

~98–345KB