数组与切片

切片和数组是 Rust 中的特殊类型。它们表示同一类型任意值的序列。您还可以拥有多维切片或数组(即,切片的切片、数组的数组、数组的切片或数组的切片)​。

切片是一种相对较新的编程概念,因为在讨论 Java、C、C++、Python 或 Ruby 语言语法中的序列时,你通常不会找到 slice(切片) 这个术语。通常,序列被称为数组(如Java、C、C++ 和 Ruby)​、列表(如 Python)或简单序列(如 Scala)​。其他语言可能提供等效的行为,但切片不一定像 Rust 或 Go 中把其当做一等语言概念或类型(尽管 slice 抽象在其他语言中越来越流行)​。C++确实有 std::spanstd::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 的情况下,DerefDerefMut 是在 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,例如 StringString 类型是 Vec<u8>,解引用(使用前面提到的 Deref trait)为 str

pub struct String {
    vec: Vec<u8>,
}

包装Vec是一种常见的模式,因为 Vec 是实现可调整大小的任何类型序列的首选方式。

与Vector相关的类型

在 90% 的情况下,您需要使用 Vec。在另外 10% 的情况下,您可能需要使用HashMap​。在某些情况下,或者在您需要特殊优化的情况下,VecHashMap 以外的容器类型可能是合理的,但大多数情况下,使用 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::BuildHasherstd::hash​::Hasherstd::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 特性有要求。
 
    // ......
}

BuildHasherHasher API 将大部分实现细节留给了散列函数的作者。对于BuildHasher,只需要一个 build_hasher() 方法,该方法返回新的 Hasher 实例。Hasher 特性只需要两个方法:write()finish()​。write() 接受一个字节切片(&[u8]​)​,finish() 返回一个表示计算哈希值的无符号 64 位整数。Hasher 特性还提供了一些通用的实现,如果你实现了 Hasher 特性,就可以免费继承这些实现。https://doc.rust-lang.org/std/hash/trait.BuildHasher.htmlhttps://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​:​:​BuildHasherstd​:​:​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::Eqstd​:​:​hash​:​:​Hash 特性。许多特性,如 EqHash,可以使用 #[derive] 属性自动导出。考虑以下示例。

#[derive(Hash, Eq, PartialEq, Debug)]
struct CompoundKey {
    name: String,
    value: i32,
}

上面的代码表示一个由namevalue组成的结构体。我们使用 #[derive] 属性来推导四个Trait: HashEqPartialEqDebug。虽然 HashMap 只需要 HashEq,但我们还需要推导 PartialEq,因为 Eq 依赖于 PartialEq。我们还推导了 Debug,它提供了自动调试打印方法。这对调试和测试代码非常方便。

以上内容来自Brenden Matthews的书籍《Code Like a Pro in Rust》