Crust of Rust : std::collections

直播錄影

• 主機資訊
  ​​​​wilson@wilson-HP-Pavilion-Plus-Laptop-14-eh0xxx ~/CrustOfRust> neofetch --stdout
  ​​​​wilson@wilson-HP-Pavilion-Plus-Laptop-14-eh0xxx 
  ​​​​----------------------------------------------- 
  ​​​​OS: Ubuntu 22.04.3 LTS x86_64 
  ​​​​Host: HP Pavilion Plus Laptop 14-eh0xxx 
  ​​​​Kernel: 6.2.0-37-generic 
  ​​​​Uptime: 22 mins 
  ​​​​Packages: 2367 (dpkg), 11 (snap) 
  ​​​​Shell: bash 5.1.16 
  ​​​​Resolution: 2880x1800 
  ​​​​DE: GNOME 42.9 
  ​​​​WM: Mutter 
  ​​​​WM Theme: Adwaita 
  ​​​​Theme: Yaru-dark [GTK2/3] 
  ​​​​Icons: Yaru [GTK2/3] 
  ​​​​Terminal: gnome-terminal 
  ​​​​CPU: 12th Gen Intel i5-12500H (16) @ 4.500GHz 
  ​​​​GPU: Intel Alder Lake-P 
  ​​​​Memory: 2024MiB / 15695MiB 
  

• Rust 編譯器版本 ：
  ​​​​wilson@wilson-HP-Pavilion-Plus-Laptop-14-eh0xxx ~/CrustOfRust> rustc --version
  ​​​​rustc 1.70.0 (90c541806 2023-05-31) (built from a source tarball)
  

Introduction

0:00:00

In this video we go over the various collection types in the Rust standard library (effectively std::collections), and discuss a bit about how they work, when you might use each one, and what their respective trade-offs are.

Module std::collections 文件寫得很好，必讀。

Rust’s collections can be grouped into four major categories:

• Sequences: Vec, VecDeque, LinkedList
• Maps: HashMap, BTreeMap
• Sets: HashSet, BTreeSet
• Misc: BinaryHeap

上面四大類的 collections 自從 1.0 版就沒新增資料結構，因為上述資料結構已足以應付大部分情境，且若新增更多資料結構，這些 API 將會限制住程式設計師，因為只要這些 API 一改動就有可能會影響到有用到標準函式庫資料結構的程式的編譯，所以想要新的資料結構要自己開發不同的 crate。所以 MISC 分類目前就只有 BinaryHeap，因為我們不確定到底需不需要把新的資料結構再放進來。

Vec

0:03:57

首先看到 Vec 的結構 :

pub struct Vec<T, #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global> {
    buf: RawVec<T, A>, 
    // 1. RawVec 是標準函式庫的內部型別，表示給定容量的 vector。
    // 2. RawVec 不知道其中有多少 itmes，它只是將其全部視為可能未初始化的記憶體。
    len: usize,
    // 追蹤 vector 中實際配置了多少 items。
    
    // 由於 Vec 知道有多少 items，就可以知道在新增 item 的時候，
    // 到底要不要時候配置新的 chunk (通常為原容量的兩倍大)，並將 items 搬到新的地方。
}

接著看到 Vec 的方法 :

pub fn with_capacity(capacity: usize) -> Vec<T>
// 一開始就配置足夠的容量，比一開始先 new 一個 Vec 再 push 會快很多，
// 因為 new 出來的 Vec 通常容量很小，需要一直重新配置記憶體以及搬 items。

// 這個性質要記得，可以讓你程式的效能不會卡在明明就可以節省的記憶體複製操作。
// HashMap 也有當容量用滿也要重新配置記憶體並搬 items 的問題。

pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>
// 確保該 Vec 有足夠的容量來容納這些許多附加 items。

pub fn capacity(&self) -> usize
// 取得目前容量

在 rust/library/alloc/src/raw_vec.rs 上找到 RawVec 實作:

