Struct FlatBitSet 

pub struct FlatBitSet<K = usize, C = u64>(/* private fields */);

有序、稀疏、节省空间的 bitset，适用于小数据量

实际上可以看作从 Key 到 Chunk 的 flat map。 故而，其时间复杂度与 flat map 同：增删 O(n)、查询 O(log(n))、遍历 O(n)。

Implementations

impl<K, C> FlatBitSet<K, C>

pub const fn new() -> Self

空集

let set = FlatBitSet::<usize>::new();
assert!(set.is_empty());

pub fn with_capacity(capacity: usize) -> Self

至少具有指定容量的块的空集

注意：所给的数字代表块数，而非元素数。块数可能远小于元素数。 n 个元素最少需要 n / C::BITS 个块，最多需要 n 个。

let set = FlatBitSet::<usize>::with_capacity(10);
assert!(set.is_empty());
assert!(set.inner().capacity() >= 10);

pub fn is_empty(&self) -> bool

判断是否为空

相当于 set.count() == 0。

let mut set = FlatBitSet::<usize>::new();
assert!(set.is_empty());
set.insert(1);
assert!(!set.is_empty());

pub fn inner(&self) -> &Vec<(K, C)>

获取内部数组

pub fn clear(&mut self)

清空集合

let mut set = FlatBitSet::<usize>::from_iter([1, 2, 3]);
set.clear();
assert!(set.is_empty());

impl<K: Key, C: Chunk> FlatBitSet<K, C>

pub fn count(&self) -> usize

元素个数

注意：时间复杂度是 O(n)！

let set = FlatBitSet::<usize>::from_iter([1, 2, 3]);
assert_eq!(set.count(), 3);

pub fn contains(&self, key: K) -> bool

判断元素是否属于集合

可以使用 set[key]，作用相同，更简洁。

时间复杂度：O(log(n))。

let set = FlatBitSet::<usize>::from_iter([1, 2, 3]);
assert_eq!(set.contains(1), true);
assert_eq!(set[114514], false);

pub fn insert(&mut self, key: K) -> bool

插入元素

若元素是新的，返回 true（与标准库相同）。若已有元素，集合不变。

时间复杂度：O(n)。

let mut set = FlatBitSet::<usize>::new();
assert_eq!(set.insert(1), true);
assert_eq!(set.insert(1), false);

pub fn remove(&mut self, key: K) -> bool

删除元素

若已有元素，返回 true（与标准库相同）。若没有元素，集合不变。

时间复杂度：O(n)。

let mut set = FlatBitSet::<usize>::from_iter([1, 2, 3]);
assert_eq!(set.remove(1), true);
assert_eq!(set.remove(1), false);

pub fn toggle(&mut self, key: K) -> bool

翻转某一位

若已有元素，删除之；否则插入之。

若已有元素，则返回 true。

时间复杂度：O(n)。

let mut set = FlatBitSet::<usize>::new();
assert_eq!(set.toggle(1), false);
assert_eq!(set[1], true);
assert_eq!(set.toggle(1), true);
assert_eq!(set[1], false);

pub fn set(&mut self, key: K, presence: bool) -> bool

设置某一位

设置某元素的存在性。若 presence 为 true 则插入之；否则删除之。 若已有元素而插入，或没有元素而删除，集合均不变。

若已有元素，返回 true。

时间复杂度：O(n)。

let mut set = FlatBitSet::<usize>::new();
assert_eq!(set.set(1, true), false);
assert_eq!(set[1], true);
assert_eq!(set.set(1, false), true);
assert_eq!(set[1], false);

pub fn shrink_to_fit(&mut self)

尽可能缩小容量

let mut set = FlatBitSet::<usize>::with_capacity(10);
set.extend([1, 2, 3]);
assert!(set.inner().capacity() >= 10);
set.shrink_to_fit();
assert!(set.inner().capacity() >= 1);

pub fn reserve(&mut self, additional: usize)

保留至少指定容量的块

注意：所给的数字代表块数，而非元素数。块数可能远小于元素数。 n 个元素最少需要 n / C::BITS 个块，最多需要 n 个。

let mut set = FlatBitSet::<usize>::from_iter([1, 2, 3]);
set.reserve(10);
assert!(set.inner().capacity() >= 11);

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

判断子集

若该集合是另一个集合的子集（可以相等），返回 true。

let set = FlatBitSet::<usize>::from_iter([1, 2, 3]);
assert!(set.is_subset(&set));
assert!(!set.is_subset(&FlatBitSet::from_iter([2, 3, 4])));
assert!(set.is_subset(&FlatBitSet::from_iter([1, 2, 3, 4])));

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

