コレクション型

コレクションを選択する際は、まず操作を列挙してください。どのように検索するか、どちらの端で追加・削除を行うか、順序が要求されるか、範囲スキャンが必要か、そしてキーのサイズと値の分布はどうなるかです。O(1) と O(log n) を個別に比較すると、ハッシュ、文字列比較、割り当て、キャッシュアクセスのコストを見落とすことになります。

操作別のクイックリファレンス

以下の計算量は、キーの比較またはハッシュのコストを個別の型に委ねています。アモルタイズ化は、すべての操作が同様に高速であることを意味するものではありません。

HashSet/BTreeSet はキーのみを格納するニーズに対応します；固定数であれば配列を使用できます。インライン小コンテナを使用するかどうかは、実際の容量分布と選択したライブラリのルールに基づいて判断すべきであり、「20項目未満ならヒープ割り当てゼロ」という一般的な閾値は存在しません。標準ライブラリ コレクションの概要

Vec：容量は長さではない

Vec はポインタ、長さ、容量の情報を含みますが、フィールドの順序は安定した C レイアウトを保証するものではありません。Vec 自体はスタック上、ヒープ上、または他のオブジェクト内部に存在し、一概に「スタック上の 24 バイト」とは呼べません。サイズ 0 の要素と容量 0 には、特別な割り当て動作があります。

with_capacity(n) は少なくとも n 個分の容量を要求しますが、n 個の初期化済み T を作成するわけではありません。reserve(additional) は、現在の長さに additional を加えたものを必要量として計算し、最終的な容量を直接設定するものではありません。通常の push は、容量が十分であれば拡張不要です。拡張戦略と成長率は、アプリケーションが依存できる永続的な公式ではありません。Vec の保証

fn main() {
    let mut values = Vec::with_capacity(8);
    assert_eq!(values.len(), 0);
    assert!(values.capacity() >= 8);
    values.extend([10, 20, 30]);
    values.clear();
    assert!(values.is_empty());
    assert!(values.capacity() >= 8); // clear はバッファの返却を要求しない
}

拡張を引き起こす操作は、生ポインタの無効化を引き起こす可能性があり、安全な借用ルールは競合するアクセスを制限します。拡張がなくても、insert、remove、sort などは、インデックスが指すオブジェクトを変更する可能性があります。「アドレスが変わらない」ことと「依然として同じ論理要素である」ことは、同じ意味ではありません。

swap_remove は、末尾の要素で削除された位置を置き換えることで、順序を維持するために必要な移動を回避できます。その代償として順序が変更されます。長期的に安定した識別子が必要な場合は、ID、世代インデックス、または適切な間接ストレージを設計し、現在のインデックスを永続的な身元として使用しないでください。

削除時に順序と身元を分離する

fn main() {
    let original = vec![(10, "a"), (20, "b"), (30, "c"), (40, "d")];
    let mut ordered = original.clone();
    assert_eq!(ordered.remove(1), (20, "b"));
    assert_eq!(ordered, [(10, "a"), (30, "c"), (40, "d")]);

    let mut unordered = original;
    assert_eq!(unordered.swap_remove(1), (20, "b"));
    assert_eq!(unordered, [(10, "a"), (40, "d"), (30, "c")]);
    assert_eq!(unordered[1].0, 40); // インデックス 1 は今や別の ID に属する
}

位置を管理する HashMap<ID, usize> が別途ある場合、swap_remove 後に末尾から持ち越された要素のインデックスを更新しなければなりません。そうしないと、クエリは誤ったオブジェクトを指してしまいます。ID は論理的身元を解決し、マッピングはストレージの位置を解決します。これら2つはどちらも不可欠です。単に Vec の要素を Box に変更しても、移動しないヒープオブジェクトのアドレスがより安定するだけで、オブジェクトの削除や古い ID の再利用を防ぐことはできません。

HashMap：ハッシュ、等値性、ランダムシードが契約を構成する

等しいキーは、等しいハッシュ結果を生成しなければなりません。カスタム Hash と Eq は互いに整合している必要があります。キーを配置した後、内部可変性などによって、ハッシュや等値比較に関与する部分を変更してはいけません。そうしないとコレクションの契約が破綻します。

標準ライブラリの現在の実装は SwissTable に由来し、ランダムな状態を持つデフォルトのハッシュコンストラクタを使用しています。デフォルトのアルゴリズムと詳細は進化し得ます。ランダムな状態は、単なる「プロセス起動ごとに1つだけ存在し、すべてのテーブルで共有される固定シード」ではありません。代替ハッシュ関数を選択する際は、入力脅威モデル、キーの長さ、測定を組み合わせ、固定で 10% や 30% 高速であることは保証されません。HashMap