impl<T, A: Allocator> RawVec<T, A> {
    // Tiny Vecs are dumb. Skip to:
    // - 8 if the element size is 1, because any heap allocators is likely
    //   to round up a request of less than 8 bytes to at least 8 bytes.
    // - 4 if elements are moderate-sized (<= 1 KiB).
    // - 1 otherwise, to avoid wasting too much space for very short Vecs.
    // 試圖找出他們想要配置的最小容量是什麼，這將取決於 T 的大小。
    // 越小的 item 會配置越多容量，越大的 item 會配置越少容量。
    pub(crate) const MIN_NON_ZERO_CAP: usize = if mem::size_of::<T>() == 1 { // 1B
        8
    } else if mem::size_of::<T>() <= 1024 { // 1KB
        4
    } else {
        1
    };
    ...
    fn grow_amortized(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> {
        ...
        // This guarantees exponential growth. The doubling cannot overflow
        // because `cap <= isize::MAX` and the type of `cap` is `usize`.
        let cap = cmp::max(self.cap.0 * 2, required_cap); // 與原容量的兩倍
        let cap = cmp::max(Self::MIN_NON_ZERO_CAP, cap);  // 再與前面定義的 MIN_NON_ZERO_CAP 比較
        // 基本上就是每次容量都會變成兩倍大。
        ...
    }

core vs. std vs. alloc

rust/library/core : 不需要任何東西。
rust/library/std : 依賴於作業系統原始碼。
rust/library/alloc : 僅需一個記憶體配置器。

很多標準函式庫的集合都在 alloc crate 中而不是 std crate 中。很多集合都在 alloc 中，除了 hash map，它需要來自作業系統的隨機性。

Q : What is Global template parameter? Default allocator?

pub struct Vec<T, A = Global>
where
    A: Allocator,
{ /* private fields */ }

A : A = Global 是一個僅限 nightly 的功能，可讓你切換使用哪個記憶體配置器來配置後備 buffer。

繼續看到 Vec 的方法 :

pub fn swap_remove(&mut self, index: usize) -> T
// Vec 是一個序列，當你移除某個 item 時，
// 這個 item 之後的 items 都要往前移動一格補上空位。
// 
// 假設你有 1,000,000 個 items，且你要刪掉第一個 item，
// 這樣移動操作就要 999,999 次，所以刪除 item 是很昂貴的操作。
// 
// 如果你用以下方法的話，可以避免這種情形，壞處是這種方法不能保順序，
// 所以這方法只適用於不在意順序的情境。

pub unsafe fn set_len(&mut self, new_len: usize)
// 用法一 : truncate Vec，但你可能會想用 not unsafe 版本的 truncate : 
//    pub fn truncate(&mut self, len: usize) 
// 
// 用法二 (更重要) : 將 Vec 的長度擴展到未初始化的記憶體或你自己初始化的記憶體。
//     可能發生在你將指標透過 FFI 傳到 C 程式 : 
//        pub fn as_mut_ptr(&mut self) -> *mut T
//     並在 C 那端初始化記憶體，這時候你就可以自己手動調整 Vec 的長度。
// 
// 在 debug 模式下，若長度大於容量會 panic !

Q : so capacity is the max amount you can allocate but the len is the actual amount of memory been used
A : 容量是正在使用的記憶體量，長度是初始化和可存取的記憶體量。

繼續看到 Vec 的方法 :

pub fn retain<F>(&mut self, f: F)
where
    F: FnMut(&T) -> bool,
// 你可以使用它來從 Vec 中刪除所有與給定條件匹配的 items。
// 也就是說，它會刪除以下 closure 回傳 false 的所有 items。
// retain 之所以比自己迴圈走訪更有價值，有以下幾個原因
//   1. 使用 borrow checker 時，自己迴圈走訪集合並嘗試對集合進行修改會變得很麻煩。
//   2. 如果你刪除了許多 items，它會更聰明地進行移動操作。
//      如果一次刪除多個 items，它不需要一次刪除一個然後移動所有 items，再刪除一個，再移動所有 items。
//      它會先刪除你要刪除的所有 items，然後對移動方式進行最佳化，使得移動操作不那麼昂貴。

看到 Vec Deref :

Methods from Deref<Target = [T]>
// 因為 Vec 也是連續記憶體，所以當你有一個 Vec 時，
// 你可以像使用 slice 一樣使用它並存取 slice 上的所有方法。

繼續看到 Vec 的方法 :

pub fn leak<'a>(self) -> &'a mut [T]
where
    A: 'a,
// 你可以呼叫 Vec::leak 並傳入 Vec，
// 這將為你回傳永久存在的底層記憶體 slice 的 mutable 參考。

// 因此，這與 Box::leak 所做的事情相同，將東西其保留在 heap 上，
// 從不釋放它，並為你提供對該記憶體的本質上靜態的參考。

// 如果你有一些想要在整個應用程式中共享的配置資料 Vec，
// 而不是必須傳遞該 Vec，這可能很有用，特別是如果你最終想要從多個案例中讀取它，
// 你可以 leak 它，然後傳遞一個參考，該參考最終在程式中的任何地方都是 static。
// 你也可以透過 Rc 等來做到這一點，但如果你實際上並不關心它是否被釋放，
// 因為它確實在程式的生命週期記憶體在，那麼像 Vec::leak  這樣的東西可能非常有用。

Q : why doesnt capacity fill with default values like vec![<default>;N]
A : 看到 Guarantees 文件說明 (推薦閱讀

Due to its incredibly fundamental nature, Vec makes a lot of guarantees about its design.

本質上 Vec 是一個非常低階的 primitive，它無所不在，就像 HashMap 部分地以 Vec 的形式實作一樣，所以你真的希望 Vec 不做任何事情或至少能夠選擇退出任何你可能不想要的行為。

這種行為的一個例子是，如果創建一個給定容量的新 Vec，如果為了填充這些值而執行了這麼多的記憶體寫入，那麼對於那些允許該記憶體未初始化的用例來說，Vec 的速度會慢很多。想像一下你要做一個讀取系統呼叫，從 TCP socket 或其他內容讀取到 buffer，在讀入 buffer 之前，buffer 中有什麼記憶體並不重要，因為無論如何你都會覆蓋它。因此，如果你在執行系統呼叫之前被迫將全零寫入其中，那麼現在你將在每次呼叫上施加額外的開銷，而這些呼叫無論如何都會被覆寫。

接著看到 Vec 的 trait :

// 如果你有一個生成 items 的迭代器並且有一個 Vec，
// 則可以告訴該 Vec 使用迭代器產生的 items 來擴展自身。
impl<'a, T, A> Extend<&'a T> for Vec<T, A>
where
    T: Copy + 'a,
    A: Allocator,

fn extend<I>(&mut self, iter: I)
where
    I: IntoIterator<Item = &'a T>,

這裡的基本思想是，在 extend 中，你可以想像實作 extend 的方法就是對由迭代器產生的每個 items push 到 Vec 中。但是 extend 可以更聰明一點。例如，如果你將一個 Vec 傳遞給另一個 Vec，當你擴展時，你知道另一個 Vec 的大小。所以你可以調整 Vec 的容量以容納來自另一個 Vec 的所有 items，然後一次性地將它們全部進行 memcpy，而不是透過迴圈和迭代器生成來做所有這些開銷。所以你可以一次性將它們全部放入，然後設置長度，然後就完成了。

同樣地，如果你有一些其他的迭代器，你碰巧知道迭代器中 items 的數量，例如，你知道這是一個包含 50 個 items 的迭代器，你也可以做同樣的事情。你可以預留那麼多記憶體，這樣至少在進行 push 操作時不會重新配置記憶體。這尤其重要，舉個例子，如果你有一個 Vec 進行迭代，然後呼叫了一個 filter，那麼如果你知道原始 Vec 的長度是 100，並且知道 filter 存在，你就知道它最多可以產生 100 個 items 。因此，在進行所有這些 push 之前，extend 的實作可以利用這一點，它可以查詢可能產生的 items 數的上限，然後使用這個訊息來提前配置容量。

Q : how to drop leaked box?
A : 不行，它們只能在程式結束後才會釋放。

Q : Ye, how does the vec! macro work?
A : 如果你沒有得到任何 item，那麼它就會變成 Vec::new()。如果它獲得任意數量的 item，它將使用 Vec::with_capacity()，然後 push 所有這些 items，然後回傳結果。

Q : difference with small_vec
A : 所有 Vec 都是 heap 配置的。因此，我們查看的 RawVec 型別是 heap 上的配置，你可以透過諸如 Box::new() 之類的方式獲得。這意味著每次你有一個 Vec 時，你都會進行記憶體配置。你必須進行指標追蹤，你必須追蹤配置到 heap 的指標，然後從那裡讀取 items。還有其他 crate，我們看到其中一個實作，SmallVec :

pub enum SmallVec<T, const N: usize> {
    // <= N, item 放這
    LocalBuf(LocalVec<T, N>), // 其容量在 stack 上配置的 Vec。
    // > N, item 放這
    RemoteBuf(Vec<T>), // 一般配置在 heap 的 Vec。
}

看到 LocalVec 結構 :

pub struct LocalVec<T, const N: usize> {
    buf: [MaybeUninit<T>; N],
    len: usize, // 追蹤真實長度
}

Q : Do any of the data structures have stable ABI, say for C FFI?
A : 在 Rust 中沒有 stable ABI。但是，例如 Vec 保證了它佈局記憶體的方式，保證了它是連續的。因此，你可以使用 Vec 的後備記憶體來建構一個陣列指標，然後將它傳遞給 C。這取決於你對資料結構的理解，例如，你無法透過 FFI 從 C 呼叫 Vec 的 push 方法。但是你可以在 Rust 中分配一個 Vec 並將指標和長度傳遞給 C。然後 C 將能夠對其進行操作。對於其他 collections 類型來說，情況並不如此，這主要是 Vec 的一個特性。

Q : Why Vec doesn't implement iter but into_iter ?

impl<'a, T, A> IntoIterator for &'a Vec<T, A>
where
    A: Allocator,

A : 因為 Vec 不是一個迭代器。一個迭代器需要追蹤目前是哪個 item，或者下一次要產生哪個 item，或者是剛剛產生了哪個 item。而 Vec 並沒有這個訊息，Vec 有三個欄位，指向後備記憶體的指標、容量和長度。而對於迭代器，你需要一個額外的 item (即將產生的)。這就是當你在 Vec 上呼叫 IntoIterator 時會發生的事情，如果你要產生一個 Vec，它會產生一個新型別，該型別具有對 Vec 的參考。如果你從一個共享參考獲得了迭代器，則該參考是 read-only；如果你從一個 mutable 參考到 Vec 獲得了迭代器，則它是 mutable；如果你有一個 owned的 Vec，並將其轉換為迭代器，那麼它就是 owned。因此，它具有對底層 Vec 的參考，然後具有一個 item 或索引 :

pub struct IterMut<'a, T: 'a> {
    /// The pointer to the next element to return, or the past-the-end location
    /// if the iterator is empty.
    ///
    /// This address will be used for all ZST elements, never changed.
    ptr: NonNull<T>,
    /// For non-ZSTs, the non-null pointer to the past-the-end element.
    ///
    /// For ZSTs, this is `ptr::invalid_mut(len)`.
    end_or_len: *mut T, // 追蹤 Vec 下一個應該生產什麼
    _marker: PhantomData<&'a mut T>,
}

Q : Isnt there a size limit on the stack?
A : 是的。所以通常你不想使用一個 SmallVec 並且擁有很多 items。這也意味著如果你將 SmallVec 跨越函式呼叫邊界傳遞，它將在 stack frame 之間進行複製。而對於 heap 配置，你只需傳遞 heap 指標。

Q : Why is the lifetime of Vec::leak not static?

pub fn leak<'a>(self) -> &'a mut [T]
where
    A: 'a,

A : 之所以回傳任意的生命週期而不是 static，是因為這樣可以讓 borrow checker 更容易處理 Vec::leak()。如果回傳 static，那麼它需要將生命周期縮短為你所需的生命周期。如果它總是回傳一個 static mutable 參考，那麼無論你把它放在哪裡，它都會被放置為 static。這與 variant 的工作方式有關，這意味著如果它在 invariant 的東西裡面，那麼 invariant 現在將會在 static 上，而你可能不希望它在 static 上。所以任意的生命週期最終會稍微比 static 更少地讓你遇到麻煩的事情，但它們在某種程度上是等效的。

Q : is there any reason to not use SmallVec over vec?
A : 是的，不使用 SmallVec 的原因是需要額外的成本來追蹤該 item 是在 heap 上還是在 stack 上。這意味著你需要根據一個額外的欄位進行 branch，告訴你它是 local 的還是 remote。另一個原因是，對於任何在 heap 上分配記憶體的東西，每次你透過 ownership 傳遞它而不是作為參考傳遞時，都需要將 stack 上的整個內容複製過來。因此，你可能會開始看到記憶體複製的出現，因此你的 stack frame 變得非常大。而對於 Vec，它始終只有三個欄位。這也意味著，如果將一個 SmallVec 放入一個結構中，該結構的大小將隨著該 SmallVec 的 stack 大小而增長。

Q : you could impl Iterator for Vec by defining next() as remove(0), but it would be bad
A : 是的，你不想這樣做。你擁有的等效項是 drain 方法 :

pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, A>
where
    R: RangeBounds<usize>,
// 接受一個範圍，這個範圍可以是開放式的，意味著從 Vec 中刪除所有內容或 drain 整個 Vec。
// 回傳一種型別，即一個迭代器，該迭代器將從 Vec 中移除所有它走訪的 items。
// 但是，對於 Vec 本身，沒有一種合理的方法可以實作迭代器。

VecDeque

0:29:57

首先看到 VecDeque 結構 :

pub struct VecDeque<T, A = Global>
where
    A: Allocator,
{ /* private fields */ }

A double-ended queue implemented with a growable ring buffer.

• Vec :
  
  
  當 len == capacity 會配置新的記憶體
• VecDeque :
  
  
  當 start == end 會配置新的記憶體

使用 Ring buffer 的好處是，它既可以充當 stack (LIFO)，也可以充當 queue (FIFO)。

看到 VecDeq 的方法 :

// 以下方法 Vec 皆有，但 ring buffer 在 pop_front 以及 push_front 時，
// 不需移動 items，只需操作 start 或 end 指標即可。
pub fn pop_front(&mut self) -> Option<T>
pub fn pop_back(&mut self) -> Option<T>
pub fn push_front(&mut self, value: T)
pub fn push_back(&mut self, value: T)

如果 VecDeq 如此神奇，那我們為什麼不到處都使用它們呢？這有幾個原因。其中之一是它們的效率有點低。他們效率較低的最大原因是，想像你透過呼叫迭代器從 start 開始走訪這些元素，而硬體的工作方式通常是，當你正在走訪任何型別的記憶體時，如果它偵測到你一次正在走訪索引，那麼你的 CPU 將執行的操作就像是預讀 :

當你走到 (1) 時，CPU 可能會載入到 (2) 的記憶體。當你到達 (3) 時，它將載入到 (5) 的記憶體中。它永遠不會使用 (4)-(5) 的記憶體，因為它超出了界限。它不知道你接下來要讀取 (6) 的記憶體。所以從某種意義上來說它是一種碎片整理。因此，這種方式會損失一點效率，這對於特定型別的迴圈來說可能非常重要。

另一個原因是，當你在計算元素的索引 [i] 時，如果 start 位置 + i 超過 VecDeq 長度且未處理會有問題，所以你必須要有一個複雜的邏輯去計算出索引 [i] 在記憶體的實際位置，而這個複雜的邏輯將造成每次存取額外的開銷。

還有一個原因是，不能把 VecDeq 變成 slice。因為 VecDeq 的記憶體不一定是連續的。而 slice 的要求是，它是一塊連續的記憶體，因此 VecDeq 並不一定滿足。這意味著你無法存取許多其他方法，例如二元搜尋，它不是在 Vec 上實作的，而是在 slice 上實作的。

有許多方法可以嘗試將 VecDeq 變成更容易使用的東西。例如 :

1. &mut [T]
   ​​​​pub fn make_contiguous(&mut self) -> &mut [T]
   

   make_contiguous 將原本兩塊連續的記憶體，透過搬移組成一塊，你就可以 將 VecDeq 作為 slice 使用 :
   
   
2. (&mut [T], &mut [T])
   ​​​​pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T])
   

