5

次のシナリオで並べ替えて維持する必要のあるstd::list<MyObject*> objectListコンテナがあります。

  • 各オブジェクトには、コストを提供する特定のフィールドがあります（たとえば、float値）。そのコスト値は、2つのオブジェクトを浮動小数点数であるかのように比較するために使用されます
  • コレクションは順序付け（昇順）する必要があり、新しく挿入された要素の正しい位置をすばやく見つける必要があります。
  • （コストの観点から）最も低い要素を削除することが可能であり、いくつかの任意に配置された要素のコストを更新することも可能です。次に、リストは、すでにソートされている性質を利用して、できるだけ早く並べ替える必要があります。

他のstlコンテナ/メカニズムを使用して、3つの動作プロパティを許可できますか？これはヒープによく似ておりmake_heap、リストを並べ替えるには、を使用するのが良い方法だと思いました。これらのポインターに依存する他のデータ構造がいくつかあるため、ポインターのコンテナーが必要です。

では、ポインターに対応し、指定された型の比較演算子を調べて並べ替えることができる、より優れたコンテナーを選択するにはどうすればよいでしょうか。

明確化：シナリオに最適で、その問題のポインターまたは参照を正常にラップできるstlコンテナーが必要です。（たとえば、std::setコンテナは良い候補になる可能性があることを簡単に読みましたが、私はそれについての経験がありません）。

以下の回答に基づく現在の実装：

struct SHafleEdgeComparatorFunctor
    {
        bool operator()(SHEEdge* lhs, SHEEdge* rhs)
        {
            return (*lhs) < rhs;
        }
    };

std::multiset<SHEEdge*, SHafleEdgeComparatorFunctor>    m_edges;

もちろん、SHEEdgeデータ構造にはオーバーロードされた演算子があります。

bool operator<(SHEEdge* rhs) 
    {
        return this->GetCollapseError() < rhs->GetCollapseError();
    }
4

3 に答える 3

4

私は確かに使用しますstd::set。要件のトリッキーな点は、既存の要素を更新することです。

Astd::setは常にソートされます。便利な比較演算子を使用してポインタをクラスにラップするか、比較述語をセットに渡す必要があります。

次に、並べ替えられたプロパティを自動的に取得し、最下位の要素を一定時間削除します。

また、ログの複雑さでコスト値が更新されます。セットからオブジェクトを削除して、再度追加するだけです。これは、ソートされたコンテナーの場合と同じくらい高速になります。

セット内での挿入と削除は高速です。

于 2013-03-25T11:58:53.277 に答える
2

私は生のポインターの代わりにのようなスマートポインターを使い始めます（生のポインターは、関数パラメーターとして渡されるポインターのようにポインターを監視している場合などに適していますが、この場合のように所有権のセマンティクスがある場合は、スマートポインタ）。shared_ptr

次に、std::vectorコンテナとして開始します。

だから、作ってみてくださいvector<shared_ptr<MyObject>>。

と比較してパフォーマンスを測定できますlist<shared_ptr<MyObject>>。

（これはノードベースのコンテナであり、各ノードにはある程度のオーバーヘッドがあるため、std::listよりもオーバーヘッドが多いことに注意してください。代わりに、データを格納するために連続したメモリのチャンクを割り当てます。この場合はsです。-フレンドリー」など）std::vectorstd::vectorshared_ptrstd::vector

一般的に、std::vector非常に優れたパフォーマンスを提供し、「最初の選択肢」のコンテナーとして適したオプションです。いずれにせよ、あなたのマイレージは非常に高いかもしれません、そして最も良いことはあなたの特定のケースでより良い理解を得るためにパフォーマンス（速度）を測定することです。

于 2013-03-25T11:36:17.827 に答える
1

私があなたが何を求めているかを正しく理解しているなら、あなたは使用する正しい容器を探しています。

確かstd::setに、あなたがやりたいことの種類の正しいコンテナのようですが、それはすべてのユースケースに依存します

  • 要素へのO（1）アクセスが必要ですか？
  • 最も重要なコストがかかる使用される操作は何ですか？

std::setキーを使用して要素を並べ替え、重複を許可しません（重複が必要な場合は、を参照してくださいstd::multiset）。要素を追加すると、その要素は自動的に正しい位置に挿入されます。オブジェクトはnullになる可能性があるため、通常、生のポインタをキーとして使用することは望ましくありません。

std::vector<std::shared_ptr>>@MikeProが言ったように、別の代替手段として、ポインターを手動で削除する必要がないように（たとえば、例外が発生した場合のメモリリークを回避するために）スマートポインター内にポインターを配置することをお勧めします。ベクトルを使用する場合は、ヘッダーにあるstd::sort、などの関数を使用する必要があります。std::find<algorithm>std::vector::insert

通常、この画像はコンテナを見つけるのに役立ちます。完璧ではありませんが（表示されているものよりも少し詳しく知る必要があるため）、通常はうまく機能します。

標準コンテナの選択

于 2013-03-25T11:49:52.833 に答える