判断超集

若该集合是另一个集合的超集（可以相等），返回 true。

let set = FlatBitSet::<usize>::from_iter([1, 2, 3]);
assert!(set.is_superset(&set));
assert!(!set.is_superset(&FlatBitSet::from_iter([2, 3, 4])));
assert!(set.is_superset(&FlatBitSet::from_iter([2, 3])));

pub fn subset_cmp(&self, other: &Self) -> Option<Ordering>

比较子集关系

若该集合是另一个集合的真子集，返回 Some(Less)； 若是真超集，返回 Some(Greater)； 若相等，返回 Some(Equal)；否则返回 None。

let set = FlatBitSet::<usize>::from_iter([1, 2, 3]);
assert_eq!(set.subset_cmp(&set), Some(Equal));
assert_eq!(set.subset_cmp(&FlatBitSet::from_iter([1, 2, 3, 4])), Some(Less));
assert_eq!(set.subset_cmp(&FlatBitSet::from_iter([1, 2])), Some(Greater));
assert_eq!(set.subset_cmp(&FlatBitSet::from_iter([2, 3, 4])), None);

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

判断交集为空

若两集合没有共同元素，返回 true。

let set = FlatBitSet::<usize>::from_iter([1, 2, 3]);
assert!(set.is_disjoint(&FlatBitSet::from_iter([4, 5, 6])));
assert!(!set.is_disjoint(&FlatBitSet::from_iter([2, 3, 4])));

pub fn perform_biop_with<O: BiOp<C>>(&mut self, other: &Self)

原地进行二元逻辑运算

请使用 FlatBitSet::intersection_with 之类的方法。 也可以使用 s1 & &s2 之类的运算符，作用相同，更为简洁。 运算符会获取左侧集合的所有权，改写后返回其自身。

会预先计算大小，最多只会分配一次。不会减少容量。

也可以看看创造新集合的 FlatBitSet::intersection、 返回迭代器的 FlatBitSet::intersection_iter 以及惰性完成的 Thunk::intersection

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

集合中元素的借用迭代器

有序。

let set = FlatBitSet::<usize>::from_iter([3, 2, 1]);
assert!(set.iter().eq([1, 2, 3]));

pub fn thunk(&self) -> Thunk<Copied<Iter<'_, (K, C)>>>

获取惰性集合

请参阅 Thunk。

impl<K: Key, C: Chunk> FlatBitSet<K, C>

pub fn intersection(&self, other: &Self) -> Self

计算交集

可以使用运算符 &s1 & &s2，作用相同，更为简洁。

let s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
let set = s1.intersection(&s2);
assert!(set.iter().eq([2, 3]));

可以看看就地计算的 FlatBitSet::intersection_with、返回迭代器的 FlatBitSet::intersection_iter 以及惰性计算的 Thunk::intersection（该方法在内部就是用了它）。

pub fn intersection_with(&mut self, other: &Self)

就地计算交集

可以使用运算符 s1 & &s2，作用相同，更为简洁。 运算符会获取左侧集合的所有权，改写后返回其自身。

let mut s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
s1.intersection_with(&s2);
assert!(s1.iter().eq([2, 3]));

可以看看返回新集合的 FlatBitSet::intersection、返回迭代器的 FlatBitSet::intersection_iter 以及惰性计算的 Thunk::intersection。

pub fn intersection_iter<'a>( &'a self, other: &'a Self, ) -> GenericIter<BiOpIter<AndOp, Copied<Iter<'a, (K, C)>>, Copied<Iter<'a, (K, C)>>>, K, C>

交集中元素的迭代器

let mut s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
let iter = s1.intersection_iter(&s2);
assert!(iter.eq([2, 3]));

可以看看返回新集合的 FlatBitSet::intersection、就地计算的 FlatBitSet::intersection_with 以及惰性计算的 Thunk::intersection（该方法在内部就是用了它）。

impl<K: Key, C: Chunk> FlatBitSet<K, C>

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

计算并集

可以使用运算符 &s1 | &s2，作用相同，更为简洁。

let s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
let set = s1.union(&s2);
assert!(set.iter().eq([1, 2, 3, 4]));

可以看看就地计算的 FlatBitSet::union_with、返回迭代器的 FlatBitSet::union_iter 以及惰性计算的 Thunk::union（该方法在内部就是用了它）。

pub fn union_with(&mut self, other: &Self)

就地计算并集

