Rust Book Datastructure - Datastructure

Table of Contents

Rust DataStucture
#

// 类型推导与标注
let i = "42".parse::<i32>().expect("This is not a number!");
// let i: i32 = "42".parse().expect("This is not a number!");
println!("i: {}", i);

浮点型溢出
#

// 浮点型溢出,按照补码循环溢出
let u: u8 = 255;
let u1 = u.wrapping_add(1);
println!("u1: {}", u1);

// 浮点数运算,对浮点数进行等值判断时,应该使用一个误差范围, f32与f64的误差范围不同
//assert!(0.1 + 0.2 == 0.3);  // 值不相等
assert!((0.1_f64 + 0.2 - 0.3).abs() < 0.00001);

// 细看输出值,精度不同输出的结果也不同
let abc: (f32, f32, f32) = (0.1, 0.2, 0.3);
let xyz: (f64, f64, f64) = (0.1, 0.2, 0.3);

println!("0.1 + 0.2: {:x}", (abc.0 + abc.1).to_bits());
println!("           {:x}", (abc.2).to_bits());
println!("0.1 + 0.2: {:x}", (xyz.0 + xyz.1).to_bits());
println!("           {:x}", (xyz.2).to_bits());

/**
*  0.1 + 0.2: 3e99999a
			  3e99999a
   0.1 + 0.2: 3fd3333333333334
			  3fd3333333333333
*/

Unicode
#

Unicode 都是 4 个字节编码，因此字符类型也是占用 4 个字节

let x = '中';
println!("x: {}", std::mem::size_of_val(&x));

Tips: Rust 的字符只能用’ ’ 来表示， "" 是留给字符串的。

发散函数
#

当用 ! 作函数返回类型的时候，表示该函数永不返回( diverge function )

fn foo() -> ! {
    panic!("This call never returns.");
}

所有权示例
#

类型拥有 Copy特征，一个旧的变量在被赋值给其他变量后仍然可用

    let x1: &str = "hi";
    let x2 = x1; // 引用并没有获取所有权
    println!("x1: {}, x2: {}", x1, x2);

像整型这样的基本类型在编译时是已知大小的，会被存储在栈上，所以拷贝其实际的值是快速的。这意味着没有理由在创建变量 y 后使 x 无效（ x 、 y 都仍然有效）

    let x = 1;
    let y = x;
    println!("x: {}, y: {}", x, y);

所有权转移报错

    let z = String::from("ki");
    let z1 = z; // z.clone() 解决
    println!("z: {}, z1: {}", z, z1);

error[E0382]: borrow of moved value: `z`
  --> src/chapter_1.rs:16:31
   |
14 |     let z = String::from("ki");
   |         - move occurs because `z` has type `String`, which does not implement the `Copy` trait
15 |     let z1 = z;
   |              - value moved here
16 |     println!("z: {}, z1: {}", z, z1);
   |                               ^ value borrowed here after move
   |
   = note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider cloning the value if the performance cost is acceptable
   |
15 |     let z1 = z.clone();
   |               ++++++++

error: aborting due to previous error

Copy trait
#

任何基本类型的组合可以 Copy ，不需要分配内存或某种形式资源的类型是可以 Copy

所有整数类型，比如 u32
布尔类型， bool ，它的值是 true 和 false
所有浮点数类型，比如 f64
字符类型， char
元组，当且仅当其包含的类型也都是 Copy 的时候。比如， (i32, i32) 是 Copy 的，但(i32, String) 就不是
不可变引用 &T ，例如转移所有权中的最后一个例子，但是注意: 可变引用 &mut T 是不可以Copy的

fn takes_ownership(some_string: String) { // some_string 进入作用域
	println!("{}", some_string);
} // 这里，some_string 移出作用域并调用 `drop` 方法。占用的内存被释放
fn makes_copy(some_integer: i32) { // some_integer 进入作用域
	println!("{}", some_integer);
} // 这里，some_integer 移出作用域。不会有特殊操作

可变引用
#

同一作用域，特定数据只能有一个可变引用,要么任意多个不可变引用

   let mut s = String::from("hello");
   let r1 = &mut s;
   let r2 = &mut s;
   
======================================================
error[E0499]: cannot borrow `s` as mutable more than once at a time
--> src/chapter_1.rs:4:14
 |
3 |     let r1 = &mut s;
 |              ------ first mutable borrow occurs here
4 |     let r2 = &mut s;
 |              ^^^^^^ second mutable borrow occurs here
5 |     println!("{}, {}", r1, r2);
 |                        -- first borrow later used here

error: aborting due to previous error

作用域
#

