切片双端队列

一个可以解引用为切片的双端队列，也称为环形缓冲区或循环缓冲区。

优点

SliceDeque 的主要优点是

• 更好的API：因为它可以解引用为切片，所以所有适用于切片的操作（如 sort）对 SliceDeque 都“正常工作”。

• 高效：与切片一样高效（迭代、排序等），通常比 VecDeque 更高效。

平台支持

支持Windows、Linux、MacOS和其他所有类Unix操作系统（尽管可能未经测试）。以下目标已知可以正常工作并通过所有测试

Linux

• aarch64-unknown-linux-gnu
• arm-unknown-linux-gnueabi
• arm-unknown-linux-musleabi
• armv7-unknown-linux-gnueabihf
• armv7-unknown-linux-musleabihf
• i586-unknown-linux-gnu
• i686-unknown-linux-gnu
• i686-unknown-linux-musl
• mips-unknown-linux-gnu
• mips64-unknown-linux-gnuabi64
• mips64el-unknown-linux-gnuabi64
• mipsel-unknown-linux-gnu
• powerpc-unknown-linux-gnu
• powerpc64-unknown-linux-gnu
• powerpc64le-unknown-linux-gnu
• x86_64-unknown-linux-gnu
• x86_64-unknown-linux-musl
• aarch64-linux-android
• arm-linux-androideabi
• armv7-linux-androideabi
• x86_64-linux-android

MacOS X

• i686-apple-darwin
• x86_64-apple-darwin

Windows

• x86_64-pc-windows-msvc

缺点

SliceDeque 的主要缺点是

• “受限”的平台支持：操作系统必须支持虚拟内存。通常，如果你可以使用 std，你就可以使用 SliceDeque。

• 全局分配器绕过：SliceDeque绕过Rust的全局分配器/它自己的内存分配器，直接与操作系统通信。也就是说，分配和增长SliceDeque总是涉及系统调用，而由全局分配器支持的VecDeque可能无需任何系统调用即可收到分配器拥有的内存。

• 最小的容量受操作系统分配粒度限制：某些操作系统允许SliceDeque以4/8/64 kB块分配内存。

何时不应使用它？在我看来，如果

• 你需要针对#[no_std]，或者
• 你无法使用它（因为你的平台不支持它）

你必须使用其他东西。如果。

• 你的环形缓冲区非常小；

那么使用SliceDeque可能会以内存换取性能。另外，

• 如果你的应用程序有很多短生命周期的环形缓冲区；

设置和增长SliceDeque所需系统调用的成本可能不会被你的应用程序摊销（更新：有一个拉取请求在启用use_std功能时在线程局部堆中缓存分配，显著提高了短生命周期环形缓冲区的性能，但它尚未合并）。这些权衡是否有价值取决于应用程序，所以不要轻信我的话：要测量。

它的工作原理

标准库中的双端队列（VecDeque）是使用可增长环形缓冲区实现的（0表示未初始化内存，而T表示队列中的一个元素）

// [ 0 | 0 | 0 | T | T | T | 0 ]
//               ^:head  ^:tail

当队列增长超过已分配缓冲区的末尾时，其尾部会绕回

// [ T | T | 0 | T | T | T | T ]
//       ^:tail  ^:head

因此，VecDeque不能Deref到切片，因为其元素通常不占用连续的内存区域。这使得实现及其接口复杂化（例如，没有as_slice方法 - as_slices方法返回一对切片）并产生负面性能影响（例如，在遍历元素时需要考虑绕回）。

此crate提供SliceDeque，这是一个使用可增长虚拟环形缓冲区实现的双端队列。

虚拟环形缓冲区实现与在VecDeque中使用的实现非常相似。主要区别在于虚拟环形缓冲区将两个相邻的虚拟内存区域映射到同一物理内存区域。

// Virtual memory:
//
//  __________region_0_________ __________region_1_________
// [ 0 | 0 | 0 | T | T | T | 0 | 0 | 0 | 0 | T | T | T | 0 ]
//               ^:head  ^:tail
//
// Physical memory:
//
// [ 0 | 0 | 0 | T | T | T | 0 ]
//               ^:head  ^:tail

也就是说，上面的虚拟内存区域 0 和 1（顶部）映射到相同的物理内存（底部）。就像 VecDeque 一样，当队列增长超出分配的物理内存区域末端时，队列会环绕，新元素将继续附加到队列的开头。然而，由于 SliceDeque 将物理内存映射到两个相邻的内存区域，在虚拟内存空间中，队列保持了连续内存布局的错觉。

// Virtual memory:
//
//  __________region_0_________ __________region_1_________
// [ T | T | 0 | T | T | T | T | T | T | 0 | T | T | T | T ]
//               ^:head              ^:tail
//
// Physical memory:
//
// [ T | T | 0 | T | T | T | T ]
//       ^:tail  ^:head

由于许多操作系统的进程仅处理虚拟内存地址，将物理内存映射留给CPU内存管理单元（MMU），SliceDeque 能够在这些系统中 Deref 为切片。

这简化了 SliceDeque 的API和实现，在某些情况下使其性能优于 VecDeque。

一般来说，你可以将 SliceDeque 视为一个具有 O(1) pop_front 和摊销 O(1) push_front 方法的 Vec。