23

私の質問は基本的に、Qt コンテナーとしていつ選択するかQVector、いつ選択するかです。QList私がすでに知っていること：

  1. Qt ドキュメント: QList クラス

ほとんどの場合、QList が適切なクラスです。そのインデックスベースの API は、QLinkedList の反復子ベースの API よりも便利であり、アイテムをメモリに格納する方法により、通常は QVector よりも高速です。また、実行可能ファイル内のコードが少なくなります。

  1. この非常に人気のある Q&A: QVector vs QListにも同じことが書かれています。また、QList を優先します。

  2. しかし、最近の Qt World Summit 2015 で KDAB は「なぜ QList が有害なのか」を発表しましたが、基本的には次のとおりです。

有害と見なされる QList

QList を使用しないで、Q_DECLARE_TYPEINFO を使用してください

私が理解している限りでは、QList新しい要素をヒープに割り当てるとき、ほとんどすべての型が非効率的であるという考えを理解しています。新しい要素を追加するたびに、new(要素ごとに 1 回) が呼び出されますが、これは に比べて非効率的QVectorです。

これが、私が理解しようとしている理由です:QVectorデフォルトのコンテナーとして選択する必要があるのはどれですか?

4

8 に答える 8

5

QListの配列ですvoid*。

通常の操作でnewは、ヒープ上の要素であり、それらへのポインターをvoid*配列に格納します。リンク リストと同様に、リストに含まれる要素への参照 (ただし、リンク リストとは異なり、イテレータではありません!) は、要素がコンテナーから再度削除されるまで、すべてのコンテナーの変更の下で有効なままであることを意味します。したがって、名前は「リスト」です。このデータ構造は配列リストと呼ばれ、すべてのオブジェクトが参照型 (Java など) である多くのプログラミング言語で使用されます。これは、すべてのノードベースのコンテナーと同様に、非常にキャッシュに適していないデータ構造です。

ただし、配列リストのサイズ変更は、型に依存しないヘルパー クラス ( ) に組み込むことができますQListData。これにより、実行可能なコードのサイズがいくらか節約されるはずです。QList私の実験では、と のどちらが最も実行可能なコードを生成しないQVectorかを予測することはほぼ不可能です。std::vector

これは、 pimpl ポインター以外の何もない 、 などQStringの多くの Qt 参照のような型に適したデータ型でした。QByteArrayこれらの型についてQList、重要な最適化が行われました。型がポインターより大きくない場合 (この定義はプラットフォームのポインター サイズ (32 ビットまたは 64 ビット) に依存することに注意してください)、オブジェクトはヒープ割り当てオブジェクトではなく、void*直接スロット。

ただし、これは型が自明に再配置可能である場合にのみ可能です。つまり、を使用してメモリ内で再配置できますmemcpy。ここでの再配置とは、オブジェクトmemcpyを別のアドレスに移動し、重要なことに、古いオブジェクトのデストラクタを実行しないことを意味します。

そして、これは物事がうまくいかなくなったところです。Java とは異なり、C++ ではオブジェクトへの参照はそのアドレスであるためです。また、元のでは、このプロパティが保持されなくなっQListた配列にオブジェクトを配置することにより、オブジェクトがコレクションから再び削除されるまで、参照は安定していました。void*これは、すべての意図と目的のための「リスト」ではなくなりました。

ただし、 a よりも厳密に小さい型を avoid*に配置することも許可されたため、問題が発生し続けましたQList。しかし、メモリ管理コードはポインタ サイズの要素を想定しているためQList、パディング (!) を追加します。つまりQList<bool>、64 ビット プラットフォームの a は次のようになります。

