0

次の問題があります: この (簡略化された) 構造を考えてみましょう:

struct Task {
    int priority;
    std::string description;
    // Some other fields
};

今、私はすべてのタスクのセットを持ち、それを使っていくつかの作業をしたいと思っています. したがって、すべての要素が等しいことを確認する等価演算子があります。

bool isEqual(const Task& lhs, const Task& rhs) {
    return lhs.priority == rhs.priority &&
        lhs.description == rhs.description &&
        // Some other fields
        ;
}

このために、正常に機能する std::unordered_set を使用しました。

しかし今、これらのタスクを優先度順に並べ替えて（最も優先度の高いタスクを取得するために）セットに入れたいと思っています。明らかに、これは std::unordered_set では不可能なので、次の less 演算子を使用して std::set を試しました。

bool lessTask(const Task& lhs, const Task& rhs) {
    return lhs.priority < rhs.priority;
}

しかし、これは厳密な弱い順序付けによって、優先度が等しい場合に2つのタスクが等しいことを意味します。これは望ましくありません(同等性チェックのために isEqual メソッドを維持したい)。

一連のタスクを達成するための最良の方法は何ですか?要素を非常に高速に挿入でき、重複するエントリ (私の isEqual 関数で定義) がなく、優先度が最も高いタスクを非常に高速に取得できますか?
私は特定のSTLコンテナに縛られていませんが、サードパーティのライブラリを使用したくありません(ブーストさえも)。

4

2 に答える 2

1

要素をマップに配置するときは、通常、クラスのすべてのメンバーを に追加する必要がありますless。そうしないと、正しく動作しません。マップに含まれる約 15 の異なる常に変化するクラスのシステムを作成しなければならなかったとき、それは大きな課題でした。コンパイル時のリフレクションを本当に見逃し始めたのはこのときでした。

ちなみに、マップの代わりに優先キュー( std::make_heap) を使用できます。優先度ヒープは平等を気にせず、最も優先度の高いタスクを最初に提供します。

于 2015-11-03T18:46:48.113 に答える
1

最初に書くget_tie：

// auto or decltype(auto)
auto get_tie(const Task& task) {
  return std::tie(lhs.priority, lhs.description, /* some other fields */ );
}

C++11 では、->decltype末尾の戻り値の型で本体を繰り返すか、マクロを使用して繰り返しを避ける必要があります。

#define RETURNS(...) decltype(__VA_ARGS__) { return __VA_ARGS__; }
auto get_tie(const Task& task)->
RETURNS( std::tie(lhs.priority, lhs.description, /* some other fields */ ) )

簡単get_tieに解決できれば、問題は解決します。

bool isEqual( Task const& lhs, Task const& rhs ) {
  return get_tie(lhs)==get_tie(rhs);
}
bool isLess( Task const& lhs, Task const& rhs ) {
  return get_tie(lhs) < get_tie(rhs);
}

に渡すisLessか、を使用してstd::setビルドします。std::vectorstd::sortisLess

ここで、生の参照で比較が実際に機能しない場合は、より複雑なものtieに置き換える必要がある場合があります。get_tie

于 2015-11-03T20:23:34.390 に答える