   切成兩個連續的記憶體，並分別將它們轉成 slice :
   
   

Q : Fun fact, VecDeque actually uses head + len, not start + end.
A : 沒差，它們是等價的。

Q : Can you chain the two iterators from .as_slices()?
A : 可以，但不需要這麼做。即使 VecDeq 不是連續的，它也會實作到迭代器中，因為它可以輕鬆地為你進行迭代，只是不能專門變成 slice 來使用。

我們討論的 VecDeq 功能，比如 drain、retain、truncate 以及 reserve…等等。它通常在外觀和感覺上非常像一個 Vec，只是它不能在某些方面像 Vec 那樣。
因為 VecDeq 不是對 slice 進行解參考，所以它的一個缺點是，有相當多的方法需要為 VecDeq 手動重新實作，因為當你沒有連續的記憶體時，它就不起作用了。例如以下的二元搜尋就是 VecDeq 上的實作 :

pub fn binary_search(&self, x: &T) -> Result<usize, usize>
where
    T: Ord,

VecDeq 無法使用 slice 上實作的相同方法。這就是為什麼它是在更晚的版本中添加的原因。它與 slice 的實作是分開的。因此，VecDeq 基本上是建構兩個 slice，對它們中的一個進行二元搜尋，因為它必須處理這裡有兩個 slice 的事實。

繼續看到 VecDeq 方法 :

pub fn rotate_left(&mut self, n: usize)
pub fn rotate_right(&mut self, n: usize)
// 這兩種方法都會處理 wrapping around 的情形

Q : But why there is no is_contiguous method? Or try_as_contiguous_slice?
A : 你可以自己實作。但實際上，你可以直接呼叫 as_slices 方法，並檢查第二個 slice 是否為空。如果第二個 slice 不為空，則意味著你無法獲取 slice，如果第二個 slice 為空，則第一個 slice 就是連續 slice ，而無需任何 unsafe 的程式碼。
A : 觀察 make_contiguous 可以發現，is_contiguous 確實是存在的，但是它是私有的。

Q : What complexity is rotate?
A : O(n)

Q : Why do rotate_left|right have differently named arguments?
舊文件寫的如下 :

pub fn rotate_left(&mut self, mid: usize)
pub fn rotate_right(&mut self, k: usize)

A : PR 有修正將第二個參數都叫 n 了。

Q : How does VecDeque implement Extend?
A : 它可以很容易地實作 Extend，如果你考慮簡單的實作，它只是當迭代器傳遞到 extend 產生一個 item 時，然後將你得到的 item push 回去。所以相當簡單。它也執行與 Vec 相同的最佳化，如果我們知道迭代器將產生一定數量的 items，那麼我們可以保留額外的容量以確保我們有足夠的空間。

Q : Seems like rotate* should be a lot more effective compared to Vec
A : 沒錯，可以透過移動 start 以及 end 來達成，中間不需要有記憶體複製。

Q : Why does make_contiguous ensure start is an storage index 0 ? Couldn't it just make sure end > start ?
A : 看到 make_contiguous 實作 :

pub fn make_contiguous(&mut self) -> &mut [T] {
    if T::IS_ZST {
        self.head = 0;
    }
    // 確實是這樣做，沒有保證從 0 開始。
    if self.is_contiguous() {
        unsafe { return slice::from_raw_parts_mut(self.ptr().add(self.head), self.len) }
    }
    ...
}

Q : What do you do if you have to prepare buf array which has specific alignment while System Programming like 16 bytes alignment of [u8; 100]
A : 你需要在儲存的資料結構上執行對齊操作，Vec 本身不會為你強制執行對齊。

Q : I did the original implementation of the optimized VecDeque Extend implementation and it's really nice to read if you're curious
A : 如下 :

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> Extend<T> for VecDeque<T, A> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter());
    }

現在全部轉換為 SpecExtend 了，但是要找到 SpecExtend 更加麻煩。 SpecExtend 是 extend 的一種特殊化，這就是它的意思。因此，你希望將 extend 的實作特化為迭代器的確切型別，以便你可以更加聰明地處理迭代器的來源。例如，如果迭代器來自 Vec，則你知道其大小。

Q : from what I understand the stdlib doesn't have editions. Does that mean that it will have to stay backwards compatible forever?
A : 是的，API 必須保持向下相容。

LinkedList

0:49:54

