常用集合

rust的std中有多种实用的数据结构称为集合Collection

集合存储在堆heap上,意味在编译期不必预知集合的大小,集合大小在运行期动态变化。每种集合有不同的能力和代价

我们主要论述以下三种使用频繁的集合

vector 存储相邻的数据
string 存储字符的集合
hashmap 存储键值对,关联值v到特定的k上

vector

vector将多个相同类型数据存储在连续的内存中

创建vector

#![allow(unused)]
fn main() {
    //创建空vector，需要显式声明i32类型
    let v: Vec<i32> = Vec::new();
    //通过vec!宏使用初始值创建，rust会自动推断类型为i32
    //因为i32是int的默认类型
    let v = vec![1, 2, 3];
}

添加元素

#![allow(unused)]
fn main() {
    //使用mut创建一个可变vector
    let mut v = Vec::new();

    //使用push添加元素,rust会自动推断类型为i32
    v.push(5);
    v.push(6);
    v.push(7);
    v.push(8);
}

移除元素

remove 移除并返回指定索引的元素,并移动索引之后的元素到左边
swap_remove 若不需保留元素顺序可替代remove
pop 移除并返回最后一个元素的Option

#![allow(unused)]
fn main() {
let mut v = vec![1, 2, 3];
assert_eq!(v.remove(1), 2);
assert_eq!(v, [1, 3]);
}

读取元素

有两种方式可读取vertor中的元素

使用索引
使用get方法

#![allow(unused)]
fn main() {
    let v = vec![1, 2, 3, 4, 5];
    //索引
    let third: &i32 = &v[2];
    println!("The third element is {third}");
    //get方法
    let third: Option<&i32> = v.get(2);
    match third {
        Some(third) => println!("The third element is {third}"),
        None => println!("There is no third element."),
    }
}

使用超出范围的索引会直接panic

#![allow(unused)]
fn main() {
    let v = vec![1, 2, 3, 4, 5];

    let does_not_exist = &v[100];
    let does_not_exist = v.get(100);

//thread 'main' panicked at src/main.rs:4:28:
//index out of bounds: the len is 5 but the index is 100
}

注意所有权和借用规则

#![allow(unused)]
fn main() {
    let mut v = vec![1, 2, 3, 4, 5];

    let first = &v[0]; //不可变借用

    v.push(6); //可变借用

    println!("The first element is: {first}");//不可变借用

//error[E0502]: cannot borrow `v` as mutable because it is also borrowed as immutable
}

上述代码会报错是由于vector的存储原理：vector始终连续的存储值到内存中，当push一个新元素时，如果当前的空间不足以存储，vector会重新分配新内存然后copy之前的元素到新空间。所以上述first的不可变借用可能会被push的可变借用所影响，rust借用规则自然会阻止其通过编译

遍历vector

#![allow(unused)]
fn main() {
    let v = vec![100, 32, 57];
    for i in &v {
        println!("{i}");
    }

    //也可使用可变借用以改变其元素的值
    let mut v = vec![100, 32, 57];
    for i in &mut v {
        *i += 50;//使用*取引用的值 
    }
}

* ：dereference operator 解引用（叫取值更通顺）操作符

注意，无论使用可变或不可变引用遍历时不能添加或删除元素，会造成编译错误。还是因为借用规则，可变引用和不可变引用不能同时存在

使用枚举

vector只能存储相同类型的值，但可以借助枚举的特性间接存储不同类型的值

#![allow(unused)]
fn main() {
    enum SpreadsheetCell {
        Int(i32),
        Float(f64),
        Text(String),
    }

    let row = vec![
        SpreadsheetCell::Int(3),
        SpreadsheetCell::Text(String::from("blue")),
        SpreadsheetCell::Float(10.12),
    ];
}

rust在编译期需要知道vector中存储的元素类型，然后才能精确计算需要多少heap内存去存储每个元素。所以使用枚举+match可以保证在编译期所有可能的情况都被处理

删除vector会删除其所有元素

和其它类型一样，vector在离开作用域时会被释放

#![allow(unused)]
fn main() {
    {
        let v = vec![1, 2, 3, 4];

        // do stuff with v
    } // <- v goes out of scope and is freed here
}