Entry API は、クエリと挿入の意図を1つの操作にまとめます。

use std::collections::HashMap;
fn main() {
    let mut counts = HashMap::new();
    for word in ["red", "blue", "red"] {
        *counts.entry(word).or_insert(0_u32) += 1;
    }
    assert_eq!(counts.get("red"), Some(&2));
}

HashMap の走査順序に依存して、安定したスナップショットやテストの期待値を生成しないでください。現在の実装では、len だけでなく capacity に基づいて走査する可能性があります。以前は大きかったが後で疎になったテーブルは、個別に測定する価値があります。安定した順序が必要な場合は、出力を明示的にソートするか、順序付き構造体を選択してください。

借用によるクエリで割り当てを回避する

use std::collections::HashMap;
fn main() {
    let mut values: HashMap<String, Vec<u32>> = HashMap::new();
    values.insert(String::from("red"), vec![1]);
    assert_eq!(values.get("red").map(Vec::len), Some(1));

    let mut constructed = 0;
    values.entry(String::from("red")).or_insert_with(|| {
        constructed += 1;
        vec![99]
    }).push(2);
    assert_eq!(constructed, 0);
    assert_eq!(values.get("red").unwrap(), &[1, 2]);
}

String キーは、対応する Borrow 契約により、2つの表現の等値性とハッシュが一致するため、str で借用してクエリできます。この機能は、任意のカスタム「文字列に変換可能」な型が Borrow<str> に適していることを意味しません。キーが大文字小文字を区別せずに比較され、通常の str が大文字小文字を区別して比較される場合、これらは同じキーセマンティクスを持ちません。

or_insert_with はキーが存在しない場合にのみ値を構築しますが、この例では entry に渡される String は呼び出し前に作成されています。ホットパスが主にヒットする場合、まず get_mut を行い、キーが存在しない場合に作成するパスを測定する価値があります。これによりヒット時のキー割り当てが削減されますが、ミス時のパスで1回余計な検索が行われる可能性があります。Entry を、キーと値の両方が自動的に遅延作成されるものだと理解しないでください。HashMap 借用クエリ

BTreeMap：順序はインターフェースの能力であり、性能のおまけではない

BTreeMap は Ord に基づいてソートされ、範囲クエリ、境界の検索、順序付き出力に適しています。ノード内部には複数の値が格納され、一定の局所性を持ちますが、木全体が連続した配列であるわけではありません。ソート済み Vec も、連続レイアウトと順序付き読み取りの両方を提供できるため、「キャッシュ局所性と順序は両立しない」という主張は成立しません。

use std::collections::BTreeMap;
fn main() {
    let values = BTreeMap::from([(10, "a"), (20, "b"), (30, "c")]);
    let selected: Vec<_> = values.range(15..=30)
        .map(|(&key, &value)| (key, value)).collect();
    assert_eq!(selected, [(20, "b"), (30, "c")]);
}

木かソート済み Vec かを選択する際は、更新頻度と範囲読み取りを比較してください。データを一括で構築し、長期間読み取り専用である場合、ソート済み Vec を測定する価値があります。頻繁なオンライン挿入・削除が必要な場合は、木の方が適しているかもしれません。キー比較に長い文字列が含まれる場合、比較自体のコストも考慮に入れる必要があります。

最寄りの境界クエリでは包含関係を明確にする

use std::collections::BTreeMap;
fn main() {
    let changes = BTreeMap::from([(10, "v1"), (20, "v2"), (30, "v3")]);
    let at = |time| changes.range(..=time).next_back().map(|(_, v)| *v);
    assert_eq!(at(9), None);
    assert_eq!(at(20), Some("v2"));
    assert_eq!(at(25), Some("v2"));

    let sorted = [(10, "v1"), (20, "v2"), (30, "v3")];
    let end = sorted.partition_point(|(time, _)| *time <= 25);
    let predecessor = end.checked_sub(1).map(|i| sorted[i].1);
    assert_eq!(predecessor, Some("v2"));
}

ここでは「time 以降でない最後の変更」をクエリしています。木では順序付き range に next_back を使用し、ソート済みスライスでは partition_point で time より大きい最初の位置を探します。スライスは最も早い時間より前で 0 を返すため、前驱が存在しない場合に備えて checked_sub が必要です。同じ時間に重複を許可する場合、Map では同じキーへの挿入は値を上書きしますが、Vec では複数の項目を保持できるため、並列イベントの順序を別途定義する必要があります。BTreeMap 範囲

