如何在Rust程式語言中將元素安全地插入至已排序好的集合結構中？

Rust程式語言雖然有內建BTreeSet結構體，可以保證插入至該結構中的元素是有經過排序的。但BTreeSet是一個Set資料結構，無法儲存複數個邏輯上相同的資料，所以在一些情況下我們還是需要用比較單純的Vec結構或是其它的資料結構來儲存已排序的資料。

先請看以下的程式碼：

fn main() {
    let mut v = vec![1, 3];

    // insert 2
}

假設我們不知道變數v儲存的Vec結構實體內有什麼資料，若要在程式第2行之後，插入元素2至Vec結構實體並保留遞增順序的話，該怎麼做？

最簡單的方式自然是先把2給push到Vec資料結構的最後面，接著再去調用這個Vec結構實體的sort方法或是sort_unstable方法，如下：

fn main() {
    let mut v = vec![1, 3];

    v.push(2);
    v.sort_unstable();
}

但是這樣做的效率並不是很好，因為我們已經知道這個Vec結構實體在被插入新元素之前是遞增順序了，沒有必要再全部重排。

所以比較好的作法是，利用插入排序法(只需迭代一次)來進行插入，如下：

fn main() {
    let mut v = vec![1, 3];

    v.push(2);
    insertion_sort_single(&mut v);
}

fn insertion_sort_single(array: &mut [i32]) {
    let i = array.len() - 1;

    let temp = array[i];

    let mut j = i - 1;

    while temp < array[j] {
        array[j + 1] = array[j];

        if j == 0 {
            array[j] = temp;
            return;
        }

        j -= 1;
    }

    array[j + 1] = temp;
}

有關於插入排序法的介紹可以參考這篇文章：

不過以上的插入排序法的實作是一個元素一個元素進行搬移的動作，我們其實可以單純地從Vec資料結構的最後端去做線性搜尋，尋找適當的插入位置，再使用Vec結構實體提供的insert方法來插入會比較好。程式如下：

fn main() {
    let mut v = vec![1, 3];

    let index = v.iter().copied().rposition(|e| e <= 2).map(|index| index + 1).unwrap_or(0);
    v.insert(index, 2);
}

有關於線性搜尋法的介紹可以參考這篇文章：

不過既然提到了線性搜尋法，且又是在資料已排序的情況下，自然就會去想到二元搜尋法。在這邊用二元搜尋法也是可以的，但要注意二元搜尋法比較適合用在資料長度比較長，或是兩元素之間進行比較時所需的開支(overhead)有點大的時候。

Vec結構實體提供的binary_search方法，本身就會在找不到元素時回傳該元素如果存在，應該要被放在哪個索引值下，直接拿來利用即可。程式如下：

fn main() {
    let mut v = vec![1, 3];

    let index = match v.binary_search(&2).map(|index| index + 1) {
        Ok(index) => index + 1,
        Err(index) => index
    };
    
    v.insert(index, 2);
}

有關於二元搜尋法的介紹可以參考這篇文章：

所以在Rust中要將元素插入至已排序好的Vec結構實體中，是一件簡單的事情。不過簡單的事情每次要用的時候都要再寫一次差不多的程式碼也是挺無聊的，因此筆者另外做了一個套件來達成這個功能。當然，也不是只有支援Vec結構體而已。

Sorted Insert

「Sorted Insert」是筆者開發的套件，提供了一些特性，可以將元素插入至已排序好的集合中，並且維持集合的排序。

Crates.io

Cargo.toml

使用方法

直接看以下例子吧！

use sorted_insert::SortedInsert;

let mut v = vec![1, 5];

v.sorted_insert_asc(2);

assert_eq!([1, 2, 5], v.as_slice());

use sorted_insert::SortedInsertBinary;

let mut v = vec![5, 1];

v.sorted_insert_desc_binary(2);

assert_eq!([5, 2, 1], v.as_slice());

use sorted_insert::SortedInsertByKey;

#[derive(Debug, Copy, Clone, Eq, PartialEq)]
struct A(i32, i32);

let mut v = vec![A(1, 10), A(2, 20)];

v.sorted_insert_asc_by_key(A(1, 15), |e| &e.1);

assert_eq!([A(1, 10), A(1, 15), A(2, 20)], v.as_slice());