【译】Rust与智能指针

MikeLoveRust

发布于 2020-10-26 10:55:14

1K0

发布于 2020-10-26 10:55:14

原文链接：https://dev.to/imaculate3/that-s-so-rusty-smart-pointers-245l 原文标题：That's so Rusty!: Smart pointers 公众号：Rust碎碎念译者：Praying

如果你一直在订阅这个系列，关于所有权的那篇文章[1]可能给你带来了这种印象——Rust 确实是个好东西，C++不应该在生产环境中使用。智能指针可能会改变你的想法。用现代的话来说，Smart pointers 是指那些有点（嗯......）额外(东西)的指针。他们本质上还是管理其所指向的对象的内存地址，并且当对象不再被使用的时候会将其释放。这消除了很多因不恰当的内存管理而引起的 bug，并使得编程不再那么枯燥乏味。C++智能指针为原始指针提供了一个安全的替代方案，而 Rust 智能指针则在保证安全的前提下扩展了语言功能。

智能指针可以像普通指针一样被解引用，但是在赋值（assignment）和析构（deallocation）时会表现出不同的行为。因此，有不同类型的智能指针。在本文中，我们将会探讨它们如何被用于实现各种链表：

单链表
共享链表
双链表

简单链表

链表是一个节点的线性集合，在链表中，每个节点指向下一个节点。在一个单链表中，每个节点有它自己的数据和指向下一个节点的指针，最后一个节点指向 NULL 表示链表结尾。

Rust

在 Rust 中，一个单链表节点可以定义如下：

struct Node {
    value: i32,
    next: Node,
}

但是它会因各种原因而无法编译。首先，因为next可以是 NULL，所以next应该是一个Option<Node>，（Option 中的 NULL）相当于 Rust 中的 NULL。此外，Rust 结构体在编译时必须是确定性大小的。如果Option<Node>是Node的一个字段，Node的大小可能和链表的长度一样长，也有可能是无限长的。为了解决这个问题，指针就派上用场了，因为它们拥有有限的大小，毕竟它们只是地址。最直观的智能指针是 Box(Box<T>)。它在堆上分配数据，并且当它离开作用域的时候，指针和其指向的数据都会被丢弃(drop)。在赋值时，Box 遵循 Rust 的所有权规则；在赋值时，数据和指针的所有权都被移动(move)。把next类型改为Box<Option<T>>，准确地抓住了一个节点的本质。下面的例子展示了两个节点是如何被单向链接为一个链表的：

struct Node {
    value: i32,
    next: Box<Option<Node>>,
}

fn main() {
    let a = Node {
        value: 5,
        next: Box::new(None),
    };
    let b = Node {
        value: 10,
        next: Box::new(Some(a)),
    };
    println!("b is {:?}", b);
    // println!("a is {:?}", a);
}

它可以成功运行，但是如果没有注释最后的打印语句会导致编译错误，因为a在当它被赋予b.next的时候被移动（move）了。

C++

C++中与 Box 等价的是 unique pointer。顾名思义，unique pointer 显式地拥有对象，当达到析构条件时，它会删除被管理的对象而不管其它指向该对象的指针。出于这个原因，应该只有一个 unique pointer 管理一个对象。如果要把一个对象赋值给另一个 unique pointer，这个指针就必须要被移动（move）;所有权被转移并且先前的指针就是无效的了。听起来很熟悉？是的，因为 Rust 的所有权系统也有类似的行为。C++ unique pointer 能提供类似的好处，但是他们不能提供编译期的内存安全保证；对一个无效的指针进行解引用会在运行时出错。下面是一个通过 unique pointer 来实现链表节点的例子:

#include <iostream>
#include <memory>
#include <utility>
using namespace std;

struct Node
{
    int value;
    unique_ptr<Node> next;
};

void printNode(unique_ptr<Node> n)
{
    if (n != nullptr)
    {
        cout << "value: " << n->value << ", ";
        printNode(move(n->next));
    }
    cout << '\n';
}

int main()
{
    Node a{5, nullptr};
    unique_ptr<Node> upA(&a);
    Node b{10, move(upA)};
    unique_ptr<Node> upB(&b);
    printNode(move(upB));
    // printNode(move(upA));
}

实现printNode()是因为 C++不能像 Rust 那样生成toStirng()实现。unique pointerupA被移动（move)以赋值给节点 b 的next，这些指针在传递给函数的时候也必须被移动（move）。因为upA是 null，所以没有注释最后一条 print 语句会导致一个段错误。

共享链表（Shared linked list）

在共享链表中，两个或以上的链表共享一个或多个节点。下图展示了一个示例，在该示例中，节点 C-D 被两个分别以 A 和 B 开始的链表共享。

Rust

