数组与切片
切片和数组是 Rust 中的特殊类型。它们表示同一类型任意值的序列。您还可以拥有多维切片或数组(即,切片的切片、数组的数组、数组的切片或数组的切片)。
切片是一种相对较新的编程概念,因为在讨论 Java、C、C++、Python 或 Ruby 语言语法中的序列时,你通常不会找到 slice(切片) 这个术语。通常,序列被称为数组(如Java、C、C++ 和 Ruby)、列表(如 Python)或简单序列(如 Scala)。其他语言可能提供等效的行为,但切片不一定像 Rust 或 Go 中把其当做一等语言概念或类型(尽管 slice 抽象在其他语言中越来越流行)。C++确实有 std::span
和 std::string_view
,它们提供等效的行为,但在描述这些时,C++不使用 slice 这个术语。
注意术语切片应该是起源于 Go 语言,正如 Rob Pike 在 2013 年的一篇博客文章中所描述的那样:https://go.dev/blog/slices。
具体来说,在 Rust 中,切片和数组有着微妙的区别。数组是固定长度的值序列,而切片是任意长度的值序列。也就是说,切片可以是可变长度的,在运行时确定,而数组在编译时已知固定长度。切片还有另一个有趣的属性,即您可以将切片拆分为任意多个不重叠的子切片;这可以方便地实现使用分治或递归策略的算法。
在 Rust 中,有时与数组一起工作可能会很棘手,因为要在编译时间知道序列的长度,需要在编译时间将信息传递给编译器,并在类型签名中提供该信息。在 Rust 1.51 中,可以使用 const generics 来定义任意长度的泛型数组,但只能在编译期使用。
让我们用下面的代码来说明切片和数组之间的区别。
let array = [0u8; 64]; // ❶
let slice: &[u8] = &array; // ❷
- ❶ 这里的类型签名是
[0u8; 64]
,一个以零初始化的数组。 - ❷ 从数组中借用一部分。
在这段代码中,我们初始化了一个包含 64 个元素的字节数组,所有元素都是 0。0u8
是无符号整型数字 0 的简写,长度为 8 位,值为 0。0 是值,u8 是类型。
在第二行中,我们将数组作为切片进行借用。到目前为止,这还没有什么特别有趣的地方。你可以使用切片做一些稍微更有趣的事情,比如借用两次:
let (first_half, second_half) = slice.split_at(32); //❶
println!(
"first_half.len()={} second_half.len()={}",
first_half.len(),
second_half.len()
);
- ❶ 分割并借用一个切片两次,将其解构为两个不重叠的子切片
上面的代码调用了split_at()
函数,该函数是 Rust 核心库的一部分,适用于所有切片、数组和Vector。split_at()
函数解构了切片(已经从数组中借用),并返回两个不重叠的切片,分别对应于原始数组的前半部分和后半部分。
在 Rust 中,解构的概念非常重要,因为您可能会发现自己需要借用数组或切片的一部分。事实上,您可以使用此模式多次借用相同的切片或数组,因为切片不会重叠。一个常见的用例是解析或解码文本或二进制数据。例如:
let wordlist = "one,two,three,four";
for word in wordlist.split(‘,’) {
println!("word={}", word);
}
观察前面的代码,我们可能立刻就会明白,我们获取了一个字符串,用逗号将其分割,然后打印了该字符串中的每个单词。这段代码的输出如下:
word=one
word=two
word=three
word=four
上述代码值得注意的一点是,没有发生堆分配。所有内存都是在编译时已知固定长度的栈上分配的,没有在幕后调用 malloc()
。这相当于使用原始的 C 指针,没有引用计数或垃圾回收;因此,没有开销。与 C 指针不同,代码简洁、安全,而且没有过于冗长。
此外,切片还有许多针对内存连续区域的优化方法。其中一种优化方法是copy_from_slice()
方法,它适用于切片。从标准库中调用 copy_from_slice()
方法时,会使用 memcpy()
函数复制内存,如下所示。
pub fn copy_from_slice(&mut self, src: &[T])
where
T: Copy,
{
// ......
// SAFETY: `self` is valid for `self.len()` elements by definition, and `src` was
// checked to have the same length. The slices cannot overlap because
// mutable references are exclusive.
unsafe {
ptr::copy_nonoverlapping(src.as_ptr(), self.as_mut_ptr(), self.len());
}
}
在前面的列表中,来自 Rust 核心库的 ptr::copy_nonoverlapping()
只是 C 库 memcpy()
的包装器。在某些平台上,memcpy()
具有比您可能能够使用常规代码实现的更多优化。其他经过优化的函数是 fill()
和 fill_with()
,它们都使用 memset()
来填充内存。
总结
- 数组是一个固定长度的值序列,在编译时已知其值。
- 切片是内存相邻区域的指针,包括一个长度,表示任意长度的值序列。
- 切片和数组都可以递归地解构为不重叠的子切片。
Vector
可以这么说,Vector 是 Rust 中最重要的数据类型(其次是基于 Vector的 String 类型)。在 Rust 中处理数据时,如果你需要一个可调整大小的值序列,你会发现自己经常创建 Vector。如果你来自 C++,你以前可能听说过 Vector 这个术语,在许多方面,Rust 的 Vector 类型与你在 C++ 中看到的非常相似。Vector 是一种通用的容器,可用于存储几乎任何类型的序列。
Vector 是 Rust 中在堆上分配内存的方式之一(另一种方式是像 Box 这样的智能指针)。Vector 有一些内部优化来限制过度分配,例如以块的形式分配内存。此外,在 nightly Rust 中,您可以提供一个自定义分配器,以实现您自己的内存分配行为。
深入研究 Vector
Vec
继承了 Slice 的方法,因为我们可以从 Vec
得到一个 Slice 的引用。Rust 没有面向对象编程意义上的继承,但是 Vec
是一个特殊的类型,它同时是一个 Vec
和一个 Slice。例如,让我们看看标准库中 as_slice()
的实现。
pub fn as_slice(&self) -> &[T] {
self
}
上面的代码清单执行了一个特殊的转换(在正常情况下)不会起作用。它接受 self
,也就是上面的代码中的 Vec<T>
,然后简单地将它作为 &[T]
返回。如果你自己尝试编译相同的代码,它会失败。
这是如何实现的?Rust 提供了一个名为 Deref
(及其可变版本 DerefMut
)的trait,编译器可以隐式地将一个类型强制转换为另一个类型。一旦为给定类型实现Deref
,该类型也将自动实现 dereferenced 类型的所有方法。在 Vec
的情况下,Deref
和 DerefMut
是在 Rust 标准库中实现的,如下所示。
impl<T, A: Allocator> ops::Deref for Vec<T, A> {
type Target = [T];
fn deref(&self) -> &[T] {
unsafe { slice::from_raw_parts(self.as_ptr(), self.len) }
}
}
impl<T, A: Allocator> ops::DerefMut for Vec<T, A> {
fn deref_mut(&mut self) -> &mut [T] {
unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) }
}
}
在前面的代码清单中,解引用Vec会将它从原始指针和长度强制转换为切片。需要注意的是,这种操作是暂时的——也就是说,切片不能重新调整大小,解引用时向切片提供的长度是固定的。
如果由于某种原因,您从Vec
中取出一部分并调整Vec
的大小,则切片的大小不会改变。然而,这只有在不安全代码中才有可能,因为借用检查器不会允许您同时借用Vec
中的切片并更改Vec
。以下面的例子来说明:
let mut vec = vec![1, 2, 3];
let slice = vec.as_slice(); // ❶
vec.resize(10, 0); // ❷
println!("{}", slice[0]); // ❸
- ❶ 返回
&[i32]
,因为这里借用了vec - ❷ 这是一个可变操作。
- ❸ 这无法编译。
上面的代码将无法编译,因为借用检查器会返回这个错误:
error[E0502]: cannot borrow `vec` as mutable because it is also borrowed as
immutable
--> src/main.rs:4:5
|
3 | let slice = vec.as_slice();
| --- immutable borrow occurs here
4 | vec.resize(10, 0);
| ^^^^^^^^^^^^^^^^^ mutable borrow occurs here
5 | println!("{}", slice[0]);
| -------- immutable borrow later used here
包装Vec
Rust 中的某些类型只是包装了 Vec
,例如 String
。String
类型是 Vec<u8>
,解引用(使用前面提到的 Deref
trait)为 str
。
pub struct String {
vec: Vec<u8>,
}
包装Vec
是一种常见的模式,因为 Vec
是实现可调整大小的任何类型序列的首选方式。
与Vector相关的类型
在 90% 的情况下,您需要使用 Vec
。在另外 10% 的情况下,您可能需要使用HashMap
。在某些情况下,或者在您需要特殊优化的情况下,Vec
或 HashMap
以外的容器类型可能是合理的,但大多数情况下,使用 Vec
将绰绰有余,而使用其他类型不会提供明显的性能改进。
如果您担心分配的连续内存区域过大,或者担心内存的位置,您可以通过简单地将Box
塞入 Vec
(即使用 Vec<Box<T>>
)来轻松解决这个问题。话虽如此,Rust 标准库中还有其他几种集合类型,其中一些在内部包装了 Vec
,您可能偶尔需要使用它们:
VecDeque
: 基于Vec
的可调整大小的双端队列LinkedList
: 双向链表HashMap
: 哈希表BTreeMap
: 基于B树的映射HashSet
: 基于 HashMap 的哈希集BTreeSet
: 基于 BTreeMap 的 B 树集BinaryHeap
: 使用二叉堆实现的优先队列,内部使用 Vec。
其他Rust 核心数据结构的最新性能细节,可以在 Rust 标准库集合参考中找到,网址为 https://doc.rust-lang.org/std/collections/index.html。
Maps
HashMap
是你在 Rust 中会经常使用的另一种容器类型。如果说 Vec
是 Rust 语言中首选的可调整大小的类型,那么 HashMap
就是在需要使用键按常量时间获取集合的情况下的首选类型。Rust 的 HashMap
与你在其他语言中遇到过的哈希表没有太大区别,但得益于 Rust 提供的一些优化,Rust 的实现可能比你在其他库中找到的实现更快、更安全。
HashMap
使用 Siphash-1-3 函数进行散列,该函数也用于 Python(从 3.4 开始)、Ruby、Swift 和 Haskell。该函数为常见情况提供了良好的折衷,但对于非常小的或非常大的键,如整数类型或非常大的字符串,它可能是不合适的。
您还可以为 HashMap
提供自己的哈希函数。在您想要对非常小的或非常大的键进行哈希的情况下,您可能需要这样做,但对于大多数情况来说,默认实现是足够的。
自定义哈希函数
要使用具有自定义哈希函数的 HashMap
,您需要首先找到现有实现或编写一个实现必要属性的哈希函数。HashMap
要求为要使用的哈希函数实现std::hash::BuildHasher
、std::hash::Hasher
和 std::default::Default
。
让我们从以下列表中检查标准库中HashMap
的实现。
impl<K, V, S> HashMap<K, V, S>
where
K: Eq + Hash,
S: BuildHasher,
{
// ......
}
在这个列表中,你可以看到 BuildHasher
被指定为 S
类型参数上的一个 trait 要求。再深入一点,在下面的列表中,你可以看到 BuildHasher
只是围绕 Hasher
trait 的包装器。
pub trait BuildHasher {
/// Type of the hasher that will be created.
type Hasher: Hasher; // 这里对 Hasher 特性有要求。
// ......
}
BuildHasher
和 Hasher
API 将大部分实现细节留给了散列函数的作者。对于BuildHasher
,只需要一个 build_hasher()
方法,该方法返回新的 Hasher
实例。Hasher
特性只需要两个方法:write()
和 finish()
。write()
接受一个字节切片(&[u8]
),finish()
返回一个表示计算哈希值的无符号 64 位整数。Hasher
特性还提供了一些通用的实现,如果你实现了 Hasher 特性,就可以免费继承这些实现。https://doc.rust-lang.org/std/hash/trait.BuildHasher.html 和 https://doc.rust-lang.org/std/hash/trait.Hasher.html 上的散列特性的文档值得一看,以便更清楚地了解它们的工作原理。
https://crates.io 上有很多现成的实现各种哈希函数的 crate。例如,在下面的列表中,让我们使用 J. Andrew Rogers 设计的 MetroHash 构建一个 HashMap,MetroHash 是 SipHash 的替代品,详情请见https://www.jandrewrogers.com/2015/05/27/metrohash/。MetroHash crate 已经包含了 std::hash::BuildHasher
和 std::hash::Hasher
特性的必要实现,这使事情变得非常简单。
use metrohash::MetroBuildHasher;
use std::collections::HashMap;
// 使用 MetroHash 创建一个新的 HashMap 实例
let mut map = HashMap::<String, String, MetroBuildHasher>::default();
// 将键和值对插入到map中,使用 `Into` 特性将 `&str` 转换为 `String`
map.insert("hello?".into(), "Hello!".into());
// 从map中检索值,它返回一个 Option
// println! 宏的 {:?} 参数告诉它使用fmt::Debug trait 格式化此值。
println!("{:?}", map.get("hello?"));
创建可哈希类型
HashMap
可以使用任意键和值,但键必须实现 std::cmp::Eq
和 std::hash::Hash
特性。许多特性,如 Eq
和 Hash
,可以使用 #[derive]
属性自动导出。考虑以下示例。
#[derive(Hash, Eq, PartialEq, Debug)]
struct CompoundKey {
name: String,
value: i32,
}
上面的代码表示一个由name
和value
组成的结构体。我们使用 #[derive]
属性来推导四个Trait: Hash
、Eq
、PartialEq
和 Debug
。虽然 HashMap
只需要 Hash
和 Eq
,但我们还需要推导 PartialEq
,因为 Eq
依赖于 PartialEq
。我们还推导了 Debug
,它提供了自动调试打印方法。这对调试和测试代码非常方便。
以上内容来自Brenden Matthews的书籍《Code Like a Pro in Rust》