You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

471 lines
21 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

<!DOCTYPE HTML>
<html lang="zh-CN" class="light sidebar-visible" dir="ltr">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>最后实现 - Rust语言圣经(Rust Course)</title>
<!-- Custom HTML head -->
<meta name="description" content="">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="theme-color" content="#ffffff">
<link rel="icon" href="../../favicon.svg">
<link rel="shortcut icon" href="../../favicon.png">
<link rel="stylesheet" href="../../css/variables.css">
<link rel="stylesheet" href="../../css/general.css">
<link rel="stylesheet" href="../../css/chrome.css">
<link rel="stylesheet" href="../../css/print.css" media="print">
<!-- Fonts -->
<link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
<link rel="stylesheet" href="../../fonts/fonts.css">
<!-- Highlight.js Stylesheets -->
<link rel="stylesheet" id="highlight-css" href="../../highlight.css">
<link rel="stylesheet" id="tomorrow-night-css" href="../../tomorrow-night.css">
<link rel="stylesheet" id="ayu-highlight-css" href="../../ayu-highlight.css">
<!-- Custom theme stylesheets -->
<link rel="stylesheet" href="../../theme/style.css">
<!-- Provide site root and default themes to javascript -->
<script>
const path_to_root = "../../";
const default_light_theme = "light";
const default_dark_theme = "navy";
</script>
<!-- Start loading toc.js asap -->
<script src="../../toc.js"></script>
</head>
<body>
<div id="body-container">
<!-- Work around some values being stored in localStorage wrapped in quotes -->
<script>
try {
let theme = localStorage.getItem('mdbook-theme');
let sidebar = localStorage.getItem('mdbook-sidebar');
if (theme.startsWith('"') && theme.endsWith('"')) {
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
}
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
}
} catch (e) { }
</script>
<!-- Set the theme before any content is loaded, prevents flash -->
<script>
const default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? default_dark_theme : default_light_theme;
let theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
const html = document.documentElement;
html.classList.remove('light')
html.classList.add(theme);
html.classList.add("js");
</script>
<input type="checkbox" id="sidebar-toggle-anchor" class="hidden">
<!-- Hide / unhide sidebar before it is displayed -->
<script>
let sidebar = null;
const sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
} else {
sidebar = 'hidden';
}
sidebar_toggle.checked = sidebar === 'visible';
html.classList.remove('sidebar-visible');
html.classList.add("sidebar-" + sidebar);
</script>
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
<!-- populated by js -->
<mdbook-sidebar-scrollbox class="sidebar-scrollbox"></mdbook-sidebar-scrollbox>
<noscript>
<iframe class="sidebar-iframe-outer" src="../../toc.html"></iframe>
</noscript>
<div id="sidebar-resize-handle" class="sidebar-resize-handle">
<div class="sidebar-resize-indicator"></div>
</div>
</nav>
<div id="page-wrapper" class="page-wrapper">
<div class="page">
<div id="menu-bar-hover-placeholder"></div>
<div id="menu-bar" class="menu-bar sticky">
<div class="left-buttons">
<label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
<i class="fa fa-bars"></i>
</label>
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
<i class="fa fa-paint-brush"></i>
</button>
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
<li role="none"><button role="menuitem" class="theme" id="default_theme">Auto</button></li>
<li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
</ul>
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
<i class="fa fa-search"></i>
</button>
</div>
<h1 class="menu-title">Rust语言圣经(Rust Course)</h1>
<div class="right-buttons">
<a href="../../print.html" title="Print this book" aria-label="Print this book">
<i id="print-button" class="fa fa-print"></i>
</a>
<a href="https://github.com/sunface/rust-course" title="Git repository" aria-label="Git repository">
<i id="git-repository-button" class="fa fa-github"></i>
</a>
<a href="https://github.com/sunface/rust-course/edit/main/src/too-many-lists/bad-stack/final-code.md" title="Suggest an edit" aria-label="Suggest an edit">
<i id="git-edit-button" class="fa fa-edit"></i>
</a>
</div>
</div>
<div id="search-wrapper" class="hidden">
<form id="searchbar-outer" class="searchbar-outer">
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
</form>
<div id="searchresults-outer" class="searchresults-outer hidden">
<div id="searchresults-header" class="searchresults-header"></div>
<ul id="searchresults">
</ul>
</div>
</div>
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
<script>
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
</script>
<div id="content" class="content">
<main>
<h1 id="一些收尾工作以及最终代码"><a class="header" href="#一些收尾工作以及最终代码">一些收尾工作以及最终代码</a></h1>
<p>在之前的章节中,我们完成了 Bad 单链表栈的数据定义和基本操作,下面一起来写一些测试代码。</p>
<h2 id="单元测试"><a class="header" href="#单元测试">单元测试</a></h2>
<blockquote>
<p>关于如何编写测试,请参见<a href="https://course.rs/test/write-tests.html">自动化测试章节</a></p>
</blockquote>
<p>首先,单元测试代码要放在待测试的目标代码旁边,也就是同一个文件中:</p>
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>// in first.rs
#[cfg(test)]
mod test {
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop(), None);
// Populate list
list.push(1);
list.push(2);
list.push(3);
// Check normal removal
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push(4);
list.push(5);
// Check normal removal
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), Some(4));
// Check exhaustion
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), None);
}
}
<span class="boring">}</span></code></pre></pre>
<p><code>src/first.rs</code> 中添加以上测试模块,然后使用 <code>cargo test</code> 运行相关的测试用例:</p>
<pre><code class="language-shell">$ cargo test
error[E0433]: failed to resolve: use of undeclared type or module `List`
--&gt; src/first.rs:43:24
|
43 | let mut list = List::new();
| ^^^^ use of undeclared type or module `List`
</code></pre>
<p>Ooops! 报错了,从错误内容来看,是因为我们在一个不同的模块 <code>test</code> 中,引入了 <code>first</code> 模块中的代码,由于前者是后者的子模块,因此可以使用以下方式引入 <code>first</code> 模块中的 <code>List</code> 定义:</p>
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>#[cfg(test)]
mod test {
use super::List;
// 其它代码保持不变
}
<span class="boring">}</span></code></pre></pre>
<p>大家可以再次尝试使用 <code>cargo test</code> 运行测试用例,具体的结果就不再展开,关于结果的解读,请参看文章开头的链接。</p>
<h2 id="drop"><a class="header" href="#drop">Drop</a></h2>
<p>现在还有一个问题,我们是否需要手动来清理释放我们的链表?答案是 No因为 Rust 为我们提供了 <code>Drop</code> 特征,若变量实现了该特征,则在它离开作用域时将自动调用解构函数以实现资源清理释放工作,最妙的是,这一切都发生在编译期,因此没有多余的性能开销。</p>
<blockquote>
<p>关于 Drop 特征的详细介绍,请参见<a href="https://course.rs/advance/smart-pointer/drop.html">智能指针 - Drop</a></p>
</blockquote>
<p>事实上,我们无需手动为自定义类型实现 <code>Drop</code> 特征,原因是 Rust 自动为几乎所有类型都实现了 <code>Drop</code>,例如我们自定义的结构体,只要结构体的所有字段都实现了 <code>Drop</code>,那结构体也会自动实现 <code>Drop</code> !</p>
<p>但是,有的时候这种自动实现可能不够优秀,例如考虑以下链表:</p>
<pre><code class="language-shell">list -&gt; A -&gt; B -&gt; C
</code></pre>
<p><code>List</code> 被自动 <code>drop</code> 后,接着会去尝试 <code>Drop</code> A然后是 <code>B</code>,最后是 <code>C</code>。这个时候,其中一部分读者可能会紧张起来,因此这其实是一段递归代码,可能会直接撑爆我们的 stack 栈。</p>
<p>例如以下的测试代码会试图创建一个很长的链表,然后会导致栈溢出错误:</p>
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>#[test]
fn long_list() {
let mut list = List::new();
for i in 0..100000 {
list.push(i);
}
drop(list);
}
<span class="boring">}</span></code></pre></pre>
<pre><code class="language-shell">thread 'first::test::long_list' has overflowed its stack
</code></pre>
<p>可能另一部分同学会想 "这显然是<a href="https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8">尾递归</a>,一个靠谱的编程语言是不会让尾递归撑爆我们的 stack"。然后,这个想法并不正确,下面让我们尝试模拟编译器来看看 <code>Drop</code> 会如何实现:</p>
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>impl Drop for List {
fn drop(&amp;mut self) {
// NOTE: 在 Rust 代码中,我们不能显式的调用 `drop` 方法,只能调用 std::mem::drop 函数
// 这里只是在模拟编译器!
self.head.drop(); // 尾递归 - good!
}
}
impl Drop for Link {
fn drop(&amp;mut self) {
match *self {
Link::Empty =&gt; {} // Done!
Link::More(ref mut boxed_node) =&gt; {
boxed_node.drop(); // 尾递归 - good!
}
}
}
}
impl Drop for Box&lt;Node&gt; {
fn drop(&amp;mut self) {
self.ptr.drop(); // 糟糕,这里不是尾递归!
deallocate(self.ptr); // 不是尾递归的原因是在 `drop` 后,还有额外的操作
}
}
impl Drop for Node {
fn drop(&amp;mut self) {
self.next.drop();
}
}
<span class="boring">}</span></code></pre></pre>
<p>从上面的代码和注释可以看出为 <code>Box&lt;Node&gt;</code> 实现的 <code>drop</code> 方法中,在 <code>self.ptr.drop</code> 后调用的 <code>deallocate</code> 会导致非尾递归的情况发生。</p>
<p>因此我们需要手动为 <code>List</code> 实现 <code>Drop</code> 特征:</p>
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>impl Drop for List {
fn drop(&amp;mut self) {
let mut cur_link = mem::replace(&amp;mut self.head, Link::Empty);
while let Link::More(mut boxed_node) = cur_link {
cur_link = mem::replace(&amp;mut boxed_node.next, Link::Empty);
// boxed_node 在这里超出作用域并被 drop,
// 由于它的 `next` 字段拥有的 `Node` 被设置为 Link::Empty,
// 因此这里并不会有无边界的递归发生
}
}
}
<span class="boring">}</span></code></pre></pre>
<p>测试下上面的实现以及之前的长链表例子:</p>
<pre><code class="language-shell">$ cargo test
Running target/debug/lists-5c71138492ad4b4a
running 2 tests
test first::test::basics ... ok
test first::test::long_list ... ok
test result: ok. 2 passed; 0 failed; 0 ignored; 0 measured
</code></pre>
<p>完美!</p>
<p><span style="float:left"><img src="https://rust-unofficial.github.io/too-many-lists/img/profbee.gif" /></span></p>
<h4 id="为什么要提前优化"><a class="header" href="#为什么要提前优化">为什么要提前优化?</a></h4>
<p>事实上,我们在这里做了提前优化,否则可以使用 <code>while let Some(_) = self.pop() { }</code>, 这种实现显然更加简单. 那么问题来了:它们的区别是什么,有哪些性能上的好处?特别是在链表不仅仅支持 <code>i32</code> 时。</p>
<details>
<summary>点击这里展开答案</summary>
<p><code>self.pop()</code> 的会返回 <code>Option&lt;i32&gt;</code>, 而我们之前的实现仅仅对智能指针 <code>Box&lt;Node&gt;</code> 进行操作。前者会对值进行拷贝,而后者仅仅使用的是指针类型。</p>
<p>当链表中包含的值是其他较大的类型时,那这个拷贝的开销将变得非常高昂。</p>
</details>
<h2 id="最终代码"><a class="header" href="#最终代码">最终代码</a></h2>
<pre><pre class="playground"><code class="language-rust edition2021"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>use std::mem;
pub struct List {
head: Link,
}
enum Link {
Empty,
More(Box&lt;Node&gt;),
}
struct Node {
elem: i32,
next: Link,
}
impl List {
pub fn new() -&gt; Self {
List { head: Link::Empty }
}
pub fn push(&amp;mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: mem::replace(&amp;mut self.head, Link::Empty),
});
self.head = Link::More(new_node);
}
pub fn pop(&amp;mut self) -&gt; Option&lt;i32&gt; {
match mem::replace(&amp;mut self.head, Link::Empty) {
Link::Empty =&gt; None,
Link::More(node) =&gt; {
self.head = node.next;
Some(node.elem)
}
}
}
}
impl Drop for List {
fn drop(&amp;mut self) {
let mut cur_link = mem::replace(&amp;mut self.head, Link::Empty);
while let Link::More(mut boxed_node) = cur_link {
cur_link = mem::replace(&amp;mut boxed_node.next, Link::Empty);
}
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop(), None);
// Populate list
list.push(1);
list.push(2);
list.push(3);
// Check normal removal
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push(4);
list.push(5);
// Check normal removal
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), Some(4));
// Check exhaustion
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), None);
}
}
<span class="boring">}</span></code></pre></pre>
<p>从代码行数也可以看出,我们实现的肯定不是一个精致的链表:总共只有 80 行代码,其中一半还是测试!</p>
<p>但是万事开头难,既然开了一个好头,那接下来我们一鼓作气,继续看看更精致的链表长什么样。</p>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="prev" href="../../too-many-lists/bad-stack/basic-operations.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next prefetch" href="../../too-many-lists/ok-stack/intro.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
<div style="clear: both"></div>
</nav>
</div>
</div>
<nav class="nav-wide-wrapper" aria-label="Page navigation">
<a rel="prev" href="../../too-many-lists/bad-stack/basic-operations.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next prefetch" href="../../too-many-lists/ok-stack/intro.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
</nav>
</div>
<script>
window.playground_copyable = true;
</script>
<script src="../../ace.js"></script>
<script src="../../editor.js"></script>
<script src="../../mode-rust.js"></script>
<script src="../../theme-dawn.js"></script>
<script src="../../theme-tomorrow_night.js"></script>
<script src="../../elasticlunr.min.js"></script>
<script src="../../mark.min.js"></script>
<script src="../../searcher.js"></script>
<script src="../../clipboard.min.js"></script>
<script src="../../highlight.js"></script>
<script src="../../book.js"></script>
<!-- Custom JS scripts -->
<script src="../../assets/custom2.js"></script>
<script src="../../assets/bigPicture.js"></script>
</div>
</body>
</html>