为了支持共享链表，节点必须能够有多个所有者。我们能将 Box 用于这类链表么？

#[derive(Debug)]
struct Node {
    value: i32,
    next: Box<Option<Node>>,
}

fn main() {
    let a = Node {
        value: 5,
        next: Box::new(None),
    };
    let b = Node {
        value: 10,
        next: Box::new(Some(a)),
    };
    println!("b is {:?}", b);
    let c = Node {
        value: 20,
        next: Box::new(Some(a)),
    };
}

编译器不会同意因为，Box 只能有一个所有者。

为了支持多个所有者，Rust 有引用计数智能指针，缩写为Rc<T>。Rc<T>指针通过 clone 来共享，clone 操作会创建一份（Rc的）拷贝，这份拷贝指向相同的数据并增加引用计数。当这些指针失效时，引用计数会减少。

为了让节点可以共享，next的类型从Box<Option<Node>>> 变更为 Rc<Option<Node>>。这个变化证明了定义另一个结构体——SharedNode 以区分简单节点的合理性。a中的节点通过b和c克隆它的智能指针来共享。这一次，编译器是满意的。

#[derive(Debug)]
struct SharedNode {
    value: i32,
    next: Rc<Option<SharedNode>>,
}

use std::rc::Rc;

fn main() {
    let a = Rc::new(Some(SharedNode {
        value: 5,
        next: Rc::new(None),
    }));
    let b = SharedNode {
        value: 10,
        next: Rc::clone(&a),
    };
    let c = SharedNode {
        value: 20,
        next: Rc::clone(&a),
    };
    println!("a is {:?}", a);
    println!("b is {:?}", b);
    println!("c is {:?}", c);
}

引用计数（ Reference counts）

使用函数Rc::strong_count()可以追踪引用计数是如何更新的。在下面的例子中，SharedNode 的引用数在 clone 它连接到节点 b 和 c 时增加，当 c 退出作用域时，引用数就会减少。

let a = Rc::new(Some(SharedNode {
  value: 5,
  next: Rc::new(None),
}));
println!("Rc count of a after creating a = {}", Rc::strong_count(&a));
let b = SharedNode {
  value: 10,
  next: Rc::clone(&a),
};
println!("Rc count of a after creating b = {}", Rc::strong_count(&a));
{
  let c = SharedNode {
      value: 20,
      next: Rc::clone(&a),
  };
  println!("Rc count of a after creating c = {}", Rc::strong_count(&a));
}
println!(
  "Rc count of a after c goes out of scope = {}",
  Rc::strong_count(&a)
);

变更（Mutation）

在可变性那篇文章[2]中，我们知道 Rust 不喜欢默认可变性，部分是因为多个可变引用会导致数据竞争（data races）和竞态条件(race conditions)。智能指针是可变的，这一点很重要，否则他们的功能会受限。为了弥补这一差距，Rust 提供了RefCell<T>——另一种类型的智能指针，该智能指针提供了内部可变性：一种通过将借用规则执行推迟到运行时来对不可变引用进行修改。内部可变性是有用的，但是因为引用是在运行时被分析的，相较于编译期分析，它可能会导致不安全的代码在运行时炸开并且引起性能衰退。下面的例子演示了Rc<T>和Box<T>类型如何被变更。RefCell<T>有 borrow_mut()函数，该函数返回一个可变的智能指针RefMut<T>，该指针可以被解引用（使用*操作符）和变更。借用规则仍然适用，因此，如果在同一个作用域中使用了多个 RefCell<T>，程序将在运行时发生 panic。

#[derive(Debug)]
struct Node {
    value: i32,
    next: Box<RefCell<Option<Node>>>,
}

#[derive(Debug)]
struct SharedNode {
    value: i32,
    next: Rc<RefCell<Option<SharedNode>>>,
}
use crate::List::{Cons, Nil};
use std::cell::RefCell;
use std::rc::Rc;
fn main() {
    println!("Mutating node");
    let node_a = Node {
        value: 5,
        next: Box::new(RefCell::new(None)),
    };
    let a = Box::new(RefCell::new(Some(node_a)));
    let b = Node { value: 10, next: a };
    println!("Before mutation b is {:?}", b);

    if let Some(ref mut x) = *b.next.borrow_mut() {
        (*x).value += 10;
    }
    println!("After mutation b is {:?}", b);

    println!("Mutating shared node ...");
    let node_a = SharedNode {
        value: 5,
        next: Rc::new(RefCell::new(None)),
    };
    let a = Rc::new(RefCell::new(Some(node_a)));

    let b = SharedNode {
        value: 10,
        next: Rc::clone(&a),
    };
    let c = SharedNode {
        value: 20,
        next: Rc::clone(&a),
    };
    println!("Before mutation a is {:?}", a);
    println!("Before mutation b is {:?}", b);
    println!("Before mutation c is {:?}", c);

    if let Some(ref mut x) = *a.borrow_mut() {
        (*x).value += 10;
    }

    println!("After mutation a = {:?}", a);
    println!("After mutation b = {:?}", b);
    println!("After mutation c = {:?}", c);
}

