0

パラメータの1つで並べ替えられたオブジェクトの長いリストが必要です。C ++でこれを行うための最速の方法は何ですか？このリストに要素を追加および削除し、それでもその特定のパラメーターでソートできるようにする必要があります。

Class Foo {
private:
  int rank;
}

Fooすべてのオブジェクトを昇順でリストしたいのですが、新しいオブジェクトが追加または削除されたときに、オブジェクトは順序の正しい位置に配置されるはずです。同じオブジェクトが複数存在する可能性もあるrankため、Key-Valueは使用できません。

C ++でこれを行う方法はありますか？make_heap（）を見ていましたが、オブジェクトでどのように使用するか（または使用できるかどうか）がわかりません。

4

1 に答える 1

2

まず、おそらく（このようなもの）を定義する必要がありoperator<ますFoo...

inline bool operator< (const Foo& lhs, const Foo& rhs) {
  return lhs.rank < rhs.rank;
}

これは、の友達として宣言する必要がありますFoo。

class Foo {
 public:
  explicit Foo(int rank_init) : rank(rank_init) {}
  friend bool operator< (const Foo&, const Foo&);
 private:
  int rank;
};


これで、 sを昇順で並べ替えたstd::multiset<Foo>ままにするを 作成できます。Foorank

std::multiset<Foo> foo_multiset;
foo_multiset.insert(Foo(5));  // 5
foo_multiset.insert(Foo(3));  // 3, 5
foo_multiset.insert(Foo(1));  // 1, 3, 5
foo_multiset.insert(Foo(3));  // 1, 3, 3, 5
size_t erased_count(foo_multiset.erase(Foo(3)));  // 1, 5 (erased_count == 2)

ただし、特定の場合にこれが「最速」のオプションになるという保証はありません。そのためにプロファイリングする必要があります。std::vector<Foo>要素の数、挿入/消去操作の頻度、およびSTLの実装によっては、ソートがニーズに適していることがわかります。

スコットマイヤーズの効果的なSTLは、これが項目23にどのように当てはまるかを説明しています。

于 2012-04-11T01:46:48.143 に答える