当vector被释放时，vector中所有元素也会被清理

vector始终是(ptr,len,cap)三元组

包含'a','b'的容量为4的vector如下

#![allow(unused)]
fn main() {
            ptr      len  capacity
       +--------+--------+--------+
       | 0x0123 |      2 |      4 |
       +--------+--------+--------+
            |
            v
Heap   +--------+--------+--------+--------+
       |    'a' |    'b' | uninit | uninit |
       +--------+--------+--------+--------+
}

参考vector文档

String

String是UTF-8编码的字符串若不需要utf8编码的字符串，可使用OsString

str

str是string slice，是最原始的字符串类型。常见使用&str,也是字符串字面量

#![allow(unused)]
fn main() {
    //声明一个字符串字面量
    let hello_world = "Hello, World!";
}

string字面量拥有静态statics生命周期，意味着在整个程序运行期间都是有效的

#![allow(unused)]
fn main() {
    //显式的声明生命周期
    let hello_world: &'static str = "Hello, world!";
}

&str由指向字节数组的指针和长度`length`构成

#![allow(unused)]
fn main() {
use std::slice;
use std::str;

let story = "Once upon a time...";

let ptr = story.as_ptr();
let len = story.len();

// story has nineteen bytes
assert_eq!(19, len);

// We can re-build a str out of ptr and len. This is all unsafe because
// we are responsible for making sure the two components are valid:
let s = unsafe {
    // First, we build a &[u8]...
    let slice = slice::from_raw_parts(ptr, len);

    // ... and then convert that slice into a string slice
    str::from_utf8(slice)
};

assert_eq!(s, Ok(story));
}

创建string

一些在vector中相同的方法同样在String中可用,因为String实际是在Vec<u8>的基础上增加其它保证，限制，能力的封装

#![allow(unused)]
fn main() {
    //比如String同样可用new创建
    let mut s = String::new();
}

实现了Displaytrait的可使用to_string创建String,比如下面使用string字面量

#![allow(unused)]
fn main() {
    let data = "initial contents";

    let s = data.to_string();

    // the method also works on a literal directly:
    let s = "initial contents".to_string();
}

也可使用String::from创建

#![allow(unused)]
fn main() {
    let s = String::from("initial contents");
}

添加内容

使用push_str或push方法

#![allow(unused)]
fn main() {
    let mut s = String::from("foo");
    s.push_str("bar");

    s.push('l');//也可添加单个字符
}

可使用+操作符或format!宏连接字符串

#![allow(unused)]
fn main() {
    let s1 = String::from("Hello, ");
    let s2 = String::from("world!");
    let s3 = s1 + &s2; // note s1 has been moved here and can no longer be used
}

+操作符使用add方法

#![allow(unused)]
fn main() {
fn add(self, s: &str) -> String {
}

#![allow(unused)]
fn main() {
    let s1 = String::from("tic");
    let s2 = String::from("tac");
    let s3 = String::from("toe");

    使用+连接多个字符串可读性很低
    //let s = s1 + "-" + &s2 + "-" + &s3;
    let s = format!("{s1}-{s2}-{s3}");
}

索引

rust中String不支持索引

#![allow(unused)]
fn main() {
    let s1 = String::from("hello");
    let h = s1[0];

//error[E0277]: the type `String` cannot be indexed by `{integer}`  
}

内部展示

String实际是Vec<u8>的封装

#![allow(unused)]
fn main() {
    //len = 4 byte,每个字符使用1个字节当使用utf8编码
    let hello = String::from("Hola");

    //貌似是西里尔字母啥的,首字母也不是3,是西里尔字母的Ze
    //实际len=24 byte，每个字符在utf8编码中用2个字节表示
    let hello = String::from("Здравствуйте");

    //所以使用0这个索引根本得不到预期的结果
    let answer = &hello[0];
}

所以了为避免非预期的结果造成bug，rust编译器会阻止使用索引

rust不允许使用index访问string的最终原因是String不能保证常数时间复杂度（O(1)）去索引一个字符，因为rust必须遍历从开始到索引的内容，以确定有多少有效字符。

Slice String

可使用[range]创建字符串slice

#![allow(unused)]
fn main() {
    let hello = "Здравствуйте";

    let s = &hello[0..4];//Зд
}

但如果只获取字符的一部分时

#![allow(unused)]
fn main() {
    //会报错
    let s = &hello[0..1];
// thread 'main' panicked at src/main.rs:4:19:
// byte index 1 is not a char boundary; it is inside 'З' (bytes 0..2) of `Здравствуйте`
}

所以slice stirng时要当心

遍历string的方法

使用chars方法明确指定获取unicode字符

#![allow(unused)]
fn main() {
for c in "Зд".chars() {
    println!("{c}");
}
//会输出
З
д
}

或使用bytes方法获取字节

#![allow(unused)]
fn main() {
for b in "Зд".bytes() {
    println!("{b}");
}
//会输出
208
151
208
180
}

更多可参考string

hash map

HashMap<K, V>使用hash函数存储类型K到V的映射,hash函数决定了K,V如何被存储到内存

创建hash map

#![allow(unused)]
fn main() {
    //首先需要use引入
    use std::collections::HashMap;
    //使用new创建
    let mut scores = HashMap::new();
    //insert添加元素
    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);
}