LinkedList 是一個有趣的話題，因為有一些關於是否應該將 linked list 納入標準函式庫的爭論。部分原因是因為通常當你想使用 linked list 時，這是由於一些關於如何以高效的方式處理 linked list 的特定性質。例如，你可以將下一個和上一個指標嵌入到底層的資料結構中。你可以執行諸如 intrusive linked list 之類的操作。但是，從標準函式庫中提供的 linked list 是否增加了巨大價值還不是完全清楚的。儘管如此，特別是 doubly-linked list 在 Rust 中實作起來可能非常繁瑣。有一篇很棒的文章叫做《Learn Rust With Entirely Too Many Linked Lists》，其中詳細介紹了如何使 borrow checker 正確執行並避免對 linked list 進行 mutable 迭代器時發生奇怪的錯誤。

文件中寫道 :

NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache.

這論述完全正確。使用 linked list 的主要好處是在中間解除 link 並稍後再次 link 它們是相對容易的，你只需要走訪 linked list 並找到插入點插入，插入過程只涉及指標操作，並不涉及搬移 items，這是從 linked list 中獲得的主要好處。還有一些其他好處，例如，隨著元素數量增加，它使用的記憶體量不會像容量增加那樣增長，而是按元素增長。

Q : does it make sense to make a linkedlist of [T; 256] to avoid reallocation of Vec<T>
A : 不，你很少需要 linked list。只有在具有特定屬性的情況下才需要它，其中你已經知道要在 linked list 中的哪個位置進行操作，並且要執行的操作是插入或刪除。另一個好處是對於 linked list，無論你是插入一個還是多個元素，都沒有實際的區別，假設你已經知道插入點的前提下，插入的操作一樣都是 O(1)。

在標準函式庫的 LinkedList，只有私有欄位，因為指標的完整性非常重要，所以你不能存取以及操作這些指標 :

pub struct LinkedList<T, A = Global>
where
    A: Allocator,
{ /* private fields */ }

在 nightly 版本中，正在使用這些 Cursor 型別進行一些工作。這裡的想法是你首先透過獲取到 linked list 的 front 或 back 的 Cursor 來開始。當你有了一個這樣的 Cursor 時，Cursor 允許你移動到下一個節點，移動到上一個節點，查看下一個節點和查看上一個節點 :

pub fn peek_next(&self) -> Option<&'a T>
pub fn peek_prev(&self) -> Option<&'a T>

而 CursorMut 可以讓你有以下操作 :

pub fn insert_after(&mut self, item: T)
pub fn insert_before(&mut self, item: T)
pub fn split_after(&mut self) -> LinkedList<T, A>
where
    A: Clone,
pub fn split_before(&mut self) -> LinkedList<T, A>
where
    A: Clone,

所以這裡的想法是，你不是透過索引走訪，而是使用這種 Cursor 型別來走訪，然後使用 Cursor 來進行這種 splice 或插入和刪除操作。但這僅適用於 nightly 版本，從 PR 可以得知，從 2019 到現在還是 nightly，可見這種方法呼聲並不高。所以你通常會自己實作 linked list，而不是使用到標準函式庫的 LinkedList。

Q : ah, like a node handle
A : 沒錯，Cursor 就像 node handle。

Q : How would you turn a LinkedList<T> into a &[Y]
A : 你不能。因為 linked list 根本不是記憶體的連續表示，每個節點都有自己的配置。這就是為什麼他們說 linked list 比其他實作的記憶體效率更低的原因之一，因此，如果你想將其變成 slice，你必須迭代 linked list 並 collect 成類似 Vec 的東西。然後從 Vec 中，你可以得到一個 slice。

*Set types

0:59:21

HashSet 由 HashMap 實作；BTreeSet 由 BTreeMap 實作 :

pub struct HashSet<T, S = RandomState> {
    base: base::HashSet<T, S>,
}
// 無法直接看到由 HashMap 實作，看到程式碼開頭的註解 :
/// A [hash set] implemented as a `HashMap` where the value is `()`.

pub struct BTreeSet<
    T,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + Clone = Global,
> {
    map: BTreeMap<T, SetValZST, A>,
    // T : Set 型別
    // SetValZST : `()`
}

我們只關心 key，並不在意 value 的值是什麼，所以乾脆就給 value 占用 0 位元的 Unit 型別。

BTreeSet 其實只是轉送到底層 map 上的適當呼叫。看到 contain 的實作 :

pub fn contains<Q: ?Sized>(&self, value: &Q) -> bool
where
    T: Borrow<Q> + Ord,
    Q: Ord,
{
    self.map.contains_key(value) // 轉送到底層 map
}

在看到 BTreeSet::intersection 方法簽章 :

pub fn intersection<'a>(
    &'a self,
    other: &'a BTreeSet<T, A>
) -> Intersection<'a, T, A>
where
    T: Ord,

該方法會走訪 self 的所有 items、map 中的所有 key 以及 self 中的 map，然後對於 self 中的每個 key，檢查該 key 是否存在於其他集合中的 map 的 key 集合中。因此，你需要走訪所有自己的 keys，並檢查這些 keys 是否在另一個集合的 map 中存在。

另一件事是，你會獲得與底層 map 型別的 key 相同的屬性。對於 HashSet 來說，它要求型別 T 實作 Hash，因為 HashMap 的 key 依賴於該型別實作 Hash。對於 BTreeSet 來說也是一樣的道理。它要求型別 T 實作 Ord，因為 BTreeMap 的 key 要求 Ord，因此，你也會得到相應的屬性。因此，BTreeSet 確實是有序的，因為 BTreeMap 的 key 是有序的，這就是集合映射的作用。

Q : are btreesets ordered? I see Ord there.
A : 是的。

Q : Why use a set over a Vec?
A : 使用集合而不是 Vec 的原因是因為通常你想要消除重複的 items。集合的主要特性是集合中的所有 items 都是唯一的，並且可以快速檢查 item 是否已經在集合中。對於 Vec 來說，如果將 Vec 用作集合，你尋找給定 item 是否存在於集合中的方式是走訪 Vec 並檢查是否有任何 item 相等，或者你可以保持一個排序的 Vec，然後在 Vec 上執行二元搜尋，但這仍然是 O(logn) 的時間複雜度，而 HashMap 的查詢則是接近 O(1)。

看到 BTreeSet 有實作的 trait

1. Extend 會忽略重複的 key :
   ​​​​impl<'a, T, A> Extend<&'a T> for BTreeSet<T, A>
   ​​​​where
   ​​​​    T: 'a + Ord + Copy,
   ​​​​    A: Allocator + Clone,
   ​​​​source
   

2. Bit* 讓你做類似位元操作的事情 :
   ​​​​// = intersection
   ​​​​impl<T, A> BitAnd<&BTreeSet<T, A>> for &BTreeSet<T, A>
   ​​​​where
   ​​​​    T: Ord + Clone,
   ​​​​    A: Allocator + Clone,
   
   ​​​​// = union
   ​​​​impl<T, A> BitOr<&BTreeSet<T, A>> for &BTreeSet<T, A>
   ​​​​where
   ​​​​    T: Ord + Clone,
   ​​​​    A: Allocator + Clone,
   
   ​​​​// = symmetric_difference
   ​​​​impl<T, A> BitXor<&BTreeSet<T, A>> for &BTreeSet<T, A>
   ​​​​where
   ​​​​    T: Ord + Clone,
   ​​​​    A: Allocator + Clone,
   

Q : Is a set as fast as a vector?
A : 如果你想要的是一個集合，那麼 Set 和 Vec 之間是有區別的。這取決於你將對該集合進行的操作和工作負載的型別。但一般而言，Set 型別對於集合的處理要比一般的 Vec 更好。

Q : any chance of a "native" (::collections) Trie data structure?
A : Jon 不認為樹會出現在標準函式庫。Jon 認為標準函式庫實際上不會擴展其 collections 類型，很可能永遠都不會。這是因為將它放在單獨的 crate 中要好得多。必須有一個相當有說服力的理由才能將一個資料結構引入標準函式庫，它必須在所有地方都被廣泛使用。再者，就連像 linked list 這樣的基本資料結構是否應該存在於標準函式庫也是不清楚的。因為標準函式庫的限制往往會讓你想要自己實作特定的 linked list。

HashMap

1:07:51

HashMap 和 BTreeMap 都實作了 map abstraction。所謂的 map abstraction 是指每個 key 都映射到一個 value，並且不存在重複的 key，因此，它們也可用於實作集合。

看到各操作的複雜度 :

	get	insert	remove	range	append