可以使用运算符 s1 | &s2，作用相同，更为简洁。 运算符会获取左侧集合的所有权，改写后返回其自身。

let mut s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
s1.union_with(&s2);
assert!(s1.iter().eq([1, 2, 3, 4]));

可以看看返回新集合的 FlatBitSet::union、返回迭代器的 FlatBitSet::union_iter 以及惰性计算的 Thunk::union。

pub fn union_iter<'a>( &'a self, other: &'a Self, ) -> GenericIter<BiOpIter<OrOp, Copied<Iter<'a, (K, C)>>, Copied<Iter<'a, (K, C)>>>, K, C>

并集中元素的迭代器

let mut s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
let iter = s1.union_iter(&s2);
assert!(iter.eq([1, 2, 3, 4]));

可以看看返回新集合的 FlatBitSet::union、就地计算的 FlatBitSet::union_with 以及惰性计算的 Thunk::union（该方法在内部就是用了它）。

impl<K: Key, C: Chunk> FlatBitSet<K, C>

pub fn symmetric_difference(&self, other: &Self) -> Self

计算对称差

可以使用运算符 &s1 ^ &s2，作用相同，更为简洁。

let s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
let set = s1.symmetric_difference(&s2);
assert!(set.iter().eq([1, 4]));

可以看看就地计算的 FlatBitSet::symmetric_difference_with、返回迭代器的 FlatBitSet::symmetric_difference_iter 以及惰性计算的 Thunk::symmetric_difference（该方法在内部就是用了它）。

pub fn symmetric_difference_with(&mut self, other: &Self)

就地计算对称差

可以使用运算符 s1 ^ &s2，作用相同，更为简洁。 运算符会获取左侧集合的所有权，改写后返回其自身。

let mut s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
s1.symmetric_difference_with(&s2);
assert!(s1.iter().eq([1, 4]));

可以看看返回新集合的 FlatBitSet::symmetric_difference、返回迭代器的 FlatBitSet::symmetric_difference_iter 以及惰性计算的 Thunk::symmetric_difference。

pub fn symmetric_difference_iter<'a>( &'a self, other: &'a Self, ) -> GenericIter<BiOpIter<XorOp, Copied<Iter<'a, (K, C)>>, Copied<Iter<'a, (K, C)>>>, K, C>

对称差中元素的迭代器

let mut s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
let iter = s1.symmetric_difference_iter(&s2);
assert!(iter.eq([1, 4]));

可以看看返回新集合的 FlatBitSet::symmetric_difference、就地计算的 FlatBitSet::symmetric_difference_with 以及惰性计算的 Thunk::symmetric_difference（该方法在内部就是用了它）。

impl<K: Key, C: Chunk> FlatBitSet<K, C>

pub fn difference(&self, other: &Self) -> Self

计算差集

可以使用运算符 &s1 - &s2，作用相同，更为简洁。

let s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
let set = s1.difference(&s2);
assert!(set.iter().eq([1]));

可以看看就地计算的 FlatBitSet::difference_with、返回迭代器的 FlatBitSet::difference_iter 以及惰性计算的 Thunk::difference（该方法在内部就是用了它）。

pub fn difference_with(&mut self, other: &Self)

就地计算差集

可以使用运算符 s1 - &s2，作用相同，更为简洁。 运算符会获取左侧集合的所有权，改写后返回其自身。

let mut s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
s1.difference_with(&s2);
assert!(s1.iter().eq([1]));

可以看看返回新集合的 FlatBitSet::difference、返回迭代器的 FlatBitSet::difference_iter 以及惰性计算的 Thunk::difference。

pub fn difference_iter<'a>( &'a self, other: &'a Self, ) -> GenericIter<BiOpIter<DiffOp, Copied<Iter<'a, (K, C)>>, Copied<Iter<'a, (K, C)>>>, K, C>

差集中元素的迭代器

let mut s1 = FlatBitSet::<usize>::from_iter([1, 2, 3]);
let s2 = FlatBitSet::<usize>::from_iter([2, 3, 4]);
let iter = s1.difference_iter(&s2);
assert!(iter.eq([1]));

可以看看返回新集合的 FlatBitSet::difference、就地计算的 FlatBitSet::difference_with 以及惰性计算的 Thunk::difference（该方法在内部就是用了它）。

Trait Implementations

impl<K: Key, C: Chunk> BitAnd<&FlatBitSet<K, C>> for FlatBitSet<K, C>

type Output = FlatBitSet<K, C>

The resulting type after applying the & operator.

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

Performs the & operation.

