range-set

使用泛型 SmallVec 存储将 PrimInt 值存储为包含范围。

文档

一个泛型 smallvec::Array 参数允许选择在堆上溢出之前堆栈上可以容纳多少个范围

let mut s = range_set![0..=2; 1];
println!("s: {:?}", s);
assert!(!s.spilled());

assert!(s.insert_range (8..=10).is_none());
println!("s: {:?}", s);
assert!(s.spilled());
let v : Vec <u32> = s.iter().collect();
assert_eq!(v, vec![0,1,2,8,9,10]);

assert_eq!(s.insert_range (3..=12), Some (range_set![8..=10; 1]));
s.shrink_to_fit();
println!("s: {:?}", s);
assert!(!s.spilled());
let v : Vec <u32> = s.iter().collect();
assert_eq!(v, vec![0,1,2,3,4,5,6,7,8,9,10,11,12]);

这对于需要按顺序遍历的大块非连续数据最有用。

用法

  use range_set::{range_set, RangeSet};
  let mut s = RangeSet::<[_; 2]>::from_ranges ([1..=100, 500..=1000]);
  s.insert (200);
  s.insert_range (400..=499);
  assert_eq!(s, range_set![1..=100, 200..=200, 400..=1000]);

请参阅 ./examples/example.rs 和文档以获取更多示例。

堆栈大小

顶层的 report_sizes 函数将报告各种整数类型和数组大小组合的字节大小。调用此函数的程序可以在 ./examples/example.rs 中找到。示例输出

RangeSet report sizes...
  size of RangeSet <[RangeInclusive <u8>; 1]>: 32
  size of RangeSet <[RangeInclusive <u16>; 1]>: 32
  size of RangeSet <[RangeInclusive <u32>; 1]>: 32
  size of RangeSet <[RangeInclusive <u64>; 1]>: 32
  size of RangeSet <[RangeInclusive <usize>; 1]>: 32
  size of RangeSet <[RangeInclusive <u8>; 2]>: 32
  size of RangeSet <[RangeInclusive <u16>; 2]>: 32
  size of RangeSet <[RangeInclusive <u32>; 2]>: 32
  size of RangeSet <[RangeInclusive <u64>; 2]>: 48
  size of RangeSet <[RangeInclusive <usize>; 2]>: 48
  size of RangeSet <[RangeInclusive <u8>; 4]>: 32
  size of RangeSet <[RangeInclusive <u16>; 4]>: 32
  size of RangeSet <[RangeInclusive <u32>; 4]>: 48
  size of RangeSet <[RangeInclusive <u64>; 4]>: 80
  size of RangeSet <[RangeInclusive <usize>; 4]>: 80
  size of RangeSet <[RangeInclusive <u8>; 8]>: 32
  size of RangeSet <[RangeInclusive <u16>; 8]>: 48
  size of RangeSet <[RangeInclusive <u32>; 8]>: 80
  size of RangeSet <[RangeInclusive <u64>; 8]>: 144
  size of RangeSet <[RangeInclusive <usize>; 8]>: 144
  size of RangeSet <[RangeInclusive <u8>; 16]>: 48
  size of RangeSet <[RangeInclusive <u16>; 16]>: 80
  size of RangeSet <[RangeInclusive <u32>; 16]>: 144
  size of RangeSet <[RangeInclusive <u64>; 16]>: 272
  size of RangeSet <[RangeInclusive <usize>; 16]>: 272
...RangeSet report sizes

存储 u8 (字节) 范围不是一个好主意，因为最小大小（在堆栈上存储单个范围）是 32 字节，足以存储 256 个值的完整范围作为单独的位（32 * 8 = 256）。

操作

由于范围是按顺序存储的，因此插入和删除值时使用二分搜索。