c++如何判断无效指针_【译】Rust与智能指针

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

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

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

• 单链表
• 共享链表
• 双链表

简单链表

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

Rust

在 Rust 中&＃xff0c;一个单链表节点可以定义如下&＃xff1a;

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


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

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

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

C&＃43;&＃43;

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

#include 
#include 
#include 
using namespace std;

struct Node
{
    int value;
    unique_ptr next;
};void printNode(unique_ptr n){if (n !&＃61; nullptr)
    {cout <"value: "         printNode(move(n->next));
    }cout <&＃39;\n&＃39;;
}int main(){
    Node a{5, nullptr};unique_ptr upA(&a);
    Node b{10, move(upA)};unique_ptr upB(&b);
    printNode(move(upB));// printNode(move(upA));
}

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

共享链表(Shared linked list)

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

Rust

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

#[derive(Debug)]
struct Node {
    value: i32,
    next: Box,
}fn main() {let a &＃61; Node {
        value: 5,
        next: Box::new(None),
    };let b &＃61; Node {
        value: 10,
        next: Box::new(Some(a)),
    };println!("b is {:?}", b);let c &＃61; Node {
        value: 20,
        next: Box::new(Some(a)),
    };
}

编译器不会同意因为&＃xff0c;Box 只能有一个所有者。

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

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

#[derive(Debug)]
struct SharedNode {
    value: i32,
    next: Rc,
}use std::rc::Rc;fn main() {let a &＃61; Rc::new(Some(SharedNode {
        value: 5,
        next: Rc::new(None),
    }));let b &＃61; SharedNode {
        value: 10,
        next: Rc::clone(&a),
    };let c &＃61; SharedNode {
        value: 20,
        next: Rc::clone(&a),
    };println!("a is {:?}", a);println!("b is {:?}", b);println!("c is {:?}", c);
}

引用计数( Reference counts)

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

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


变更(Mutation)

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

#[derive(Debug)]
struct Node {
    value: i32,
    next: BoxOption>>,
}#[derive(Debug)]struct SharedNode {
    value: i32,
    next: RcOption>>,
}use crate::List::{Cons, Nil};use std::cell::RefCell;use std::rc::Rc;fn main() {println!("Mutating node");let node_a &＃61; Node {
        value: 5,
        next: Box::new(RefCell::new(None)),
    };let a &＃61; Box::new(RefCell::new(Some(node_a)));let b &＃61; Node { value: 10, next: a };println!("Before mutation b is {:?}", b);if let Some(ref mut x) &＃61; *b.next.borrow_mut() {
        (*x).value &＃43;&＃61; 10;
    }println!("After mutation b is {:?}", b);println!("Mutating shared node ...");let node_a &＃61; SharedNode {
        value: 5,
        next: Rc::new(RefCell::new(None)),
    };let a &＃61; Rc::new(RefCell::new(Some(node_a)));let b &＃61; SharedNode {
        value: 10,
        next: Rc::clone(&a),
    };let c &＃61; 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) &＃61; *a.borrow_mut() {
        (*x).value &＃43;&＃61; 10;
    }println!("After mutation a &＃61; {:?}", a);println!("After mutation b &＃61; {:?}", b);println!("After mutation c &＃61; {:?}", c);
}

C&＃43;&＃43;

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

#include 
#include 
#include 
using namespace std;

struct SharedNode
{
    int value;
    shared_ptr next;
};void printSharedNode(shared_ptr n){if (n !&＃61; nullptr)
    {cout <"value: "  ";
        printSharedNode(n->next);
    }cout <&＃39;\n&＃39;;
}int main(){
    SharedNode node_a{5, nullptr};shared_ptr a(&node_a);cout <"Reference count of a: "     SharedNode node_b{10, a};shared_ptr b(&node_b);cout <"Reference count of a, after linking to b: "     SharedNode node_c{20, a};shared_ptr c(&node_c);cout <"Reference count of a, after linking to c: "     a->value &＃61; 2;
    printSharedNode(a);
    printSharedNode(b);
    printSharedNode(c);
    a.reset();cout <"Reference count of a on reset: " }

输出如下&＃xff1a;

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

双链表

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

Rust

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

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

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

#[derive(Debug)]
struct DoubleNode {
    value: i32,
    next: RcOption>>,
    prev: RcOption>>,
}fn main() {let node_a &＃61; DoubleNode {
        value: 5,
        next: Rc::new(RefCell::new(None)),
        prev: Rc::new(RefCell::new(None)),
    };let a &＃61; Rc::new(RefCell::new(Some(node_a)));let node_b &＃61; DoubleNode {
        value: 10,
        next: Rc::clone(&a),
        prev: Rc::new(RefCell::new(None)),
    };let b &＃61; 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) &＃61; *a.borrow_mut() {
        (*x).prev &＃61; 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);
}

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

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

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

#[derive(Debug)]
struct DoubleNode {
  value: i32,
  next: RcOption>>,
  prev: WeakOption>>,
}fn main() {let node_a &＃61; DoubleNode {
      value: 5,
      next: Rc::new(RefCell::new(None)),
      prev: Weak::new(),
  };let a &＃61; Rc::new(RefCell::new(Some(node_a)));let node_b &＃61; DoubleNode {
      value: 10,
      next: Rc::clone(&a),
      prev: Weak::new(),
  };let b &＃61; 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) &＃61; *a.borrow_mut() {
      (*x).prev &＃61; 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&＃xff0c;并且它不会影响有效引用计数。

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

C&＃43;&＃43;

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

#include 
#include 
#include 
using namespace std;

struct DoubleNode
{
  int value;
  shared_ptr next;
  weak_ptr prev;
};void printDoubleNode(shared_ptr n){if (n !&＃61; nullptr)
  {cout <"value: " ";
      printDoubleNode(n->next);
  }cout <&＃39;\n&＃39;;
}int main(){
  DoubleNode node_a{5, nullptr, weak_ptr()};shared_ptr a(&node_a);
  DoubleNode node_b{10, a, weak_ptr()};shared_ptr b(&node_b);cout <"Before linking, rc count of a: "   printDoubleNode(a);
  printDoubleNode(b);
  a->prev &＃61; b;cout <"After linking, rc count of a: "   printDoubleNode(a);
  printDoubleNode(b);
}

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

除了语法上的差异&＃xff0c;Rust 智能指针看起来与 C&＃43;&＃43;非常相似。它们是为了解决类似的问题而设计的。Rust 智能指针维护了编译时的保证(除了循环引用)&＃xff0c;而 C&＃43;&＃43;智能指针更容易操作&＃xff0c;引用计数操作是线程安全的。你更喜欢哪个&＃xff1f;

参考资料

所有权的那篇文章: https://dev.to/imaculate3/that-s-so-rusty-ownership-493c

可变性那篇文章: https://dev.to/imaculate3/that-s-so-rusty-mutables-5b40