Rust のキューおよびスタックコレクション

Nilesh Katuwal 2023年6月21日

Rust Rust Stack

この記事は、Rust におけるキューコレクションとスタックコレクションの存在について説明しています。

さびコレクション

Rust の標準コレクションライブラリには、汎用プログラミングで最も頻繁に使用されるデータ構造の効率的な実装が含まれています。その結果、標準の実装を使用する場合、2つのライブラリは多くのデータ変換を必要とせずに通信できるはずです。

まず、おそらく Vec を使用する必要があります。これら 2つのコレクションは、汎用データのほとんどのストレージおよび処理シナリオをカバーしています。

彼らは自分の仕事に優れています。標準ライブラリの他のすべてのコレクションには、最適な選択となる特定のユースケースがありますが、これらのユースケースはニッチです。

Vec と HashMap が技術的に劣っていたとしても、それらはおそらく十分な出発点です。

Rust で利用可能なコレクションは、以下の 4つの主要なカテゴリにグループ化できます。

Rust のキューデータ構造は、要素を格納するために使用されます。 Rust のキューは、先入れ先出しを意味する FIO 方式で動作します。

これは、Rust コレクションライブラリに含まれている標準キューです。これは線形データ構造です。

キューは、それを操作するために使用できるいくつかの操作を提供します。任意の数の要素を含めることができます。実装全体は、Rust のベクトルデータ構造に基づいています。

構文：

let mut variable_name : Queue<queue_size> = queue![];

スタックは、追加および削除できるアイテムのコレクションですが、次の順序でのみ可能です: 後入れ先出し (LIFO)。たとえば、満員電車に乗った場合、他の乗客が同様に降りるために、自分が最初に降りる必要があります。

オブジェクトの追加は通常 push と呼ばれ、商品の削除は通常 pop と呼ばれます。これは、これらの関数が Vec (ベクトル) データ構造を使用して Rust に実装されているためです。

新しいスタックを作成するには、次の構文を使用できます。

let s = Stack { stack: Vec::new() };

Rust は、標準ライブラリに要素を追加するための保証されたレイテンシを備えたライブラリを提供しません。 Rust コレクションに要素を追加すると、メモリが割り当てられる場合があります。

最悪の場合、メモリの割り当てに無限の時間がかかることがあります。

いずれの場合も、候補は 2つあります。

スタックは、Vec または LinkedList のいずれかの上に実装できます。どちらも pop back と push back をサポートしているためです。
キューは、VecDeque または LinkedList のいずれかの上に実装できます。これは、どちらも pop front と push back をサポートするためです。

Vec と LinkedList にはいくつかの違いがあります。後者はより単純です: push back の呼び出しごとにメモリが割り当てられます。

一方では、プッシュバックのコストはコレクション内に既にあるオブジェクトの数とは無関係であるため、これは有利です。それでも一方で、メモリの割り当てには時間がかかる場合があります。

前者は、次の理由により、もう少し複雑です。

キャッシュフレンドリーな性質により、スループットが高くなります。
追加の容量があり、余分な容量がある限りプッシュバックが割り当てられないようにします。超過容量が事前に予約されていない場合でも、償却された O(1) プッシュバック を維持します。

スタックには Vec を、キューには VecDeque を使用することをお勧めします。