1. ホーム
  2. rust

[解決済み] Rustにはキューとスタックコレクションがありますか?

2022-02-08 10:41:53

質問

FIFOコレクションやLIFOコレクションが必要な場合(基本的に push , popfront / back ) Rustでは何を使うべきでしょうか?例えば std::queue または std::stack をC++で作成します。

どのように解決するのですか?

まず第一に、Rustは、(標準ライブラリでは)以下のようなレイテンシが保証されたライブラリを提供していません。 追加 要素で構成されています。Rustコレクションは一般に、新しい要素を追加する際にメモリを割り当てることがあり、メモリの割り当てには最悪の場合、無限の時間がかかる可能性があります。

とはいえ、それぞれのケースで2つの候補があります。

  • スタックは Vec または LinkedList (どちらも機能 pop_backpush_back )
  • の上に実装することができます。 VecDeque または LinkedList (どちらも機能 pop_frontpush_back )

との違いは Vec*LinkedList の各呼び出しに対して、後者が単純化されていることです。 push_back を使用すると、メモリの割り当てが行われます。一方では、これは push_back はコレクション内の要素数に依存しませんが、一方で......メモリの割り当てには本当に長い時間がかかるかもしれません。

前者は少し複雑です。

  • よりキャッシュに優しいため、スループットが向上します。
  • 追加容量があり、非割り当てを保証します。 push_back 余力がある限り
  • を維持しています。 アモルファス O(1) push_back 余剰生産能力を事前に予約していない場合でも

一般的には、以下のように使用することをお勧めします。 Vec をスタックに、そして VecDeque はキューです。