VecDeque：論理的に連続でも物理的に連続ではない

リングバッファにより、先頭と末尾での効率的な操作が可能ですが、拡張が発生する可能性があります。as_slices は2つのスライスを返し、順序付けて連結したものが論理的な内容です。make_contiguous を使用して1つの連続スライスに整理できますが、整理自体には要素の移動が必要になる場合があります。VecDeque

use std::collections::VecDeque;
fn main() {
    let mut queue = VecDeque::from([1, 2, 3]);
    assert_eq!(queue.pop_front(), Some(1));
    queue.push_back(4);
    let (a, b) = queue.as_slices();
    let logical: Vec<_> = a.iter().chain(b).copied().collect();
    assert_eq!(logical, [2, 3, 4]);
}

Vec を FIFO として使用するために remove(0) を繰り返し呼び出さないでください。毎回残りの要素が移動するため、長いキューでは作業量が蓄積します。ビジネスロジックでバッチ読み取り後に全体をクリアするだけでよい場合、Vec が適しているかもしれません。コンテナの名前よりも、操作パターンの方が重要です。

論理キューは物理末端をどうまたぐか

A、B、C は論理的な要素、マス番号は物理位置です。先頭が末端に近くてもキュー順は A、B、C のままで、格納領域だけが 2 つに分かれます。剰余は折り返しを説明し、Rust で任意の範囲外添字を許すわけではありません。

$$p(i)=(h+i)\mathrm{mod}C,0\le i<\mathrm{len}\le C$$

BinaryHeap：スケジューリング順序は Ord の結果

標準の BinaryHeap は最大ヒープです。期限の早いタスクを先に実行する必要がある場合は、比較キーを Reverse でラップできます。同点のタスクで FIFO が必要な場合は、キーにキュー投入順序に基づいて割り当てられたシーケンス番号を含め、内部の並べ替え順序に依存しないでください。

use std::{cmp::Reverse, collections::BinaryHeap};
fn main() {
    let mut pending = BinaryHeap::from([
        Reverse((20u64, 0u64)),
        Reverse((10, 2)),
        Reverse((10, 1)),
    ]);
    assert_eq!(pending.pop(), Some(Reverse((10, 1))));
    assert_eq!(pending.pop(), Some(Reverse((10, 2))));
    assert_eq!(pending.pop(), Some(Reverse((20, 0))));
    assert_eq!(pending.pop(), None);

    let mut scores = BinaryHeap::from([9, 5, 3]);
    {
        let mut top = scores.peek_mut().unwrap();
        *top = 1;
    } // ガードは正常にデストラクトされ、新しいヒープ順序を維持する
    assert_eq!(scores.peek(), Some(&5));
}

シーケンス番号の割り当てとラップアラウンドはスケジューラの責任です。長寿命システムでは、オーバーフロー前に処理を行うべきであり、重複する番号が順序を静かに変更させてはいけません。実際のタスクでは、期限、シーケンス番号、タスク ID のみをヒープに格納し、大きなオブジェクトは独立したテーブルに保存することで、タスク本文が Ord に参加しないようにできます。

通常の iter はソートされた走査を提供しません。連続した pop によってのみ、ヒープの優先順位に従って要素が取り出されます。また、内部可変性によってヒープ内の要素の順序付けフィールドをこっそり変更しないでください。ヒープのトップを更新するには peek_mut を使用できますが、任意のタスクの期限を変更する場合は、明示的な削除/再挿入またはバージョン化による無効化戦略が必要です。後者のアプローチでは、古いエントリをヒープに残したままにでき、ポップ時にバージョンをチェックしてスキップしますが、古くなったエントリの蓄積を制御する必要があります。BinaryHeap の契約

実際のコストを測定する

要素数、キーの分布、挿入・削除の比率、容量のピーク、出力順序の要件を記録し、構築フェーズと定常状態の2つのフェーズでテストしてください。プリアロケーションは拡張回数を減らしますが、長期的なメモリ使用量を増やす可能性があります。shrink_to_fit も RSS がすぐに下がるとは限らず、その先にはアロケータとオペレーティングシステムが横たわっています。

コレクションの安全な API を使用することは、すべての論理条件がコンパイラによって証明されることを意味しません。インデックスの有効性、ビジネス ID のライフタイム、ハッシュの一貫性、ソート規則は、設計の一部であり続けます。