C++

在 C++中与RC<T>等价的是 shared pointer。它有相似的引用计数行为并且变更(mutation)更加简单。下面的代码片段展示它是如何被用于创建共享链表：

#include <iostream>
#include <memory>
#include <utility>
using namespace std;

struct SharedNode
{
    int value;
    shared_ptr<SharedNode> next;
};

void printSharedNode(shared_ptr<SharedNode> n)
{
    if (n != nullptr)
    {
        cout << "value: " << n->value << " -> ";
        printSharedNode(n->next);
    }
    cout << '\n';
}

int main()
{
    SharedNode node_a{5, nullptr};
    shared_ptr<SharedNode> a(&node_a);
    cout << "Reference count of a: " << a.use_count() << endl;
    SharedNode node_b{10, a};
    shared_ptr<SharedNode> b(&node_b);
    cout << "Reference count of a, after linking to b: " << a.use_count() << endl;
    SharedNode node_c{20, a};
    shared_ptr<SharedNode> c(&node_c);
    cout << "Reference count of a, after linking to c: " << a.use_count() << endl;

    // mutation
    a->value = 2;

    printSharedNode(a);
    printSharedNode(b);
    printSharedNode(c);

    a.reset();
    cout << "Reference count of a on reset: " << a.use_count() << endl;
    // cout << " a is " << a->value << endl;
}

输出如下：

尽管 shared pointer 用起来更加简单，但是它也不能避免 C++的安全问题。未注释上面最后一条打印语句会导致运行时的段错误。

双链表

在一个双链表中，每个节点都有两个指针分别指向下一个节点和前一个节点。因此，一个双链表节点有prev字段，类型和next相同。

Rust

使用之前我们用过的指针可以创建名为DoubleNode的双链表。设置和更新prev和next字段需要内部可变性，因此需要RefCell<T>。为了让DoubleNode能够被下一个节点和前一个节点所拥有，我们将会使用Rc<T>。两端节点prev和next字段是可能为空的，所以我们将使用Option<DoubleNode>。因此，prev和next字段的类型就变成了 Rc<RefCell<Option<DoubleNode>>>。

简单起见，我们创建一个链表，该链表有两个节点node_a和node_b以及它们对应的指针a和b。node_b创建时带有a的一个 clone 副本（next 字段），作为a的下一个节点，并使用内部可变性，node_a的前一个节点指向node_b。这些都在下面的代码中被实现，代码中在链接节点之前和之后都会打印出节点信息和引用计数。

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct DoubleNode {
    value: i32,
    next: Rc<RefCell<Option<DoubleNode>>>,
    prev: Rc<RefCell<Option<DoubleNode>>>,
}

fn main() {
    let node_a = DoubleNode {
        value: 5,
        next: Rc::new(RefCell::new(None)),
        prev: Rc::new(RefCell::new(None)),
    };
    let a = Rc::new(RefCell::new(Some(node_a)));
    let node_b = DoubleNode {
        value: 10,
        next: Rc::clone(&a),
        prev: Rc::new(RefCell::new(None)),
    };
    let b = Rc::new(RefCell::new(Some(node_b)));

    println!(
        "Before linking a is {:?}, rc count is {}",
        a,
        Rc::strong_count(&a)
    );
    println!(
        "Before linking b is {:?}, rc count is {}",
        b,
        Rc::strong_count(&b)
    );

    if let Some(ref mut x) = *a.borrow_mut() {
        (*x).prev = Rc::clone(&b);
    }

    println!("After linking a rc count is {}", Rc::strong_count(&a));
    //println!("After linking a is {:?}", a);
    println!("After linking b rc count is {}", Rc::strong_count(&b));
    //println!("After linking b is {:?}", b);
}

这段代码可以正常编译运行，但是当最后两行被注释的打印语句取消注释后，输出结果就变得有趣了。