[ | | | | | | | [ | | | | | | | [ ...
[b|   padding   [b|   padding   [b...

キャッシュ ラインに 64 個の bool を入れる代わりに、QVector8のみQListを管理します。

ドキュメントがQList適切なデフォルト コンテナを呼び出し始めたとき、事態はあらゆる割合でうまくいきませんでした。そうではありません。元のSTLの状態：

VectorSTL コンテナー クラスの中で最も単純で、多くの場合、最も効率的です。

Scott Meyer の効果的な STLstd::vectorには、"Prefer over..."で始まる項目がいくつかあります。

一般的に正しいことは、Qt を使用しているからといって、C++ が突然間違っているわけではありません。

Qt 6 では、その特定の設計ミスが修正されます。QVectorそれまでの間、またはを使用してstd::vectorください。

于 2016-03-01T23:00:33.387 に答える
3

QList の要素型のサイズがポインターのサイズよりも大きい場合、QList は QVector よりも優れたパフォーマンスを発揮します。これは、オブジェクトをシーケンシャルに格納するのではなく、ヒープ コピーへのポインターをシーケンシャルに格納するためです。

私は反対のことを言う傾向があります。アイテムを通過すると、さらに悪化します。それをヒープ上のポインタとして格納する場合、QList は QVector よりもはるかに悪いものではないでしょうか? シーケンシャル ストレージ (常に QVector) が非常に優れている理由は、キャッシュに適しているためです。ポインターを格納すると、データの局所性が失われ、キャッシュ ミスが発生し始め、パフォーマンスが低下します。

「デフォルト」コンテナ IMHO は QVector (または std::vector) である必要があります。大量の再割り当てが心配な場合は、妥当な量を事前に割り当て、1 回限りのコストを支払うと、長期的にはメリットがあります。

パフォーマンスの問題が発生した場合は、デフォルトで *Vector を使用し、プロファイルを作成して、必要に応じて変更してください。

于 2015-11-12T06:56:27.373 に答える
0

QList は、ドキュメントに記載されているように、一般的に使用するのに最適なコンテナーです。要素の型のサイズが <= ポインターのサイズ = マシン & OS ビット数 = 4 または 8 バイトの場合、オブジェクトは QVector と同じ方法でメモリに順次格納されます。QList の要素型のサイズがポインターのサイズよりも大きい場合、QList は QVector よりも優れたパフォーマンスを発揮します。これは、オブジェクトをシーケンシャルに格納するのではなく、ヒープ コピーへのポインターをシーケンシャルに格納するためです。32 ビットの場合、図は次のようになります。

sizeof( T ) <= sizeof( void* )
=====
QList< T > = [1][1][1][1][1]
                   or
             [2][2][2][2][2]
                   or
             [3][3][3][3][3]
                   or
             [4][4][4][4][4] = new T[];

sizeof( T ) > sizeof( void* )
=====
QList< T > = [4][4][4][4][4] = new T*[]; // 4 = pointer's size
              |   |  ...  |
           new T new T   new T

通常 OpenGL プログラミングの場合と同様に、要素のサイズに関係なく、オブジェクトをメモリ内に順番に配置する場合は、QVector を使用する必要があります。

ここでは、QList の内部構造について詳しく説明します。

于 2015-11-09T13:19:35.230 に答える
0

DataType クラスがあるとします。

QVector - 次のようなオブジェクトの配列:

// QVector<DataType> internal structure
DataType* pArray = new DataType[100];

QList - 次のようなオブジェクトへのポインタの配列:

// QList<DataType> internal structure
DataType** pPointersArray = new DataType*[100];

したがって、QVector では、インデックスによる直接アクセスが高速になります。

{
// ...
cout << pArray[index]; //fast
cout << *pPointersArray[index]; //slow, need additional operation for dereferencing
// ...
}

ただし、sizeof(DataType) > sizeof(DataType*) の場合、QList のスワッピングは高速になります。

{
// QVector swaping
DataType copy = pArray[index];
pArray[index] = pArray[index + 1];
pArray[index + 1] = copy; // copy object

// QList swaping
DataType* pCopy = pPointersArray [index];
pPointersArray[index] = pPointersArray [index + 1];
pPointersArray[index + 1] = pCopy; // copy pointer
// ...
}

したがって、要素間で操作を交換せずに直接アクセスする必要がある場合 (たとえば、並べ替えなど)、または sizeof(DataType) <= sizeof(DataType*) の場合、より良い方法は QVector を使用することです。それ以外の場合は、QList を使用します。

于 2015-11-30T12:22:47.413 に答える