9个不稳定版本 (3个破坏性更改)

0.4.4 2023年4月2日
0.4.3 2023年4月2日
0.4.0 2023年3月29日
0.3.1 2023年3月18日
0.1.1 2023年2月18日

206 in 数据结构

Download history 48/week @ 2024-03-13 1/week @ 2024-03-27 1/week @ 2024-04-03 2/week @ 2024-05-22 148/week @ 2024-05-29 226/week @ 2024-06-05 460/week @ 2024-06-12 338/week @ 2024-06-19 393/week @ 2024-06-26

每月1,466次下载

MIT/Apache

130KB
2.5K SLoC

引用计数向量。

概述

此crate提供了以下两种类型

  • SharedVector<T, A>/AtomicSharedVector<T, A>,一个不可变的引用计数向量(具有原子引用计数变体)。
  • Vector<T, A>,一个具有类似于 std::Vec<T> API的唯一向量类型。

内部,共享向量与标准 Vec<T> 有所不同。 SharedVectorAtomicSharedVector 持有一个指向包含以下内容的缓冲区的单个指针:

  • 存储长度、容量和分配器的头
  • 类型为 T 的项目的连续序列。

Vector 的表示更接近于 Vec<T>:它将长度和容量信息存储在行内,并且仅在转换为共享向量时将它们写入头。分配的缓冲区为头留出了空间,因此转换为和从 SharedVector 转换不需要重新分配。

这允许这两个之间的非常便宜转换

  • 共享到唯一:只有当有多个句柄指向同一个缓冲区时(引用计数大于1)才创建新的分配。
  • 唯一到共享:由于唯一缓冲区保证是它们缓冲区的唯一所有者,因此总是快速。

泛型参数 A 是分配器。此crate使用 allocator-api2 来填充不稳定 allocator_api 功能。这使得在功能仍然是夜间时,可以在稳定Rust中使用自定义分配器。

用例

Arc<Vec<T>> 去除间接引用。

可以使用 Vec-style API 构建一个向量,然后将其变为不可变和引用计数,以适应各种用例(易于多线程或简单地共享所有权)。

使用标准库,可能会首先构建一个 Vec<T>,并通过 Arc<Vec<T>> 进行共享。这是一个不错的方法,但代价是额外的指针间接引用,这在原则上可以避免。另一种方法是将其作为一个 Arc<[T]> 来共享,这样可以消除间接引用,但代价是需要重新分配和复制内容。

使用此软件包,结果共享向量中没有任何额外的间接引用,并且在唯一版本和共享版本之间也没有任何复制。

use shared_vector::Vector;
let mut builder = Vector::new();
builder.push(1u32);
builder.push(2);
builder.push(3);
// Make it reference counted, no allocation.
let mut shared = builder.into_shared();
// We can now create new references
let shared_2 = shared.new_ref();
let shared_3 = shared.new_ref();

不可变数据结构

SharedVectorAtomicSharedVector 的行为类似于简单的不可变数据结构,是创建更复杂数据结构的好构建块。

use shared_vector::{SharedVector, rc_vector};
let mut a = rc_vector![1u32, 2, 3];

// `new_ref` (you can also use `clone`) creates a second reference to the same buffer.
// future mutations of `a` won't affect `b`.
let mut b = a.new_ref();
// Because both a and b point to the same buffer, the next mutation allocates a new
// copy under the hood.
a.push(4);
// Now that a and b are unique pointers to their own buffers, no allocation happens
// when pushing to them.
a.push(5);
b.push(6);

assert_eq!(a.as_slice(), &[1, 2, 3, 4, 5]);
assert_eq!(b.as_slice(), &[1, 2, 3, 6]);

请注意,SharedVector 并不是 RRB 向量实现。

ChunkVector

作为一个非常轻量级的实验,旨在在共享向量之上创建自定义不可变数据结构,示例文件夹中有一个非常简单的分块向量实现。

就像向量类型一样,“分块向量”有三种形式:ChunkVectorSharedChunkVectorAtomicSharedChunkVector

它们在内部表示为引用计数的表,该表包含引用计数的内存块(或“块”)。在上面的插图上,两个分块向量指向同一个表,而另一个指向不同的表,但仍共享一些存储块。在实际应用中,分块向量类型仅比 SharedVector<SharedVector<T>> 略微复杂一些。

限制

  • 这些向量类型最多可以容纳 u32::MAX 个元素。

许可

根据以下任一许可授权

贡献

请参阅 贡献指南

依赖项

~260KB