对任何一个节点的打印都会无限循环，然后导致栈溢出。这是因为要从一个节点中导出字符串，我们就要展开它所有的字段。要打印node_a，我们打印它的字段：value（5），next（None）和prev（node_b)，prev指向一个DoubleNode，因此我们以类似的方式打印它：value（10），next（node_a）和prev（None)，next指向DoubleNode，所以我们将其展开，返回的操作继续打印node_a，这个循环就会永久持续下去。这是一个结果表现为堆栈溢出的循环引用的例子。循环引用的另一个结果是内存泄漏，当内存没有被释放时，就会发生内存泄漏。当成功运行上面的代码时，可以看出，指针a和指针b的引用计数都是 2。在 main 函数结尾，Rust 会试图丢弃b，这会使得node_b只剩下 1 个引用，即node_a的prev指针。这个引用计数会一直维持在 1，从而阻止node_b被丢弃。因此，两个节点都不会被丢弃，从而导致内存泄漏。因为上面的程序运行时间较短，操作系统会清理内存。在像服务器程序这种长期运行的程序中，内存泄漏更为严重。这是少数几个可以从 Rust 编译器中溜走的 bug。这意味着在 Rust 中就无法实现双链表了嘛？不，它可以通过另一种称为 weak pointer 的指针来实现。weak pointer 是这样一种指针，它持有一个对象的非拥有引用（non-owning reference），该对象由一个共享指针管理。标记为Weak<T>，weak pointer 类似于Rc<T>因为它们都可以共享所有权，但是 weak pointer 并不影响析构。下面的例子展示了它们是如何解决双链表的难题。

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Debug)]
struct DoubleNode {
  value: i32,
  next: Rc<RefCell<Option<DoubleNode>>>,
  prev: Weak<RefCell<Option<DoubleNode>>>,
}

fn main() {
  let node_a = DoubleNode {
      value: 5,
      next: Rc::new(RefCell::new(None)),
      prev: Weak::new(),
  };
  let a = Rc::new(RefCell::new(Some(node_a)));
  let node_b = DoubleNode {
      value: 10,
      next: Rc::clone(&a),
      prev: Weak::new(),
  };
  let b = Rc::new(RefCell::new(Some(node_b)));

  println!(
      "Before cycle a is {:?}, rc count is {}",
      a,
      Rc::strong_count(&a)
  );
  println!(
      "Before cycle b is {:?}, rc count is {}",
      b,
      Rc::strong_count(&b)
  );

  if let Some(ref mut x) = *a.borrow_mut() {
      (*x).prev = Rc::downgrade(&b);
  }

  println!(
      "After cycle a rc count is {}, weak count is {}",
      Rc::strong_count(&a),
      Rc::weak_count(&a)
  );
  println!("After cycle a is {:?}", a);
  println!(
      "After cycle b rc count is {}, weak count is {}",
      Rc::strong_count(&b),
      Rc::weak_count(&b)
  );
  println!("After cycle b is {:?}", b);
}

打印节点时没有出现栈溢出说明循环引用已经被移除了。

通过把prev指针改为 weak pointer 实现了这个目标。weak pointer 是通过对共享指针进行降级而不是对其 clone，并且它不会影响有效引用计数。

通过追踪引用计数，我们可以看到循环引用是如何被避免的。在对节点链接两次后，a有一个强计数 2，b 有一个强计数 1 和一个弱计数 1。在 main 函数结尾处，Rust 会尝试丢弃b，使node_b仅剩下一个弱计数 1。因为 weak pointer 不影响析构，所以这个节点会被丢弃。在node_b丢弃后，它对a的链接也被移除，从而将a的强计数降为 1。当a离开作用域时，node_a的强计数变为 0，从而可以被丢弃。本质上，循环引可以用通过减少某些引用的重要性被解决。这一点在输出中也很明显，在输出中，weak pointer 没有被展开，而仅仅是注释为(Weak)。

C++

在 C++中也有 weak pointer 与 Rust 中的相对应。它们以相同的方式用于避免循环引用。它们可以被用于实现双链表，如下面代码所示：

#include <iostream>
#include <memory>
#include <utility>
using namespace std;

struct DoubleNode
{
  int value;
  shared_ptr<DoubleNode> next;
  weak_ptr<DoubleNode> prev;
};


void printDoubleNode(shared_ptr<DoubleNode> n)
{
  if (n != nullptr)
  {
      cout << "value: " << n->value << ", prev: (Weak) ->";
      printDoubleNode(n->next);
  }
  cout << '\n';
}

int main()
{
  DoubleNode node_a{5, nullptr, weak_ptr<DoubleNode>()};
  shared_ptr<DoubleNode> a(&node_a);
  DoubleNode node_b{10, a, weak_ptr<DoubleNode>()};
  shared_ptr<DoubleNode> b(&node_b);
  cout << "Before linking, rc count of a: " << a.use_count() << endl;
  cout << "Before linking, rc count of b: " << b.use_count() << endl;
  printDoubleNode(a);
  printDoubleNode(b);

  a->prev = b;
  cout << "After linking, rc count of a: " << a.use_count() << endl;
  cout << "After linking, rc count of b: " << b.use_count() << endl;
  printDoubleNode(a);
  printDoubleNode(b);
}

下面的输出表明 weak pointer 没有影响引用计数。