HashMap	O(1)~	O(1)~*	O(1)~	N/A	N/A
BTreeMap	O(log(n))	O(log(n))	O(log(n))	O(log(n))	O(log(n))

• get 的 ~ 是 armotized，get 不一定第一次就找到 key
• remove 的 ~ 是 armotized，不一定第一次就找到要移除的東西，且你還要持續 probe 到空 bucket 為止，並將這些 key 調整位置，才能確保下次 probe 時不會有問題。
• insert 的 ~* 是 armotized 升級版，因為 HashMap 插入 key 不一定第一次就找到插入點，而且可能會遇到 resize 整個 map 的情形。

標準函式庫的 HashMap 遇到 collision 採用 open addressing 方法來解決。

標準函式庫的 HashMap 相當快，但絕對不是你能找到的最快的。因此，你可以找到一堆提供更快 hash function 的 crates，從而顯著提高 HashMap 的效能。

Q : Why insert tho? Isn't changing a value the same operation as inserting? That's why JS uses (new Map()).set(key, value) instead of .insert() or .change() idk
A : 如果你想更新映射中的值，這與插入操作是一樣的。你可以稍微優化，但你可以把更新值想像成一種插入操作。但在 Rust 中，你也可以透過 get_mut 方法來獲取 key 的 mutable 參考，這將回傳該 key 對應的 value 的 mutable 參考。

Q : How many buckets does a hash map has and how many values can each bucket store?
A : open addressing 的方式，每個 bucket 只能存一個 (key, value)。HashMap 中的 bucket 的調整遵循類似 Vec 的規則，但最小容量比 Vec 還大 (Jon 記得是 64 或 128 個 buckets)。

Q : Why doesn't the standard library use a faster hash implementation in the first place?
A : 主要原因是標準函式庫中的實作是一個加密 hash。因此，他們試圖讓預測給定密鑰的 hash 輸出變得非常困難。他們這樣做的原因是，想像一下，如果你正在運行某種類型的 Web 服務，並且使用 user 請求中的某些內容作為密鑰。當你對該值進行 hash 時，它變成了 bucket 的 key。如果 user 控制密鑰並且可以輕鬆地確定 hash function 或確定 hash 的輸出，那麼一個惡意 user 可以做的是向你發送許多不同的密鑰請求，這些密鑰都會 hash 到同一個值。因此，他們基本上可以對你 DDOS，透過生成的所有碰撞填充所有 bucket，將你的 hash 映射性能帶入最糟糕的情況。

因此，標準函式庫在其預設實作中所做的是，當你創建一個新的映射時，它將生成一個用於 seed 的隨機數，以用於存取該映射的所有 hash 。因此，即使攻擊者知道 hash 算法，他們也不知道每個映射的 seed 是什麼。因此，他們無法弄清楚如何導致密鑰生成相同的 hash 並導致這些碰撞，從而導致性能崩潰。hash function 是一種加密 hash，因此很難逆向。因此，即使使用者學會了他們的 hash，他們也無法使用它來確定生成後續額外碰撞的 seed。因此，標準函式庫基本上試圖預設保持安全性，但作為結果，預設情況下性能較差，這就是為什麼你能夠插入自己的 hash 演算法。

看到標準函式庫的 HashMap :

pub struct HashMap<K, V, S = RandomState> { /* private fields */ }
// RandomState 就是剛剛提到的 Seed

接著追蹤 HashMap 實作 :

// Struct std::collections::HashMap
impl<K, V, S> HashMap<K, V, S>
where
    K: Eq + Hash,
    S: BuildHasher, // Hasher 可以 hash 一個值
}

// Trait std::hash::BuildHasher
pub trait BuildHasher {
    type Hasher: Hasher;
    // Required method
    fn build_hasher(&self) -> Self::Hasher;
    ...
}

fn hash_one<T>(&self, x: T) -> u64
where
    T: Hash,
    Self: Sized,
    Self::Hasher: Hasher,

// Trait std::hash::Hash
pub trait Hash { // 從很多型別衍生的
    // Required method
    fn hash<H>(&self, state: &mut H)
       where H: Hasher;

    // Provided method
    fn hash_slice<H>(data: &[Self], state: &mut H)
       where H: Hasher,
             Self: Sized { ... }
}

// Trait std::hash::Hasher
pub trait Hasher {
    // Required methods
    fn finish(&self) -> u64;
    fn write(&mut self, bytes: &[u8]);

    // Provided methods
    fn write_u8(&mut self, i: u8) { ... }
    fn write_u16(&mut self, i: u16) { ... }
    ...
}

Q : What can downsides of these faster hashing algorithms be? I guess there must be some
A : 通常的缺點部分來自複雜性，部分來自抗碰撞。

Q : Wouldn't you need constant time per request for cryptographic security anyway? (Which hashmaps don't garantee)
A : 這不是關於 map 本身的加密保證。這不是對 map 的常數時間存取。從密碼學的角度來看，它是一種具有 pre-image 的 hash。Hash 具有許多使其具有密碼學安全性的屬性，但這並不一定使整個資料結構適合使用密碼學。

Q : How would you know that something had collided?
A : 通常情况下，你是不會知道的，碰撞是對你隱藏的，這種探測是在幕後進行的。你唯一知道的方式是如果發生碰撞，那麼對於發生碰撞的 key，查詢速度會稍微變慢。

看到 HashMap 的方法 :

// 可以自己指定有多少 bucket
pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState>

// 可以自己指定 hasher
impl<K, V, S> HashMap<K, V, S>
pub fn with_hasher(hash_builder: S) -> HashMap<K, V, S>

// 透過走訪 bucket 來迭代 keys
pub fn keys(&self) -> Keys<'_, K, V>

// 透過走訪 bucket 來迭代 values
pub fn values(&self) -> Values<'_, K, V>

// 回傳迭代器
pub fn iter(&self) -> Iter<'_, K, V>
// 看到 Iter 的實作
impl<'a, K, V> Iterator for Iter<'a, K, V>
type Item = (&'a K, &'a V)

// 功能同 Vec::drain
pub fn drain(&mut self) -> Drain<'_, K, V>

// HashMap 在刪除時，並不會因為達到某個閥值而把 map 條小，
// 需要呼叫 shrink_to_fit 來做調整，
// 調整過程會涉及記憶體複製以及調整 key 位置，
// key 位置之所以改變是因為 hash function 可能會隨著 map 的大小而改變 (ex. 取不同 modulo)。
pub fn shrink_to_fit(&mut self)

// 也是 update，因為若 map 原本有 ori_key，ori_k 會被 new_key 以及 new_value 取代。
// 若 map 原本有 ori_key，並回傳 ori_value，否則回傳 None。
pub fn insert(&mut self, k: K, v: V) -> Option<V>

// 傳入欲刪除的 key，回傳 value
pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
where
    K: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

// 傳入欲刪除的 key，回傳 (key, value)。
// 這可能有用的原因是你將看到這是透過 Borrow 實作的間接存取。
// 想像一下，如果你有一個 key 的型別為 String 的映射，
// 你可以使用 str 進行查詢，即使它們不是相同的型別。
// 但是這裡的 Borrow trait，對 Borrow 的泛型，
// 意味著你可以使用儲存在映射中的 key 的 Borrow 版本來進行查詢。
// 因此，在這種情況下，如果你的 key 的型別為 String，
// 你可能會使用 str 進行查詢，對於 remove_entry，你收到的將是實際的 String 和值。
// 這可能很有價值，因為這意味著你可以在以後重用該配置給其他用途。
pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
where
    K: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

看到 HashMap 的 entry :

// 回傳 Bucket 的參考
pub fn entry(&mut self, key: K) -> Entry<'_, K, V>

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

pub struct OccupiedEntry<'a, K: 'a, V: 'a> { /* private fields */ 
// insert, remove, get 方法

pub struct VacantEntry<'a, K: 'a, V: 'a> { /* private fields */ }
// insert 方法

使用 entry API 的好處是，想做到等效於以下的功能只要 hash 一次 :

// 傳統作法
if let Some(...) = map.get_mut() { // 第一次 hash
    // 改變值的操作
} else {
    map.insert(key, value) // 第二次 hash
}

Entry 還有其他好用的方法 :

// 如果有 V，直接回傳 V 的參考，
// 如果沒有 V，則 insert V 再回傳 V 的參考
pub fn or_insert(self, default: V) -> &'a mut V