不同于vector和String是自动预置的，hashmap需要显式引入

访问hash map的值

使用get方法获取值

#![allow(unused)]
fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    let team_name = String::from("Blue");
    let score = scores.get(&team_name).copied().unwrap_or(0);
}

get方法返回一个Option<&V>，所以使用copied方法将Option<&V>转换为Option<V>，再使用unwrap_or方法设置默认值为0若K不存在

使用for遍历

#![allow(unused)]
fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Yellow"), 50);

    for (key, value) in &scores {
        println!("{key}: {value}");
    }
    //输出顺序是随机的
    //Yellow: 50
    //Blue: 10
}

注意hashmap迭代的顺序不确定

所有权 ownership

对于实现了Copy trait的类型，例如i32，值会直接copy到hashmap中。但对于String,值会move到hashmap中，hashmap会持有所有权

#![allow(unused)]
fn main() {
    use std::collections::HashMap;

    let field_name = String::from("Favorite color");
    let field_value = String::from("Blue");

    let mut map = HashMap::new();
    //field_name and field_value 所有权转移到map中
    map.insert(field_name, field_value);
    // field_name and field_value are invalid at this point, try using them and
    // see what compiler error you get!
}

更新hash map

hashmap的k是唯一的，所以插入相同的k会覆盖之前的值

#![allow(unused)]
fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();

    scores.insert(String::from("Blue"), 10);
    scores.insert(String::from("Blue"), 25);

    println!("{scores:?}");
    //输出 {"Blue": 25}
}

当K不存在时才添加

使用entry方法

#![allow(unused)]
fn main() {
    use std::collections::HashMap;

    let mut scores = HashMap::new();
    scores.insert(String::from("Blue"), 10);

    scores.entry(String::from("Yellow")).or_insert(50);
    scores.entry(String::from("Blue")).or_insert(50);

    println!("{scores:?}");
    //{"Yellow": 50, "Blue": 10}
}

entry方法返回一个Entry枚举表明值是否存在，Entry的or_insert方法在K存在时返回一个K对应值的可变引用，不存在则插入并返回可变引用

使用entry比我们自己写逻辑更清晰,和借用检测器(borrow checker)也配合的更好

#![allow(unused)]
fn main() {
pub enum Entry<'a, K: 'a, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>),
}
}

基于旧值更新

#![allow(unused)]
fn main() {
    use std::collections::HashMap;

    let text = "hello world wonderful world";

    let mut map = HashMap::new();

    for word in text.split_whitespace() {
        let count = map.entry(word).or_insert(0);
        *count += 1;//前面提过or_insert返回的是值得可变引用
    }

    println!("{map:?}");
    //{"world": 2, "hello": 1, "wonderful": 1}
}

hash函数

hashmap默认使用SipHash算法，可以抵御Denial of Service (DoS)攻击。它不是目前最快的hash算法，但为了更好的安全性而牺牲性能是值得的。

当然你也可以通过指定不同的hasher选择其它算法，hasher是实现BuildHasher trait的类型

更多可参考hash map

总结

vector，string,hash map都存放在heap上

都可以用来存储一个列表的数据，需要根据场景选择合适的集合

Rust笔记