[解決済み] QVectorとQListの比較

質問

整数のリストがあり、それを反復処理する必要があるのですが、配列では不十分です。 この場合 vectors と lists と、種類を選ぶ前に知っておくべきことはありますか？

明確にするために、私はQTドキュメントを読みましたが、これは私が知っていることの範囲です。

QList<T> , QLinkedList<T> そして QVector<T> は同様の機能を提供します。以下はその概要です。

• ほとんどの目的のために QList は使うべきクラスです。そのインデックスベースの API は QLinkedList's イテレータベースの API よりも便利で、通常は QVector よりも高速です。また、実行ファイル内のコードもより少なく展開されます。
• もし、本当のリンクリストが必要で、リストの途中への定時挿入が保証され、 インデックスではなくアイテムへのイテレータが必要な場合は QLinkedList .
• アイテムが隣接したメモリ位置を占めるようにしたい場合は QVector .

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

QVector とはほとんど類似しています。 std::vector と似ています。 QList の方が boost::ptr_deque との見かけ上の関連性はあるものの std::list . これは、オブジェクトを直接格納するのではなく、オブジェクトへのポインタを格納します。 両端での素早い挿入や、再割り当ての際にコピーコンストラクタの代わりにポインタをシャッフルするなどの利点はありますが、実際の std::deque または std::vector というように、ヒープを大量に割り当てることになります。 これは、小さなオブジェクトのヒープ割り当てを回避し、空間的な局所性を回復するためのいくつかの決定がありますが、私が理解する限り、それは int .

QLinkedList は std::list と似ていて、その欠点もすべて持っています。 一般的に言って、これはコンテナの最後の選択肢であるべきです。

QTライブラリは QList オブジェクトの使用を強く推奨しているので、あなた自身のコードでそれらを支持することは、時にはいくつかの不必要な退屈を避けることができます。 余分なヒープの使用と実際のデータのランダムな位置は、理論的にはいくつかの状況で問題になりますが、多くの場合、無視できません。 ですから、私は QList プロファイリングで QVector . 連続的なアロケーションが重要だと考えている場合 [つまり T[] ではなく QList<T> で始める理由にもなります。 QVector で始める理由にもなります。

もしあなたがコンテナ一般について尋ねていて、QTドキュメントを参照として使っただけなら、上記の情報はあまり役に立ちません。

An std::vector は、サイズを変更することができる配列です。 すべての要素が隣り合わせに格納されており、個々の要素に素早くアクセスできます。 欠点は、挿入が一端でしか効率的でないことです。 真ん中や最初に何かを入れると、スペースを空けるために他のオブジェクトをコピーしなければなりません。 ビッグ・オー表記では、末尾の挿入は O(1)、それ以外の場所の挿入は O(N)、ランダムアクセスは O(1) です。

アン std::deque は似ていますが、オブジェクトが互いに隣り合って格納されていることを保証するものではなく、両端での挿入が O(1) であることを可能にします。 また、一度に割り当てるメモリのチャンクを小さくする必要がありますが、これは時に重要なことです。 ランダムアクセスは O(1)、途中の挿入は O(N) であり、これは vector . 空間的な局所性は std::vector よりも悪いですが、オブジェクトはクラスタ化される傾向があるので、ある程度の利点は得られます。

アン std::list はリンクリストです。 3 つの標準的なシーケンシャル コンテナの中で最も多くのメモリ オーバーヘッドを必要としますが、どこにでも高速に挿入できます... ただし、挿入する必要がある場所を事前に知っていることが条件です。 個々の要素へのランダムアクセスはできないので、O(N) で反復する必要があります。 しかし、一度そこに到達すれば、実際の挿入はO(1)である。 の最大の利点は std::list の最大の利点は、それらを素早くつなぎ合わせることができることです。もし、値の範囲全体を別の std::list であり、全体の演算はO(1)である。 また、リストへの参照を無効にすることもはるかに難しく、これは時に重要です。

一般的なルールとして、私は std::deque から std::vector ただし、生の配列を期待するライブラリにデータを渡す必要がある場合は、この限りではありません。 std::vector は連続であることが保証されているので &v[0] はこの目的のために機能します。 私は、最後に std::list を最後に使ったのは覚えていませんが、それはほぼ間違いなく、参照が有効であり続けることをより強く保証する必要があったからです。