pub fn or_default(self) -> &'a mut V
...

Entry 使用範例 :

// insert a key only if it doesn't already exist
player_stats.entry("health").or_insert(100);
// update a key, guarding against the key possibly not being set
let stat = player_stats.entry("attack").or_insert(100);
*stat += random_stat_buff();

Q : 當在刪除 key x 時，為什麼不設一個 empty 旗標，讓 x 後面被 probe 到的 items 不用移動。
A : 壞處是，probe 距離不會因為刪除 key x 而縮短，記憶體配置也降不下來。

Q : Why when iterating a HashMap, it iterates also through empty buckets with .iter() ?
A : 當你對 map 呼叫 iter 時，它會走訪 bucket，但僅從非空的 bucket 中產生 (key, value)。這樣做的原因是什麼呢？它如何僅走訪具有內容的 bucket？HashMap 中並沒有一個可以說的東西，它只是儲存對 bucket 的指標，有時可能也儲存長度。但為了能夠走訪這些 bucket ，我需要一些額外的狀態。如果某個 bucket 中有一些內容，我需要知道跳到該 bucket ，然後跳過空的 bucket 。這樣，突然間需要大量的額外管理，這會增加資料結構的大小和複雜性，並通常降低其性能。

看到 Crate hashbrown :

This crate is a Rust port of Google’s high-performance SwissTable hash map, adapted to make it a drop-in replacement for Rust’s standard HashMap and HashSet types.

開發者在 hashbrown 做了很多 benchmark，hashbrown 已經盡量最佳化，hashbrown 處理 collision 的方法是 quadratic probing，可以用 SIMD 來平行計算，還有一堆最佳化，比標準函式庫的 HashMap 快很多。為了讓 hashbrown 介面與標準函式庫介面相容，開發者花了一段時間，現在的標準函式庫的 HashMap 實作已經被 HashBrown crate 取代了 :

use hashbrown::hash_map as base;
...
pub struct HashMap<K, V, S = RandomState> {
    base: base::HashMap<K, V, S>,
}

hashbrown 提到了該 crate 有以下好處 :

However you may still want to use this crate instead since it works in environments without std, such as embedded systems and kernels.

環境只需要有 rust/library/alloc，而不需要有 rust/library/std，因為我們不需要作業系統的隨機性。

HashMap 的一個缺點是它要求 key 是 hashable，許多型別是 hashable，但並非所有型別都是。另外，HashMap 不強制任何型別的排序，就像我們在 BTreeMap 中看到的那樣，這意味著如果你對 HashMap 進行迭代，你會以隨機順序獲取 key，你得到的 key 不是按照插入的順序回傳的，也不是按照排序的順序回傳的，而是隨機的順序。而且，每次呼叫 iter 時，順序都可能不同，它甚至不是一個穩定的迭代順序，這有時會導致人們的程式不確定性。

Q : maybe I missed it, but using Hashbrown is same as std:: hashmap ? perfomance wise ?
A : 是的，標準函式庫中的 HashMap 是 hashbrown，但它使用標準函式庫中的 hash collision resistant，而不是 hashbrown 使用的那個。

Q : How do you get different Hash implementations if you're deriving Hash?
A : 你不需要這樣做，也不必如此。所以如果我們看到以下兩個 traits :

pub trait Hash { // 實作如何走訪資料結構
    // Required method
    fn hash<H>(&self, state: &mut H)
       where H: Hasher;
    ...
}

pub trait Hasher { // 實作 hash 機制
    ...
}

Hash 的實作範例如下 :

impl Hash for Person {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id.hash(state); 
        // 只是呼叫 Hasher 的 hash，不用提供像 SHA-1 之類的東西
        self.phone.hash(state);
    }
}

Hash 跟 Hasher 的關係就像，Serialize 以及 Serializer，Serialize 實作如何走訪資料結構，而 Serializer 實作資料格式。

Q : Can you answer tim’s question: the collections source code has lot of unsafe. Why is that?
A : 資料結構的實作通常需要 unsafe 語法，因為通常會涉及到大量的原始指標操作，所以，要編寫任何類型的高效集合通常都很棘手，尤其是當你想要做像 SIMD 或這種二次探測這樣的事情時。有很多複雜性是你無法純粹使用 safe 程式碼表達的。因此，在標準函式庫中，在實作集合時經常會使用 unsafe 程式碼，這只是它們實作上的一個必要條件。基本上，設計 Rust 資料結構的人必須保證這些集合的 safety，而這些 safety 往往對於 borrow checker 來說過於複雜，無法由其代為檢查。

BTreeMap

1:43:42

看到 BTreeMap 的結構 :

pub struct BTreeMap<K, V, A = Global> 
// 並未要求 K 是 Hash，但要求 K 是 Ord。
where
    A: Allocator + Clone,
{ /* private fields */ }

二元搜尋樹作為 map 的缺點是，每個節點都是一個記憶體配置 (key, value, left_ptr, right_ptr)，指標的開銷會非常大，而且走訪要經過 log(n) 個指標才能走到葉子節點。BTree 可以解決二元樹的所有問題，配置的指標會比較少，樹高也比較矮，還有 cache friendly 的好處。

BTreeMap 是採用線性搜尋的方法搜尋節點內部的 key，而不是二元搜尋，因為看到 rust/library/alloc/src/collections/btree/node.rs，每個節點只有 6 個 slot，你不能自己調整節點的 slot 數量。

BTreeMap 有以下好處 :

• 允許插入 non-hashable 的 key，不像 HashMap 要求 key 一定要是 hashable。
• 記憶體配置行為通常比較友善，BTreeMap 的開銷相對小於 HashMap 的開銷。因為 HashMap 會將有放東西的 bucket 比例維持低一點 (ex. 70 %) 以減少碰撞的發生，而 BTreeMap 的節點基本上都是滿滿的，並不像 HashMap 需要浪費空間來維持查詢效能。
• 具有與 doubly-linked list 相似的屬性，例如以下方法 :
  ​​​​pub fn pop_first(&mut self) -> Option<(K, V)>
  ​​​​where
  ​​​​    K: Ord,
  ​​​​pub fn pop_last(&mut self) -> Option<(K, V)>
  ​​​​where
  ​​​​    K: Ord,
  ​​​​// 類似 linked list 中間可以插入 linked list 的概念
  ​​​​pub fn append(&mut self, other: &mut BTreeMap<K, V, A>)
  ​​​​where
  ​​​​    K: Ord,
  ​​​​    A: Clone,
  

小知識
通常某個東西若是 orderable，就會是 hashable，但反過來不一定成立，其中一個不成立的例子就是浮點數。

看到 BTreeMap 的方法 :

// 尋找給定範圍的 key
pub fn range<T, R>(&self, range: R) -> Range<'_, K, V> ⓘ
where
    T: Ord + ?Sized,
    K: Borrow<T> + Ord,
    R: RangeBounds<T>,

// 除了可以用 append 來合併 BTree，也可以切 BTree。
// 只需要配置一個節點的記憶體給分裂的節點。
pub fn split_off<Q>(&mut self, key: &Q) -> BTreeMap<K, V, A>
where
    Q: Ord + ?Sized,
    K: Borrow<Q> + Ord,
    A: Clone,

BTreeMap 也會用到 Cursor 型別 :

pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>
where
    K: Borrow<Q> + Ord,
    Q: Ord,

pub fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A>
where
    K: Borrow<Q> + Ord,
    Q: Ord,

// 類似 Linked list 的操作
pub fn move_next(&mut self)
pub fn move_prev(&mut self)

// 更改走訪節點的 value
pub fn key_value_mut(&mut self) -> Option<(&K, &mut V)>

// 不能在走訪的時候修改 key， key 會跑到 BTreeMap 的別的地方，
// 可能會破壞資料結構，因此，修改 key 是 unsafe。
pub unsafe fn key_mut_unchecked(&mut self) -> Option<&mut K>

Q : Can you please comment on the _unchecked versions of method I see in some of these data structs?
A : 如下 :

// 修改當前節點的某個 key 可能會讓該 key 不應該再屬於該節點，導致破壞資料結構
pub unsafe fn key_mut_unchecked(&mut self) -> Option<&mut K>

Q : curious about the number B, why is it 6? I suppose it's a compromise (rust/library/alloc/src/collections/btree/node.rs)
A : 節點若能儲存的 key 越多，更有效率 (追蹤較少指標)，但會浪費更多空間 (節點更不容易滿，但會用到的指標更少)，線性搜尋會變慢。

