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 数据结构
每月1,466次下载
130KB
2.5K SLoC
引用计数向量。
概述
此crate提供了以下两种类型
SharedVector<T, A>
/AtomicSharedVector<T, A>
,一个不可变的引用计数向量(具有原子引用计数变体)。Vector<T, A>
,一个具有类似于std::Vec<T>
API的唯一向量类型。
内部,共享向量与标准 Vec<T>
有所不同。 SharedVector
和 AtomicSharedVector
持有一个指向包含以下内容的缓冲区的单个指针:
- 存储长度、容量和分配器的头
- 类型为
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();
不可变数据结构
SharedVector
和 AtomicSharedVector
的行为类似于简单的不可变数据结构,是创建更复杂数据结构的好构建块。
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
作为一个非常轻量级的实验,旨在在共享向量之上创建自定义不可变数据结构,示例文件夹中有一个非常简单的分块向量实现。
就像向量类型一样,“分块向量”有三种形式:ChunkVector
、SharedChunkVector
、AtomicSharedChunkVector
。
它们在内部表示为引用计数的表,该表包含引用计数的内存块(或“块”)。在上面的插图上,两个分块向量指向同一个表,而另一个指向不同的表,但仍共享一些存储块。在实际应用中,分块向量类型仅比 SharedVector<SharedVector<T>>
略微复杂一些。
限制
- 这些向量类型最多可以容纳
u32::MAX
个元素。
许可
根据以下任一许可授权
- Apache License,版本 2.0(LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
- MIT 许可证(LICENSE-MIT 或 http://opensource.org/licenses/MIT)
贡献
请参阅 贡献指南。
依赖项
~260KB