fn main() {
    let mut s = String::from("hello");
    let r1 = &s;
    let r2 = &s;
    let r3 = &mut s;
    println!("{} and {}", r1, r2);
    println!("{}", r3);
} 
error[E0502]: cannot borrow `s` as mutable because it is also borrowed as immutable
 --> src/chapter_1.rs:5:14
  |
3 |     let r1 = &s;
  |              -- immutable borrow occurs here
4 |     let r2 = &s;
5 |     let r3 = &mut s;
  |              ^^^^^^ mutable borrow occurs here
6 |     println!("{} and {}", r1, r2);
  |                           -- immutable borrow later used here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.

修改后

fn main() {
    let mut s = String::from("hello");
    let r1 = &s;
    let r2 = &s;
    println!("{} and {}", r1, r2);
    // 新编译器中，r1,r2作用域在这里结束
    let r3 = &mut s;
    println!("{}", r3);
} // 老编译器中，r1、r2、r3作用域在这里结束
  // 新编译器中，r3作用域在这里结束

NLL
#

对于上述编译器优化行为，Rust 专门起了一个名字 —— Non-Lexical Lifetimes(NLL)，专门用于找到某个引用在作用域( } )结束前就不再被使用的代码位置。

悬垂引用(Dangling References)
#

指针指向某个值后，这个值被释放掉了，而指针仍然存在，其指向的内存可能不存在任何值或已被其它变量重新使用

fn main() {
    let reference_to_nothing = dangle();
}
fn dangle() -> &String {  // dangle 返回一个字符串的引用
    let s = String::from("hello"); // s 是一个新字符串
    &s  // 返回字符串 s 的引用
}// 这里 s 离开作用域并被丢弃。其内存被释放。

error[E0106]: missing lifetime specifier
 --> src/chapter_1.rs:4:16
  |
