5

メンバー x、y、z、および w を持つ構造体があります。C++で最初にx、次にy、z、最後にwで効率的にソートするにはどうすればよいですか?

4

4 に答える 4

6

構造体をstd::tupleusingstd::tieに変換し、辞書式比較を使用できますstd::tuple::operator<。ラムダを使用した例を次に示しますstd::sort

#include <algorithm>
#include <tuple> 
#include <vector>

struct S 
{
   // x, y, z, w can be 4 different types!
   int x, y, z, w;
};

std::vector<S> v;

std::sort(std::begin(v), std::end(v), [](S const& L, S const& R) {
    return std::tie(L.x, L.y, L.z, L.w) < std::tie(R.x, R.y, R.z, R.w);
});

この例std:sortでは、オンザフライで比較演算子を提供します。常に辞書式比較を使用したい場合は、 によって、またはおよびのような順序付けられた連想コンテナーによってbool operator<(S const&, S const&)自動的に選択される非メンバーを作成できます。std::sortstd::setstd::map

効率については、オンライン参照から:

すべての比較演算子はショートサーキットです。比較の結果を決定するために必要な範囲を超えてタプル要素にアクセスすることはありません。

C++11 環境を使用している場合は、std::tieここに記載されている手書きのソリューションよりも優先してください。エラーが発生しやすく、読みにくくなります。

于 2013-06-13T06:43:34.940 に答える
2

独自の比較演算子をロールすると、オブジェクトをstd::maps または invokeに自由にスローできますstd::sort。この実装は単純になるように設計されているため、必要に応じて簡単に検証および変更できます。x、y、z、および w を比較するためだけに使用operator<することで、これらの変数がまだ比較可能でない場合 (たとえば、それらが ints、double、std::strings ではなく独自の構造体である場合) に実装する必要がある演算子の数を最小限に抑えます。等。）。

bool operator<(const Q& lhs, const Q& rhs)
{
    if (lhs.x < rhs.x) return true;
    if (rhs.x < lhs.x) return false;
    if (lhs.y < rhs.y) return true;
    if (rhs.y < lhs.y) return false;
    if (lhs.z < rhs.z) return true;
    if (rhs.z < lhs.z) return false;
    if (lhs.w < rhs.w) return true;
    return false;
}

型は、-1、0、または 1 を返す比較関数を定義して、より小さい、等しい、またはより大きい<ことを示します。多くの作業を繰り返すことになります (最後の文字だけが異なる長いテキスト文字列を比較することを検討してください)。x、y、z、および w がたまたまそのような型であり、より高性能な比較関数を持っている場合は、次の方法で全体的なパフォーマンスを向上させることができます。<===!=>=><!=>

bool operator<(const Q& lhs, const Q& rhs)
{
    int c;
    return (c = lhs.x.compare(rhs.x) ? c :
           (c = lhs.y.compare(rhs.y) ? c :
           (c = lhs.z.compare(rhs.z) ? c :
           lhs.w < rhs.w;
}
于 2013-06-13T06:43:35.237 に答える