GeezerVison is showing docs.rs — RoaringBitMap in algorithm - Rust pub struct RoaringBitMap { /* private fields */ }
Expand description位图类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§
添加新的元素
§Examples
use algorithm::RoaringBitMap;
fn main() {
let mut map = RoaringBitMap::new();
map.add(1);
assert!(map.contains(&1));
assert!(map.len() == 1);
}
添加许多新的元素
§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);
}
添加范围内的元素(包含头与结果)，批量添加增加效率
§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);
}
删除元素
§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);
}
删除列表中元素
§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);
}
删除范围元素（包含头与尾）
§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));
}
醒看是否包含
§Examples
use algorithm::RoaringBitMap;
fn main() {
let mut map = RoaringBitMap::new();
map.add(7);
assert!(map.contains(&7));
}
迭代器，通过遍历进行循环，如果位图的容量非常大，可能效率相当低
§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]);
}
是否保留，通过遍历进行循环，如果位图的容量非常大，可能效率相当低
§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]);
}
是否为子位图
§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));
}
取两个位图间的交集
§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]);
}
取两个位图间的并集
§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]);
}
取两个位图间的异或并集
§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§
The resulting type after applying the & operator.
The resulting type after applying the | operator.
The resulting type after applying the ^ operator.
Performs copy-assignment from source. Read more
Formats the value using the given formatter. Read more
Formats the value using the given formatter. Read more
Extends a collection with the contents of an iterator. Read more
🔬This is a nightly-only experimental API. (extend_one) Extends a collection with exactly one element.
🔬This is a nightly-only experimental API. (extend_one) Reserves capacity in a collection for the given number of additional elements. Read more
Auto Trait Implementations§Blanket Implementations§
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more
🔬This is a nightly-only experimental API. (clone_to_uninit) Performs copy-assignment from self to dest. Read more
Compare self to key and return true if they are equal.
Returns the argument unchanged.
Calls U::from(self).
That is, this conversion is whatever the implementation of
From<T> for U chooses to do.
The resulting type after obtaining ownership.
Creates owned data from borrowed data, usually by cloning. Read more
Uses borrowed data to replace owned data, usually by cloning. Read more
Converts the given value to a String. Read more
The type returned in the event of a conversion error.
Performs the conversion.
The type returned in the event of a conversion error.
Performs the conversion. |