Rust的集合
Rust的集合
- 1: Rust集合中的向量(Vec)
- 2: Rust集合中的双端队列(VecDeque)
- 3: Rust集合中的链表(LinkedList)
- 4: Rust集合中的映射(Map)
- 5: Rust集合中的集合(Set)
- 6: Rust集合中的优先队列(BinaryHeap)
1 - Rust集合中的向量(Vec)
Rust集合中的向量(Vec)
向量(Vec) 也是一种数组，差别在于可动态增长。
// 用宏创建可变向量
let mut v1 = vec![];
v1.push(1);
v1.push(2);
v1.push(3);
assert_eq!(v1, [1,2,3]);
assert_eq!(v1[1], 2);
// 用宏创建不可变向量
let v2 = vec![0; 10];
// 用 new 方法创建
let mut v3 = Vec::new();
v3.push(4);
v3.push(5);
v3.push(6);
2 - Rust集合中的双端队列(VecDeque)
Rust集合中的双端队列(VecDeque)
Rust 中的 VecDeque 是基于可增长的 RingBuffer 算法实现的双端队列。
use std::collections::VecDeque;
let mut buf = VecDeque::new();
buf.push_front(1);
buf.push_front(2);
assert_eq!(buf.get(0), Some(&2));
assert_eq!(buf.get(1), Some(&1));
buf.push_back(3);
buf.push_back(4);
buf.push_back(5);
assert_eq!(buf.get(2), Some(&3));
assert_eq!(buf.get(3), Some(&4));
assert_eq!(buf.get(4), Some(&5));
3 - Rust集合中的链表(LinkedList)
Rust集合中的链表(LinkedList)
Rust 提供的链表是双向链表。
最好是使用 Vec 或者 VecDeque 类型，比链表更快。
use std::collections::LinkedList;
let mut list1 = LinkedList::new();
list1.push_back('a');
let mut list2 = LinkedList::new();
list2.push_back('b');
list2.push_back('c');
list1.append(&mut list2);
println!("{:?}", list1); // ['a', 'b', 'c']
println!("{:?}", list2); // []
list1.pop_front();
println!("{:?}", list1); // ['b', 'c']
list1.push_front('e');
println!("{:?}", list1); // ['e', 'b', 'c']
list2.push_front('f');
println!("{:?}", list2); // ['f']
4 - Rust集合中的映射(Map)
Rust集合中的映射(Map)
Rust 提供了两个 Key-Value 哈希映射表：
- HashMap<K, V>：无序
- BTreeMap<K, V>：有序
要求：Key 必须是可哈希的类型，Value 必须满足是在编译期已知大小的类型。
use std::collections::BTreeMap;
use std::collections::HashMap;
let mut hmap = HashMap::new();
let mut bmap = BTreeMap::new();
hmap.insert(3, "c");
hmap.insert(1, "a");
hmap.insert(2, "b");
hmap.insert(5, "e");
hmap.insert(4, "d");
bmap.insert(3, "c");
bmap.insert(2, "b");
bmap.insert(1, "a");
bmap.insert(5, "e");
bmap.insert(4, "d");
// 输出结果为：{1: "a", 2: "b", 3: "c", 5: "e", 4: "d"}，但key的顺序是随机的，因为HashMap是无序的
println!("{:?}", hmap);
// 输出结果永远都是 {1: "a", 2: "b", 3: "c", 4: "d", 5: "e"}，因为BTreeMap是有序的
println!("{:?}", bmap);
5 - Rust集合中的集合(Set)
Rust集合中的集合(Set)
Rust 提供了两个哈希集合：
HashSet<K>：无序，等同于 HashMap<K, ()>，值为空元组的特定类型BTreeSet<K>：有序，等同于 BTreeMap<K, ()>，值为空元组的特定类型
特性如下：
- 集合中的元素是唯一的
- 集合中的元素是可哈希的类型
use std::collections::HashSet;
use std::collections::BTreeSet;
let mut hbooks = HashSet::new();
let mut bbooks = BTreeSet::new();
// 插入数据
hbooks.insert(2);
hbooks.insert(1);
hbooks.insert(2);
// 判断元素是否存在，contains方法和HashMap中的一样
if !hbooks.contains(&1) {
}
println!("{:?}", hbooks);
bbooks.insert(1);
bbooks.insert(2);
bbooks.insert(3);
println!("{:?}", bbooks); // 输出固定为 {1, 2, 3} ，因为是有序
6 - Rust集合中的优先队列(BinaryHeap)
Rust集合中的优先队列(BinaryHeap)
Rust 提供的优先队列是基于二叉最大堆(Binary Heap)实现的。
use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();
assert_eq!(heap.peek(), None);
heap.push(93);
heap.push(80);
heap.push(48);
heap.push(53);
heap.push(72);
heap.push(30);
heap.push(18);
heap.push(36);
heap.push(15);
heap.push(35);
heap.push(45);
assert_eq!(heap.peek(), Some(&93));
println!("{:?}", heap); // [93, 80, 48, 53, 72, 30, 18, 36, 15, 35, 45]