Struct RoaringBitMap

pub struct RoaringBitMap { /* private fields */ }

位图类RoaringBitMap，根据访问的位看是否被占用 本质上是将大块的bitmap分成各个小块，其中每个小块在需要存储数据的时候才会存在 解决经典的是否被占用的问题，不会一次性分配大内存 头部以val / 65536做为索引键值, 尾部分为Array及HashSet结构 当元素个数小于4096时以有序array做为索引, 当>4096以HashSet做为存储

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_many(&vec![1, 2, 3, 4, 10]);
    assert!(map.contains(&1));
    assert!(!map.contains(&5));
    assert!(map.contains(&10));
    map.add_range(7, 16);
    assert!(!map.contains(&6));
    assert!(map.contains(&7));
    assert!(map.contains(&16));
    assert!(!map.contains(&17));
}

Implementations

impl RoaringBitMap

pub fn new() -> Self

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn clear(&mut self)

pub fn add(&mut self, val: usize)

添加新的元素

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add(1);
    assert!(map.contains(&1));
    assert!(map.len() == 1);
}

pub fn add_many(&mut self, val: &[usize])

添加许多新的元素

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_many(&vec![1, 2, 3, 4, 10]);
    assert!(map.contains(&1));
    assert!(map.contains(&10));
    assert!(map.len() == 5);
}

pub fn add_range(&mut self, start: usize, end: usize)

添加范围内的元素(包含头与结果)，批量添加增加效率

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_range(7, 16);
    assert!(!map.contains(&6));
    assert!(map.contains(&7));
    assert!(map.contains(&16));
    assert!(!map.contains(&17));
    assert!(map.len() == 10);
}

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

删除元素

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_range(7, 16);
    assert!(map.len() == 10);
    assert!(map.contains(&7));
    assert!(map.remove(7));
    assert!(!map.contains(&7));
    assert!(map.len() == 9);
}

pub fn remove_many(&mut self, val: &[usize])

删除列表中元素

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_range(7, 16);
    assert!(map.len() == 10);
    assert!(map.contains(&7));
    assert!(map.remove(7));
    assert!(!map.contains(&7));
    assert!(map.len() == 9);
}

pub fn remove_range(&mut self, start: usize, end: usize)

删除范围元素（包含头与尾）

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_range(7, 16);
    assert!(map.len() == 10);
    map.remove_range(7, 15);
    assert!(map.len() == 1);
    assert!(map.contains(&16));
}

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

醒看是否包含

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add(7);
    assert!(map.contains(&7));
}

pub fn iter(&self) -> Iter<'_>

迭代器，通过遍历进行循环，如果位图的容量非常大，可能效率相当低

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add(7);
    map.add_range(9, 12);
    map.add_many(&vec![20, 100, 300]);
    assert!(map.iter().collect::<Vec<_>>() == vec![7, 9, 10, 11, 12, 20, 100, 300]);
}

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&usize) -> bool,

是否保留，通过遍历进行循环，如果位图的容量非常大，可能效率相当低

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_range(9, 16);
    map.retain(|v| v % 2 == 0);
    assert!(map.iter().collect::<Vec<_>>() == vec![10, 12, 14, 16]);
}

pub fn contains_sub(&self, other: &RoaringBitMap) -> bool

是否为子位图

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_range(9, 16);
    let mut sub_map = RoaringBitMap::new();
    sub_map.add_range(9, 12);
    assert!(map.contains_sub(&sub_map));
}

pub fn intersect(&self, other: &RoaringBitMap) -> RoaringBitMap

取两个位图间的交集

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_range(9, 16);
    let mut sub_map = RoaringBitMap::new();
    sub_map.add_range(7, 12);
    let map = map.intersect(&sub_map);
    assert!(map.iter().collect::<Vec<_>>() == vec![9, 10, 11, 12]);
}

pub fn union(&self, other: &RoaringBitMap) -> RoaringBitMap

取两个位图间的并集

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_range(9, 16);
    let mut sub_map = RoaringBitMap::new();
    sub_map.add_range(7, 12);
    let map = map.union(&sub_map);
    assert!(map.iter().collect::<Vec<_>>() == vec![7, 8, 9, 10, 11, 12, 13, 14, 15, 16]);
}

pub fn union_xor(&self, other: &RoaringBitMap) -> RoaringBitMap

取两个位图间的异或并集

Examples

use algorithm::RoaringBitMap;
fn main() {
    let mut map = RoaringBitMap::new();
    map.add_range(9, 16);
    let mut sub_map = RoaringBitMap::new();
    sub_map.add_range(7, 12);
    let map = map.union_xor(&sub_map);
    assert!(map.iter().collect::<Vec<_>>() == vec![7, 8, 13, 14, 15, 16]);
}

Trait Implementations

impl BitAnd for &RoaringBitMap

type Output = RoaringBitMap

The resulting type after applying the & operator.

fn bitand(self, rhs: Self) -> Self::Output

Performs the & operation.

impl BitOr for &RoaringBitMap

type Output = RoaringBitMap

The resulting type after applying the | operator.

fn bitor(self, rhs: Self) -> Self::Output

Performs the | operation.

impl BitXor for &RoaringBitMap

type Output = RoaringBitMap

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: Self) -> Self::Output

Performs the ^ operation.

impl Clone for RoaringBitMap

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for RoaringBitMap

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

Formats the value using the given formatter.

impl Display for RoaringBitMap

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

Formats the value using the given formatter.

impl Extend<usize> for RoaringBitMap

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl FromIterator<usize> for RoaringBitMap

fn from_iter<T: IntoIterator<Item = usize>>(iter: T) -> RoaringBitMap

Creates a value from an iterator.

impl PartialEq for RoaringBitMap

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

Tests for self and other values to be equal, and is used by ==.

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

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for RoaringBitMap