4 | fn dangle() -> &String {
  |                ^ expected named lifetime parameter
  |
  = help: this function's return type contains a borrowed value, but there is no value for it to be borrowed from
help: consider using the `'static` lifetime
  |
4 | fn dangle() -> &'static String {
  |                 +++++++

error: aborting due to previous error

解决方法直接返回 String

fn no_dangle() -> String {
    let s = String::from("hello");
    s
}

String 的所有权被转移给外面的调用者

可变借用&不可变借用
#

fn main() {
    // 创建可变字符串
    let mut s = String::from("hello world");
    // 借用给函数
    let word = first_word(&s);
    // 清除，但是此时s仍被word借用
    // 不能在一个值不可变引用的同时可变引用
    s.clear();
    println!("the first word is: {}", word);
}
fn first_word(s: &String) -> &str {
    &s[..1]
}
error[E0502]: cannot borrow `s` as mutable because it is also borrowed as immutable
 --> src/chapter_1.rs:4:5
  |
3 |     let word = first_word(&s);
  |                           -- immutable borrow occurs here
4 |     s.clear(); // error!
  |     ^^^^^^^^^ mutable borrow occurs here
5 |     println!("the first word is: {}", word);
  |                                       ---- immutable borrow later used here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.

字符串字面量
#

    // 字符串字面量是不可变的，因为 &str 是一个不可变引用。
    let s = "Hello, world!";
    let s1: &str = "Hello, world!";
    println!("{}", s);
    println!("{}", s1);

    // String 是可变的，因为 String 是可变的。
    let mut ss: String = String::from("Hello");
    ss.push_str(", world!");
    println!("{}", ss);

字符串是由字符组成的连续集合,Rust 中的字符是Unicode 类型，因此每个字符占据 4 个字节内存空间但是在字符串中不一样，字符串是 UTF-8 编码，也就是字符串中的字符所占的字节数是变化的(1 - 4)，这样有助于大幅降低字符串所占用的内存空间。

String &str 互转
#

fn main() {
    let ss: String = String::from("Hello");
    println!("{}", ss.as_str());
    convert(ss.as_str());
    convert(&ss);

    let s = "convert &str to String".to_string();
    println!("{}", s)
}

fn convert(s: &str) {
    println!("{}", s)
}

字符串索引
#

字符串的底层的数据存储格式实际上是[ u8 ]
期望它的性能表现是O(1)，然而对于 String 类型来说，无法保证这一点

Rust不支持字符串使用索引

let s = "ssss";
let arr = s[2];
println!("arr: {}", arr);
error[E0277]: the type `str` cannot be indexed by `{integer}`
 --> src/chapter_1.rs:3:17
  |
3 |     let arr = s[2];
  |                 ^ string indices are ranges of `usize`
  |
  = help: the trait `SliceIndex<str>` is not implemented for `{integer}`
  = note: you can use `.chars().nth()` or `.bytes().nth()`
          for more information, see chapter 8 in The Book: <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>
  = help: the trait `SliceIndex<[T]>` is implemented for `usize`
  = note: required for `str` to implement `Index<{integer}>`

error: aborting due to previous error

字符串操作
#

追加

    // 在原有的字符串上追加，并不会返回新的字符串
    let mut s = String::from("Hello ");
    s.push_str("rust");
    println!("追加字符串 push_str() -> {}", s);
    s.push('!');
    println!("追加字符 push() -> {}", s);

替换

    let string_replace = String::from("I like rust. Learning rust is my favorite!");
    let new_string_replace = string_replace.replace("rust", "RUST");
    dbg!(new_string_replace);

    let mut string_replace_range = String::from("I like rust!");
    string_replace_range.replace_range(7..8, "R");
    dbg!(string_replace_range);

    let string_replace = "I like rust. Learning rust is my favorite!";
    let new_string_replacen = string_replace.replacen("rust", "RUST", 1);
    dbg!(new_string_replacen);

pop —— 删除并返回字符串的最后一个字符 remove —— 删除并返回字符串中指定位置的字符 clear —— 清空字符串

fn main() {
    let mut string_remove = String::from("测哈哈哈试remove方法");
    println!(
        "string_remove 占 {} 个字节",
        std::mem::size_of_val(string_remove.as_str())
    );
    // 删除第一个汉字
    string_remove.remove(0);
    // 下面代码会发生错误
    // string_remove.remove(1);
    // 直接删除第二个汉字
    string_remove.remove(3);
    dbg!(string_remove);
}
string_remove 占 27 个字节
[src/chapter_1.rs:13] string_remove = "哈哈试remove方法"

+ || format 连接字符串

fn main() {
    let string_append = String::from("hello ");
    let string_rust = String::from("rust");
    // &string_rust会自动解引用为&str
    let result = string_append + &string_rust;
    let mut result = result + "!"; // `result + "!"` 中的 `result` 是不可变的
    result += "!!!";
    println!("连接字符串 + -> {}", result);
    // string_append 已被移动，不能继续使用
    println!("string_append + -> {}", string_append);
}
error[E0382]: borrow of moved value: `string_append`
 --> src/chapter_1.rs:9:39
  |
2 |     let string_append = String::from("hello ");
  |         ------------- move occurs because `string_append` has type `String`, which does not implement the `Copy` trait
...
5 |     let result = string_append + &string_rust;
  |                  ------------- value moved here
...
9 |     println!("string_append + -> {}", string_append);
  |                                       ^^^^^^^^^^^^^ value borrowed here after move
  |
  = note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider cloning the value if the performance cost is acceptable
  |
5 |     let result = string_append.clone() + &string_rust;
  |                               ++++++++

error: aborting due to previous error

let s1 = String::from("tic");
let s2 = String::from("tac");
let s3 = String::from("toe");
// String = String + &str + &str + &str + &str
let s = s1 + "-" + &s2 + "-" + &s3;

String + &str 返回一个 String ，然后再继续跟一个 &str 进行 + 操作
返回一个 String 类型，不断循环，最终生成一个 s ，也是 String 类型。
s1 这个变量通过调用 add() 方法后，所有权被转移到 add() 方法里面， add() 方法调用后就被释放了
同时 s1 也被释放了。再使用 s1 就会发生错误。这里涉及到所有权转移（Move）

let s1 = "hello";
let s2 = String::from("rust");
let s = format!("{} {}!", s1, s2);

字符串转义
#

fn main() {
    println!("{}", "hello \\x52\\x75\\x73\\x74");
    let raw_str = r"Escapes don't work here: \x3F \u{211D}";
    println!("{}", raw_str);
    // 如果字符串包含双引号，可以在开头和结尾加 #
    let quotes = r#"And then I said: "There is no escape!""#;
    println!("{}", quotes);
    // 如果还是有歧义，可以继续增加，没有限制
    let longer_delimiter = r###"A string with "# in it. And even "##!"###;
    println!("{}", longer_delimiter);
}

hello \x52\x75\x73\x74
Escapes don't work here: \x3F \u{211D}
And then I said: "There is no escape!"
A string with "# in it. And even "##!

以 Unicode 字符的方式遍历字符串
#

for c in "中国人".chars() {
	println!("{}", c);
}

Rust DataStucture #

浮点型溢出 #

Unicode #

发散函数 #

所有权示例 #

Copy trait #

可变引用 #

作用域 #

NLL #

悬垂引用(Dangling References) #

可变借用&不可变借用 #

字符串字面量 #

String &str 互转 #

字符串索引 #

字符串操作 #

字符串转义 #

以 Unicode 字符的方式遍历字符串 #