Q : BTreeMap require more memory than HashMaps?
A : BTreeMap 的額外開銷通常比 HashMaps 少。

Q : Why can't the list of buckets in the hashmap be appended with another list of buckets
A : 首先，HashMaps 是兩個不同連續的記憶體，因此，無法將記憶體配置 append 到彼此。BTreeMap 之所以能夠這麼做的原因是它們已經是指向分開記憶體配置的指標，因此，你可以在整個資料結構中重複使用它們。另一個不能 append 的原因是，即使你可以 append HashMaps，hash value 也不再正確，因為當你 hash 一個 key 時，你會將其取 modulo bucket 的數量，因此，如果 buckey 的數量因為你的 append 而改變，則現在取 modulo 就改變了，這意味著 hash value 也改變了，導致可能需要重新定位許多 items，以使資料結構保持有效。

Q : if the time complexity of merging two BTree maps is n+m .. is it not similar to removing elements from one Hashmap and merge into the second Hashmap ?
A : 很類似，但不同之處在於 BTreeMap 的

$n+m$ 不是 armotized。對於 HashMap 來說，它是 armotized

$n+m$，因為還需要重新配置記憶體，而對於 BTreeMap 來說，你可以重複使用所有的記憶體配置，這對實際性能也有很大的幫助。

Q : How do you guarantee that the key changing is correct?
A : 無法保證，所以這種操作是 unsafe。所以在修改 key 值時，要自己確保 key 的 ordering 沒被改變。

Q : you mentioned BTreeMap is cache friendly, but it didn't seem to be the case for me
A : 你可以自己做實驗看看。先給結論，因為 B 樹中的每個 B 節點，特別是靠近 root 的節點，很可能會在 CPU 的 data cache 中，這將更快速。

Q : I'm surprised B isn't 2^N. Wouldn't that help for cache lookups?
A : B 是否是 2 的冪並不重要。重要的是 b 乘以資料型別的大小是否是 2 的冪。但如果 b 是 2 的冪，則更有可能出現這種情況。Jon 真的不知道為什麼選擇 6。

Q : Why can't we modify B? I imagine that you might be able to do benchmark driven optimization to find the right B value.
A : 這很有趣，Jon 認為演算法的某些部分可能會根據 B 進行特定編碼，但即使如此，具有 const generic 應該也是可行的。但是在當時 (Rust 1.0)，並不存在 const generics，所以 BTreeMap 不是透過它進行泛型化的。

Q : Are you covering probabilistic collections
A : Jon 的意思是，HashMap 可能被認為是一個 probabilistic collections，但實際上並不是。提問的人可能是在講 bloom filter，但我們只討論標準函式庫中存在的 collections 類型。

Q : Lookup is expected constant time, right?
A : BTreeMap 是 O(log(n))

Q : Can't you remove and then read with the new key and then it is safe?
A : 你可以這麼做，但剛剛的 API (key_mut_unchecked) 是直接修改節點的 key。

Q : would this have a negative impact on compiler performance?
A : 如果將 BTreeMap 改為 const generic，可能會增加編譯時間，但不應影響執行時間。

Q : Might b-tree lookup be faster than hashmap lookup for small-ish maps if the hash algorithm takes a long time?
A : 是的，小型 BTreeMap 有時可能比小型 HashMap 更快。有時甚至不需要使用 BTreeMap，只需使用 Vec 即可。直接走訪單個 Vec 會更快。但這就需要根據實際工作負載進行基準測試。

Q : If you use many different B's, wouldn't the compiler have to generate instructions for all the different versions.
A : 是的。因此，如果我們讓 BtreeMap 成為 B 的 const generic，那麼人們可能會在應用程式的不同部分使用多個不同的 B。因此，他們將不得不為每個 B 編譯多次 BtreeMap。

Q : hasmap is more secure
A : BTreeMap 與 HashMap 的安全程度相同。HashMap 具有 hash denial of service resistance，但 BTreeMap 不需要這一點，因為它不必進行 hash 處理。

Q : If B was large enough, it would probably be worth it to switch to a binary search
A : 這對於在節點內部進行二元搜尋的實作是正確的。

Q : when is a btree faster than a hashmap or a vec?
A : 當你進行測量時才能確定。這並沒有一個硬性規則。效能取決於 CPU cache 的大小，取決於其中的資料型別的大小，取決於架構，所以沒有一個直接的答案。

BinaryHeap

2:10:22

Rust 的 BinaryHeap 是 max-heap。

明明 BTreeSet 也可以將東西添加到其中，但也可以 pop 最大值，為什麼不直接使用 BTreeSet 呢？

主要原因是 BinaryHeap 的實作比 BTreeMap 或 BTreeSet 更有效率。因為它不需要保留所有這些內部排序。事實上，標準庫僅使用單個 Vec 實作 BinaryHeap。有一個演算法可以將 Vec 細分，使得位於前端的元素始終是最大值。當你刪除最大值時，有一系列操作。例如，我們刪除了最大值。根據演算法的某個特定部分，你要進行一系列交換，在完成這些交換後，現在成為最大值的東西就位於前端。但是，如果你從頭到尾走訪 Vec，你將獲得最大值，然後以看似隨機的順序獲取元素。基本上，它在 Vec 內 flatten 了一個二元樹。

以下為 BinaryHeap 操作的複雜度 :

push	pop	peek/peek_mut
O(1)~	O(log(n))	O(1)

BinaryHeap 在文件中沒提到可以重複，做以下實驗驗證 :

fn main()
{
    let mut x = std::collections::BinaryHeap::new();
    x.push(2);
    x.push(2);
    while let Some(z) = x.pop()
    {
        println!("{z}");
    }
}

使用 Rust Playground 快速驗證，輸出如下 :

2
2

Q : One thing to note is that, IIRC, creating a heap from a Vec (or iterator) directly is asymptotically more efficient than a loop with push operations.
A : 如果你一次將一堆元素添加到 BinaryHeap 中，這比一次 push 一個元素要高效得多。

Q : Why would I ever want to use a BinaryHeap instead of a Vec?
A : 對於 Vec，你需要對 Vec 進行排序，以確保最大值位於前端。Vec 的缺點是，如果你想要插入某些東西，則插入的東西可能會成為新的最大值。因此，你必須將所有元素向左移動。而這對於 BinaryHeap 表示法不成立。你只需要進行 log (n) 次交換，即可將其移至最前端。

Q : when would I need the heap algorithm? A vec can do all that a binary heap can do
A : 你確實可以使用 Vec 自行實作這一點，但實際上在 Vec 上高效地實作 Heap 很難，BinaryHeap 才能滿足你的需求。特別像是在如果你只有一個 Vec 並且希望按順序走訪值，那麼你可以將 Vec 進行排序，然後按順序走訪，完全沒問題。BinaryHeap 之所以有用，是因為如果你隨時間向這個資料結構添加元素，那麼維護已排序的 Vec 實際上是相當昂貴的。而對於 BinaryHeap，你可以這樣做，因為整個 Vec 不需要有序，只需要最大值可用，而 BinaryHeap 提供了一種高效的方法來實作。此外，如果你想要按順序走訪所有元素且不關心重複元素，那麼你可能會使用 BinaryMap，因為這樣你可以在 pop 最大值時無需每次都進行 log(n) 的重新排序。

Q : is the Heap in BinaryHeap in any way related to "the heap" (where allocated data lives)? Or just two unrelated uses of "heaps of things"
A : 它們是不相關的。BinaryHeap 之所以分配在 heap 上，是因為它由 Vec 實作的。但 BinaryHeap 與 heap 沒有其他關聯，這完全只是英文單詞 “heap” 的抽象概念。就像一堆東西一樣。

Q : What would be an example usecase for the binary heap algorithm?
A : 使用 BinaryHeap 這樣的資料結構通常涉及到 priority queue (文件有提到)。舉例來說，你要編寫任務管理器之類的東西，其中有一個位於某個地方的 Web 服務，它想要發送一堆郵件。那麼你就有一個執行緒，它的任務是查詢下一封應該發送的郵件，它從某種 queue 中取出郵件，然後發送郵件，然後它從 queue 中取出下一個郵件，再發送郵件，以此類推。

