10

関数ポインター、関数オブジェクト (またはブースト ラムダ) を std::sort に渡して、並べ替えたいコンテナーの要素の厳密な弱い順序付けを定義できます。

ただし、場合によっては (これを何度か実行したことがあります)、「プリミティブな」比較を連鎖させたい場合があります。

些細な例として、連絡先データを表すオブジェクトのコレクションを並べ替える場合があります。場合によっては、次のように並べ替えたいことがあります。

姓、名、市外局番
. 別の時に
名前苗字
- また別の時
年齢、名前、市外局番
...など

これで、ケースごとに追加の関数オブジェクトを作成できますが、これは DRY の原則に違反します。特に各比較がさほど重要でない場合はなおさらです。

比較関数の階層を記述できるはずです-低レベルのものは単一のプリミティブな比較（たとえば、名<名）を実行し、次に高レベルのものは低レベルのものを連続して呼び出します（おそらく&& (短絡評価を利用する) を使用して複合関数を生成します。

このアプローチの問題点は、std::sort がバイナリ述語を取ることです。述語は bool のみを返すことができます。したがって、それらを構成している場合、「false」が等しいかより大きいかを示すことはできません。低レベルの述語が 3 つの状態を持つ int を返すようにすることができますが、それらを std::sort で単独で使用するには、高レベルの述語でそれらをラップする必要があります。

全体として、これらは克服できない問題ではありません。必要以上に難しいように思えます-そして確かにヘルパーライブラリの実装が必要です.

したがって、ここで役立つ既存のライブラリ (特に std または boost ライブラリの場合) を知っている人はいますか?

[アップデート]

いくつかのコメントで述べたように、私は先に進み、これを管理するクラスの独自の実装を作成しました。それはかなり最小限であり、おそらく一般的にいくつかの問題があります。しかし、それに基づいて、興味のある人のために、クラスはここにあります：

http://pastebin.com/f52a85e4f

また、いくつかのヘルパー関数 (テンプレート引数を指定する必要を避けるため) は次のとおりです。

http://pastebin.com/fa03d66e

4

6 に答える 6

8

次のようなチェーン システムを構築できます。

struct Type {
  string first, last;
  int age;
};

struct CmpFirst {
  bool operator () (const Type& lhs, const Type& rhs) { return lhs.first < rhs.first; }
};

struct CmpLast {
  bool operator () (const Type& lhs, const Type& rhs) { return lhs.last < rhs.last; }
};

struct CmpAge {
  bool operator () (const Type& lhs, const Type& rhs) { return lhs.age < rhs.age; }
};

template <typename First, typename Second>
struct Chain {
  Chain(const First& f_, const Second& s_): f(f_), s(s_) {}

  bool operator () (const Type& lhs, const Type& rhs) {
    if(f(lhs, rhs))
      return true;
    if(f(rhs, lhs))
      return false;

    return s(lhs, rhs);
  }

  template <typename Next>
  Chain <Chain, Next> chain(const Next& next) const {
     return Chain <Chain, Next> (*this, next);
  }

  First f;
  Second s;
};

struct False { bool operator() (const Type& lhs, const Type& rhs) { return false; } };

template <typename Op>
Chain <False, Op> make_chain(const Op& op) { return Chain <False, Op> (False(), op); }

それを使用するには：

vector <Type> v;  // fill this baby up

sort(v.begin(), v.end(), make_chain(CmpLast()).chain(CmpFirst()).chain(CmpAge()));

最後の行は少し冗長ですが、意図したことは明らかだと思います。

于 2008-11-08T18:45:16.847 に答える
2

あなたはこれを試すことができます：

使用法：

struct Citizen {
    std::wstring iFirstName;
    std::wstring iLastName;
};

ChainComparer<Citizen> cmp;
cmp.Chain<std::less>( boost::bind( &Citizen::iLastName, _1 ) );
cmp.Chain<std::less>( boost::bind( &Citizen::iFirstName, _1 ) );

std::vector<Citizen> vec;
std::sort( vec.begin(), vec.end(), cmp );

実装：

template <typename T>
class ChainComparer {
public:

    typedef boost::function<bool(const T&, const T&)> TComparator;
    typedef TComparator EqualComparator;
    typedef TComparator CustomComparator;

    template <template <typename> class TComparer, typename TValueGetter>
    void Chain( const TValueGetter& getter ) {

        iComparers.push_back( std::make_pair( 
            boost::bind( getter, _1 ) == boost::bind( getter, _2 ), 
            boost::bind( TComparer<TValueGetter::result_type>(), boost::bind( getter, _1 ), boost::bind( getter, _2 ) ) 
        ) );
    }

    bool operator()( const T& lhs, const T& rhs ) {
        BOOST_FOREACH( const auto& comparer, iComparers ) {
            if( !comparer.first( lhs, rhs ) ) {
                return comparer.second( lhs, rhs );
            }
        }

        return false;
    }

private:
    std::vector<std::pair<EqualComparator, CustomComparator>> iComparers;
};
于 2012-06-23T06:55:41.727 に答える
2

これを処理する 1 つの従来の方法は、複数のパスでソートし、安定したソートを使用することです。std::sortは一般に安定していないことに注意してください。ただし、ありstd::stable_sortます。

そうは言っても、トライステート (少ない、等しい、大きいを表す) を返すファンクターのラッパーを作成します。

于 2008-11-08T17:27:00.110 に答える
2

std::sort通常、安定ソートは非安定ソートよりも遅いため、安定であるとは限りません...したがって、安定ソートを複数回使用すると、パフォーマンスの問題が発生する可能性があります...

はい、述語を要求するのは本当に残念です。トライステート関数のベクトルを受け入れるファンクターを作成する以外に方法はありません...

于 2008-11-08T18:21:49.937 に答える
1

C ++ 11の可変個引数テンプレートは、より短いオプションを提供します。

    #include <iostream>
    using namespace std;

    struct vec { int x,y,z; };

    struct CmpX {
      bool operator() (const vec& lhs, const vec& rhs) const 
      { return lhs.x < rhs.x; }
    };

    struct CmpY {
      bool operator() (const vec& lhs, const vec& rhs) const 
      { return lhs.y < rhs.y; }
    };

    struct CmpZ {
      bool operator() (const vec& lhs, const vec& rhs) const 
      { return lhs.z < rhs.z; }
    };

    template <typename T>
    bool chained(const T &, const T &) {
      return false;
    }

    template <typename CMP, typename T, typename ...P>
    bool chained(const T &t1, const T &t2, const CMP &c, P...p) {
      if (c(t1,t2)) { return true;          }
      if (c(t2,t1)) { return false;         }
      else          { return chained(t1, t2, p...); }
    }

    int main(int argc, char **argv) {
      vec x = { 1,2,3 }, y = { 2,2,3 }, z = { 1,3,3 };
      cout << chained(x,x,CmpX(),CmpY(),CmpZ()) << endl;
      return 0;
    }
于 2013-02-22T00:09:00.927 に答える
1

連鎖ソリューションは冗長です。また、boost::bind を std::logical_and と組み合わせて使用​​して、並べ替え述語を作成することもできます。詳細については、リンクされた記事を参照してください:どのようにブースト バインド ライブラリを使用して C++ プログラムを改善できるか

于 2008-11-09T17:34:44.743 に答える