4

さまざまな C++11 標準コンテナーとコンテナー アダプター (オプションで boost/Qt も含む) の重要なプロパティの包括的な概要/リファレンスを探していますが、通常のコンテナーごとのドキュメントではなく、これらのプロパティによってインデックスが付けられています (詳細については、下）。

私が念頭に置いているプロパティには、頭の上から次のものが含まれます。

  • 挿入機能 (前面/背面/任意)。
  • 取り外し機能 (前面/背面/任意)。
  • アクセス機能 (フロント/バック/一方向/双方向トラバーサル/ランダム アクセス)。
  • 前述の操作の複雑さと、反復子の無効化規則。
  • 独自性？順序付けられました？連想？連続収納？事前予約？

コメント/編集をためらわないでください。

目標は、そのドキュメントを参考にして、適切なジョブに適切なコンテナー/アダプターを選択することです。さまざまな個別のドキュメントを何度も何度も確認する必要はありません (ひどい記憶があります)。

理想的には、基本的な制約をすばやく参照できるだけでなく、意思決定を可能にするために、プロパティとコンテナーの種類 (テーブルのようなものなど) の両方でインデックスを作成する必要があります。しかし、実際にはプロパティごとのインデックスが最も重要です。これは、ドキュメントで検索するのが最も難しいためです。

誰もそのような文書を作成していなかったとしたら、私は非常に驚くだろうが、私の Search-fu はこの文書で失敗している.

注:これらすべての情報を要約するように求めているわけではありません (本当に必要な場合は自分で要約します。その場合は結果をここに投稿します) 。それらの要件。このようなものは良いスタートですが、ご覧のとおり、メンバー関数に制限されているため、必要な情報の多くがまだ不足しています。

ご清聴ありがとうございました。

4

1 に答える 1

3

必要なものすべてを提供する 1 つの文書を私は知りませんが、そのほとんどはどこかにカタログ化されています。

  • このリファレンス サイトには、すべてのコンテナーのすべてのメンバー関数を含む大きなテーブルがあります。
  • このSO の質問には、複雑さの保証の大きな表があります。
  • This SO questionは、コンテナを選択するための決定木を提供します。

O(1)コンテナー メンバー関数の複雑さの要件は、(償却) 、O(log N)、O(N)、および(標準ライブラリのアルゴリズム ドメインに実際に交差するO(N log N)メンバー関数) の4 つのカテゴリしかないため、覚えるのがそれほど難しくありません。 std::list::sort()cpp 参照コンテナー テーブルの 4 色コード バージョン。

std::vectorプロファイラーがボトルネックを示さない限り、適切なコンテナーを選択することは、常に使用するのと同じくらい簡単です。そのポイントに到達した後、空間/時間の複雑さ、データの局所性、検索の容易さと挿入/変更の容易さ、および余分な不変条件 (並べ替え、一意性、イテレータの無効化規則) の間で厳しいトレードオフを行う必要があります。

最も難しい部分は、使用しているアルゴリズム (時間要件) に対してコンテナー (スペース要件) のバランスを取る必要があることです。コンテナは、他のコンテナがアルゴリズムを使用してのみ模倣できる不変条件を維持できます（たとえばstd::map、そのキーでソートされます）（たとえばstd::vector、std::sort同じ挿入の複雑さはありません）。したがって、コンテナ テーブルを完成させた後は、アルゴリズムに対して同様のことを行うようにしてください。

最後に、 Boost.MultiIndexに言及せずにコンテナーの概要を完成させることはできません。選択する必要がない場合があるからです。

于 2013-05-03T18:35:55.640 に答える