假設有些郵件比其他郵件更重要。因此，某些郵件 (ex. 密碼郵件)需要以高優先級發送。它們需要在整個郵件 queue 中的其他郵件之前發送。你可以使用 BinaryHeap 來確保工作按照優先權高低來發送，因為它實作了一個 priority queue。因此，對於放入此 queue 的工作，你將擁有排序函式，用於確保密碼重置等工作具有更高的排序，更接近最大值，而新聞通訊等工作則具有較低的排序，例如某個整數的較低值。因此，結果是，當此執行緒從 BinaryHeap 中取出東西時，它將首先取出優先級更高的郵件，這就是為什麼 BinaryHeap 是一個 priority queue。

Q : Does non-nightly drain() return in sorted order?
A : 不是。實際上對此有一些爭論，如果你看到 BinaryHeap 的 iter，回傳並非有序的迭代器，只保證迭代器的第一個值是最大值 :

pub fn iter(&self) -> Iter<'_, T>
// Returns an iterator visiting all values in the underlying vector, in "arbitrary" order.

再看到 into_iter_sorted，透過一直 pop 最大值來保證輸出是有序的，但複雜度是 O(nlog(n)):

pub fn into_iter_sorted(self) -> IntoIterSorted<T, A>
// This is a nightly-only experimental API. (binary_heap_into_iter_sorted #59278)

// 之所以是 nightly-only 的原因是只能輸出遞減的序列。

回頭看到聊天室問的 drain()，該方法也不是回傳有序的 Drain :

pub fn drain(&mut self) -> Drain<'_, T, A>
// Clears the binary heap,
// returning an iterator over the removed elements in "arbitrary" order.

// If the iterator is dropped before being fully consumed,
// it drops the remaining elements in "arbitrary" order.

BinaryHeap 是 PartialOrd，舉郵件的例子，同一種郵件類型 (新聞) 之間並沒有排序，但在不同郵件類型 (新聞/密碼設置) 就有排序。

Q : good example would be heap sort
A : Heap sort 是另一種可以使用 BinaryHeap 的例子，heap sort 本來就是用在 BinaryHeap 才叫 heap sort…。

Q : Is it quicker than radix sort the list and yolo it?
A : 當你的值都是整數，你可以使用 radix sort，該排序法非常快。

問題是你如果需要維護資料結構，你在每次插入或刪除元素時都需要在做一次這種排序。或許這種方法維護資料結構可能比較有效率，這建立在 radix sort 非常快的基礎上。但 radix sort 的限制是，你的值只能是整數。

Q : Do you think there's a way we can make min-heaps more ergonomic? It's very annoying to have to re-implement Ord.
A : 標準函式庫提供的是 max-heap，第一種方法是透過重新實作 Ord 來得到 min-heap，但標準函式庫還提供第二種方法，也就是提供 Struct std::cmp::Reverse 來幫你實作 min-heap :

#[repr(transparent)]
pub struct Reverse<T>(pub T);
// A helper struct for reverse ordering.

#[stable(feature = "reverse_cmp_key", since = "1.19.0")]
impl<T: Ord> Ord for Reverse<T> {
    #[inline]
    fn cmp(&self, other: &Reverse<T>) -> Ordering {
        other.0.cmp(&self.0) // 這個結構的 Ord 只做這件事
    }
}

第二種方法的使用例子如下 :

use std::collections::BinaryHeap;
use std::cmp::Reverse;

let mut heap = BinaryHeap::new();

// Wrap values in `Reverse`
heap.push(Reverse(1));
heap.push(Reverse(5));
heap.push(Reverse(2));

// If we pop these scores now, they should come back in the reverse order.
assert_eq!(heap.pop(), Some(Reverse(1)));
assert_eq!(heap.pop(), Some(Reverse(2)));
assert_eq!(heap.pop(), Some(Reverse(5)));
assert_eq!(heap.pop(), None);

Option and Result maybe(?)

2:30:31

Enum std::option::Option 可以想成容量為 1 的 Vec；Enum std::result::Result 可以想成從 boolean 到 bi-genius 的映射。但 Jon 不建議你將它們兩個歸類成 collections 類型。

雖然它們在某種程度上像 collections ，例如，它們實現了 IntoIterator和 FromIterator 等 trait，但它們算是一種非常奇特的 collections。有些人可能會稱它們為 monad，但這裡不打算就這個問題進行爭論。

人們之所以經常稱它們為 collections 而不考慮 monad 這個詞，是因為他們想到了 Iterator trait，尤其是該 trait 有一個 collect 的方法 :

fn collect<B>(self) -> B
where
    B: FromIterator<Self::Item>,
    Self: Sized,

當你進行 collect 操作時，你將一個迭代器中的 items collect 到一個 collection 中，這個 collection 是迭代和 collect 的結果。你可以將其 collect 到 Vec、BinaryHeap、HashMap 中，或者任何你想要的地方。但你也可以 collect 到 Option 和 Result 中。因此，人們可能會認為，Result 是一個 collection，Option 也是一個 collection。然而，在實踐中，這並不完全正確。

看到以下例子 :

fn main()
{
    // Option 不是 collection 的證明
    let w: Option<usize> = (0..10).collect();      // 不 work
    let x: Vec<usize> = (0..10).collect();         // work

    // 作為 wrapper 的 Option 以及 Result 並非 collection，
    // 但它們可以 wrap 一個 collection。
    let y: Option<Vec<usize>> = (0..10)     // work
        .map(Some)
        .collect();
    let z: Result<Vec<usize>, ()> = (0..10) // work
        .map(Ok)
        .chain(std::iter::once(Err(())))
        .collect();
}

Line 9 實際上是在說 Option 是一個 functor。這實際上是說 Option 可以將一個 collection 映射到另一個 collection 中，例如透過 IntoIterator，Result 也是一樣的道理。如果你有一個包含 Option 的迭代器，你可以從這些迭代器中產生一個結果，這個結果包含了另一個 collection 。這種 wrapper 的作用是，如果其中任何一個值是 None，那麼它將產生 None，根本不會產生一個 Vec。但如果所有的值都是 Some，那麼它將產生內部值的一個 Vec。

Result 和 Option 並不像我們從 collection 中預期的那樣實作了許多其他功能，比如 extend。因為它們不是真正的 collection，但它們在某種程度上感覺像 collection。這是因為它們與 collection 共享了一些屬性，至於它們共享的屬性的具體名稱，Jon 不會提。

Q : "Applicative" is short for "applicative functor", IIRC, so "functor" is not as far off.
A : 是的，functor 確實是 applicative functor。這是 Jon 一直以來的理解。

Q : yo is that a monoid from the category of endofunctors?
A : 可能是。

Is () a collection?

2:37:35

Unit 型別是 collection，它實作了 extend, FromIterator。你可能會想，為什麼要將東西 collect 到 Unit 中以丟棄所有值？你之所以想這樣做，是因為如果要查詢的是 Err 而不在乎 Ok，那麼它會很有用 :

use std::io::*;
let data = vec![1, 2, 3, 4, 5];
let res: Result<()> = data.iter()
    .map(|x| writeln!(stdout(), "{x}"))
    .collect();
assert!(res.is_ok());

Q : Did we talk about plain arrays?
A : 它也是 collection，但不是本次想談到的 collection 類型。

Q : I'm curious how efficient very small hashmaps are. Is it very much frowned upon if you create and drop a bunch of tiny hashmaps quite often
A : 對於小型的 HashMap 來說，這取決於你打算進行多少次查詢操作，因為如果 items 數量很少，HashMap 可能會有些浪費，因為在一個很小的 HashMap 中進行 hash 計算和查詢的效率可能不如在一個小向量中進行查詢。建構一個 HashMap 並不太昂貴。配置一個 HashMap 實際上就是配置一個向量，因此這不會花費太多。但是，就執行時性能而言，與只使用向量進行搜索相比，這是否值得，則不太清楚。

Q : What if there is more than one error?
A : Collect 到 Result 中將取得第一個 Err，然後就會停止迭代。

Q : Could you point to some cool "collections" crates that are useful to know about?
A : dashmap, flurry, crossbeam, evmap (適用於 read-heavy)，hashbrown, indexmap (記得插入 key 的順序)，phf_shared (編譯時期知道所有 key，可以用這個 crate)，剩下的可以到 crate.io 看看。

小知識
MPSC 也是 collection，它實作了 queue。