标准库中的集合容器

  1. Vec, 动态可增长数组
  2. VecDeque, 双端队列
  3. LinkedList, 双向链表
  4. BinaryHeap, 二叉堆
  5. HashMap<K, V>, 哈希表
  6. BTreeMap<K, V>, B树
  7. HashSet, 哈希集合
  8. BTreeSet, B树集合

Primitive Type slice

A dynamically-sized view into a contiguous sequence, [T]

let vec: Vec<i32> = vec![1, 2, 3];
let int_slice: &[i32] = &vec[..];

可以看到 slice 的类型就是 &[T] 这样。

Struct std::vec::Vec

Vec 是一个动态可增长数组，它的定义如下：

#[stable(feature = "rust1", since = "1.0.0")]
#[cfg_attr(not(test), rustc_diagnostic_item = "Vec")]
#[rustc_insignificant_dtor]
pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> {
    buf: RawVec<T, A>,
    len: usize,
}

可以看到 Vec 有两个字段，一个是长度，另一个是内部的结构体，负责内存分配相关的。

如果只是小规模的数据，可以尝试用 small-vec

Struct std::collections::HashMap

Rust 的哈希表是通过二次探测和 SIMD 查找实现的。默认的哈希算法是 SipHash 1-3, 这个可以自己选择其它的算法.

pub struct HashMap<K, V, S = RandomState> {
    base: base::HashMap<K, V, S>,
}

Enum std::collections::hash_map::Entry

HashMap 通过 Entry 这种模式来隐藏是否有 key 的细节。

pub enum Entry<'a, K: 'a, V: 'a> {
    Occupied(OccupiedEntry<'a, K, V>),
    Vacant(VacantEntry<'a, K, V>),
}

Struct std::collections::LinkedList

标准库带的双向链表，定义如下：

pub struct LinkedList<
    T,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    alloc: A,
    marker: PhantomData<Box<Node<T>, A>>,
}

struct Node<T> {
    next: Option<NonNull<Node<T>>>,
    prev: Option<NonNull<Node<T>>>,
    element: T,
}