impl<K: Key, C: Chunk> BitAnd for &FlatBitSet<K, C>

type Output = FlatBitSet<K, C>

The resulting type after applying the & operator.

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

Performs the & operation.

impl<K: Key, C: Chunk> BitAndAssign<&FlatBitSet<K, C>> for FlatBitSet<K, C>

fn bitand_assign(&mut self, rhs: &Self)

Performs the &= operation.

impl<K: Key, C: Chunk> BitOr<&FlatBitSet<K, C>> for FlatBitSet<K, C>

type Output = FlatBitSet<K, C>

The resulting type after applying the | operator.

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

Performs the | operation.

impl<K: Key, C: Chunk> BitOr for &FlatBitSet<K, C>

type Output = FlatBitSet<K, C>

The resulting type after applying the | operator.

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

Performs the | operation.

impl<K: Key, C: Chunk> BitOrAssign<&FlatBitSet<K, C>> for FlatBitSet<K, C>

fn bitor_assign(&mut self, rhs: &Self)

Performs the |= operation.

impl<K: Key, C: Chunk> BitXor<&FlatBitSet<K, C>> for FlatBitSet<K, C>

type Output = FlatBitSet<K, C>

The resulting type after applying the ^ operator.

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

Performs the ^ operation.

impl<K: Key, C: Chunk> BitXor for &FlatBitSet<K, C>

type Output = FlatBitSet<K, C>

The resulting type after applying the ^ operator.

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

Performs the ^ operation.

impl<K: Key, C: Chunk> BitXorAssign<&FlatBitSet<K, C>> for FlatBitSet<K, C>

fn bitxor_assign(&mut self, rhs: &Self)

Performs the ^= operation.

impl<K: Clone, C: Clone> Clone for FlatBitSet<K, C>

fn clone(&self) -> FlatBitSet<K, C>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Key + Debug, C: Chunk> Debug for FlatBitSet<K, C>

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

Formats the value using the given formatter.

impl<K, C> Default for FlatBitSet<K, C>

fn default() -> Self

Returns the “default value” for a type.

impl<K: Key, C: Chunk> Extend<K> for FlatBitSet<K, C>

fn extend<T: IntoIterator<Item = K>>(&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<K: Key, C: Chunk> FromIterator<K> for FlatBitSet<K, C>

fn from_iter<T: IntoIterator<Item = K>>(iter: T) -> Self

Creates a value from an iterator.

impl<K: Hash, C: Hash> Hash for FlatBitSet<K, C>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<K: Key, C: Chunk> Index<K> for FlatBitSet<K, C>

type Output = bool

The returned type after indexing.

fn index(&self, index: K) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, K: Key, C: Chunk> IntoIterator for &'a FlatBitSet<K, C>

type Item = K

The type of the elements being iterated over.

type IntoIter = GenericIter<Copied<Iter<'a, (K, C)>>, K, C>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Key, C: Chunk> IntoIterator for FlatBitSet<K, C>

type Item = K

The type of the elements being iterated over.

type IntoIter = GenericIter<IntoIter<(K, C)>, K, C>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Ord, C: Ord> Ord for FlatBitSet<K, C>

fn cmp(&self, other: &FlatBitSet<K, C>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<K: PartialEq, C: PartialEq> PartialEq for FlatBitSet<K, C>

fn eq(&self, other: &FlatBitSet<K, C>) -> 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<K: PartialOrd, C: PartialOrd> PartialOrd for FlatBitSet<K, C>

fn partial_cmp(&self, other: &FlatBitSet<K, C>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

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

Tests less than (for self and other) and is used by the < operator.

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

Tests less than or equal to (for self and other) and is used by the <= operator.

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

Tests greater than (for self and other) and is used by the > operator.

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

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K: Key, C: Chunk> Sub<&FlatBitSet<K, C>> for FlatBitSet<K, C>

type Output = FlatBitSet<K, C>

The resulting type after applying the - operator.

fn sub(self, rhs: &Self) -> Self::Output

Performs the - operation.

impl<K: Key, C: Chunk> Sub for &FlatBitSet<K, C>

type Output = FlatBitSet<K, C>

The resulting type after applying the - operator.

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

Performs the - operation.

impl<K: Key, C: Chunk> SubAssign<&FlatBitSet<K, C>> for FlatBitSet<K, C>

fn sub_assign(&mut self, rhs: &Self)

Performs the -= operation.

impl<K: Eq, C: Eq> Eq for FlatBitSet<K, C>

impl<K, C> StructuralPartialEq for FlatBitSet<K, C>