#discriminant #optimization #optimized #nightly #space #memory #collection

vec-option

存储判别符的独立版本,是 Vec<Option<T>> 的空间优化版本。

4 个版本 (2 个破坏性更新)

0.3.0 2019年8月15日
0.2.1 2019年8月15日
0.2.0 2019年8月14日
0.1.0 2019年8月14日

#720 in 数据结构

每月 21 次下载

MIT 许可证

52KB
1K SLoC

vec-option

Vec<Option<T>> 的空间优化版本,它将判别符单独存储。

功能标志

nightly - 这将打开一些优化(使 Cloneing Copy 元素更加便宜)并将 try_foldtry_for_each 扩展到所有 Try 类型。最后,这也允许使用 .nth_back(n) 方法。

优点

  • 如果 Option<T> 的空间优化不起作用,则与 Vec<Option<T>> 相比,可以拥有更小的内存占用。
  • 如果 Option<T> 的空间优化不起作用,则更具有缓存友好性。
  • 可以快速将整个集合设置为包含 None
  • 使用 None 快速扩展

缺点

  • 2 次分配,而不是单次分配
  • 不能从向量的中间删除元素
  • 不能直接在选项上工作

示例

就像普通向量一样,可以从向量的末尾推入和弹出元素

let mut vec = VecOption::new();

vec.push(10);

assert_eq!(vec, [Some(10)]);

vec.push(20);
vec.push(None);
vec.push(Some(30));

assert_eq!(vec, [Some(10), Some(20), None, Some(30)]);

assert_eq!(vec.pop(), Some(Some(30)));
assert_eq!(vec.pop(), Some(None));
assert_eq!(vec.pop(), Some(Some(20)));
assert_eq!(vec.pop(), Some(Some(10)));
assert_eq!(vec.pop(), None);
assert_eq!(vec, []);

可以获取向量中的元素

let mut vec = VecOption::from(vec![0, 1, 2, 3, 4]);

assert_eq!(vec.get(2), Some(Some(&2)));
assert_eq!(vec.get_mut(4), Some(Some(&mut 4)));
assert_eq!(vec.get(5), None);

可以交换和替换元素

vec.swap(2, 1);

assert_eq!(vec, [Some(0), Some(2), Some(1), Some(3), Some(4)]);

assert_eq!(vec.replace(3, None), Some(Some(3)));
assert_eq!(vec.replace(1, Some(10)), Some(Some(1)));

assert_eq!(vec, [Some(0), Some(10), Some(1), None, Some(4)]);

或者如果 vec.replace(index, None) 太多,你可以这样做

assert_eq!(vec.take(1), Some(Some(10)));

assert_eq!(vec, [Some(0), None, Some(1), None, Some(4)]);

当然,你也可以截断或清除向量

let mut vec = VecOption::from(vec![0, 1, 3, 4]);

assert_eq!(vec.len(), 4);

vec.truncate(2);

assert_eq!(vec, [0, 1]);

vec.clear();

assert!(vec.is_empty());

但是,由于分割向量表示的限制,你无法在闭包之外获取 &Option<T>/&mut Option<T>。事实上,你甚至无法获取一个 &Option<T>,这几乎是毫无用处的,因为你唯一能做的就是将其转换为 Option<&T>。但是 &mut Option<T> 是有用的,因此有一些函数允许你操作它们。

// This one allows you to edit a single value however you want, and the updates will
// be reflected once the closure returns. If the closure panics, then it is as if you took the
// option out of the vector.
vec.with_mut(index, |element: &mut Option<T>| {
    ...
});

以下函数类似于 Iterator 中的对应函数,它们遍历向量,并根据你调用的函数执行操作。唯一的区别是你可以直接操作 &mut Option<T>。再次强调,如果闭包崩溃,它将类似于从向量中取出值。

vec.try_fold(...);

vec.fold(...);

vec.try_for_each(...);

vec.for_each(...);

但是,由于这些限制,你很快就会用 None 填满你的向量,并将向量的所有元素设置为 None!如果你的类型没有 drop glue,这可以编译成简单的 memset

let mut vec = VecOption::from(vec![0, 1, 2, 3, 4]);

assert_eq!(vec, [Some(0), Some(2), Some(1), Some(3), Some(4)]);

vec.extend_none(5);

assert_eq!(vec, [Some(0), Some(2), Some(1), Some(3), Some(4), None, None, None, None, None]);

vec.set_all_none();

assert_eq!(vec, [None, None, None, None, None, None, None, None, None, None]);

无运行时依赖

特性