c++ - C++ テンプレートを使用してベクトルをソートする方法

Question

C++ テンプレートを使用してベクトルをソートする方法

こんにちはみんな、私の質問を見てくれてありがとう。

このようになる Templates.h ファイルを取得しました。

/* Template Less Than */

template<typename T>
bool lessThan(T a,T b)
{
return a<b;
}

/* Template greater Than */

template<typename T>
bool greaterThan(T a,T b)
{
return a>b;
}

/* Template Equals */

template<typename T>
bool equals(T a,T b)
{
return a==b;
}

それから私はこのクラスを得ました

Map2D

Map2Dについて..

class Map2D
{
protected:
int x;
int y;

public:
Map2D();
Map2D(int,int);
int getX();
int getY();
};

私のmain.cppで、Map2Dのベクトルクラスを取得しました

vector<Map2D> map2d;

だから今、私はそれをX昇順でソートする必要があります..テンプレートファイルを利用してX昇順のベクトルをソートするにはどうすればよいですか.後でDESCENDINGのために別のオーバーロードが必要になると考えてください..

通常、私は使用します

sort(map2d.begin(),map2d.end(),sortByX);

sortByX は、 it () 演算子によるオーバーロードを持つ構造体になります。

しかし、問題は、次よりも小さいテンプレートと大きいテンプレートを取得したためです。それを使用して X を昇順で並べ替え、別の X を Templates.H のテンプレートジェネリック関数を使用して降順で並べ替えるにはどうすればよいでしょうか。

アップデート:

クラス Map2D 演算子 > 、 < および == をオーバーロードする必要があると思います

しかし、私の質問は、lesserThan、greaterThan、equals などの MyTemplates.h 関数を使用してオーバーロードする方法です。

ありがとう。

score 6 · Accepted Answer

クラスまたはより単純なoperator<()オーバーロードのコンパレータを定義します（テンプレートが機能するためには、とにかく行う必要があります）。

まず、テンプレートを修正します。

template<typename T>
bool lessThan(const T& a, const T& b)
{
    return a<b;
}

template<typename T>
bool greaterThan(const T& a, const T& b)
{
    return b<a;
}

template<typename T>
bool equals(const T& a, const T& b)
{
    return !(a<b || b<a);
}

次に、クラスで operator<() を定義します。

class Map2D
{
protected:
    int x;
    int y;

public:
    Map2D();
    Map2D(int,int);
    int getX();
    int getY();

    // this sample sorts on X dominantly, and Y if X is the same
    bool operator <(const Map2D& obj) const
    {
        return (x < obj.x || (x == obj.x && y < obj.y));
    };
}

次に、並べ替えを呼び出します。

std::sort(map2d.begin(), map2d.end());

次のように、lessThan テンプレートを使用して呼び出します。

std::sort(map2d.begin(), map2d.end(), lessThan<Map2D>);

またはあなたのより大きなテンプレート:

std::sort(map2d.begin(), map2d.end(), greaterThan<Map2D>);

score 4 · Accepted Answer

コードにはいくつかの問題があります。

クラスの最後にセミコロンがありません。
比較テンプレートはboolの代わりに返す必要がありTます。

クラス内に比較演算子がありません:

bool operator<(const Map2D &m) const {return /* some code here */ }
bool operator>(const Map2D &m) const {return /* some code here */ }
bool operator==(const Map2D &m) const {return /* some code here */ }

operator<()または、すべての比較にのみ使用するようにテンプレートを修正します(これは一般的な方法です)。

上記を修正すると、次のようにテンプレートを使用するだけです。

sort(map2d.begin(),map2d.end(), lessThan<Map2D>);
sort(map2d.begin(),map2d.end(), greaterThan<Map2D>);

ところで、このような簡単な方法でクラスをソートするためにカスタムテンプレートは必要ありません。すでに STL にあるものを再利用します。

sort(map2d.begin(),map2d.end()); // less
sort(map2d.begin(),map2d.end(), std::greater<Map2D>());

それらは機能ヘッダーにあります。並べ替えにも使用できませんが、C++11 で導入された順序付けられていないコンテナーoperator==()に役立つ場合があります。

編集: Map2D クラスの並べ替えアルゴリズムが修正されている場合 (時間の経過とともに lessThan が変化しない場合)、私の回答に従うことをお勧めします。それ以外の場合は、X で並べ替え、数行後に Y で並べ替えたい場合は、@MikeSeymour の回答の方がニーズに適している可能性があります。

score 4 · Accepted Answer

C++11 では、ラムダ関数を記述してそれを行うことができます。

ブーストを使用して、「ワンステップオンザフライ」ファンクターが必要な場合は、次のようにする必要があります。

bind( less<int>, bind(&Map2D::getX(),_1), bind(&Map2D::getX(),_2) )
// or your lessThan<int> which already exists in C++ as less<int>

それが正確に機能するかどうかはわかりません。(2 番目と 3 番目のバインドはプレースホルダーに適切に変換されますか?) 実行しようとしていることを組み合わせた非常に一般的なファンクターを作成する方が簡単です。つまり、クラスから何かを抽出 (変換) し、それを述語に渡します。

template< typename Trans, typename Pred >
struct Comparator
{
    Comparator( Trans t , Pred p ) : trans( t ), pred ( p )
    {
    }

    template< typename T >
    bool operator()( T const& t1, T const& t2 ) const
    {
         return pred( trans(t1), trans(t2) );
    }
private:
    Trans trans;
    Pred pred;
};


template< typename Trans, typename Pred >
Comparator< Trans, Pred > makeComparator( Trans t, Pred p )
{
     return Comparator( t, p );
}

// then in your code

std::sort( map2d.begin(), map2d.end(), 
    makeComparator( boost::bind( &Map2D::getX(), _1 ), lessThan<int> ) );

動作するはずで、 Comparator を汎用のままにしています。

(ブーストが既にこのようなものを提供しているかどうかはわかりません)。

score 2 · Accepted Answer

C ++ 11を使用している場合は、次のように記述できます。

std::sort(map2d.begin(), map2d.end(), [](const Map2D& a, const Map2D& b) {
    return lessThan(a.getX(), b.getX()); } ); // accending
std::sort(map2d.begin(), map2d.end(), [](const Map2D& a, const Map2D& b) {
    return greaterThan(a.getX(), b.getX()); }); // decending

それ以外の場合は、比較ファンクターを実装する必要があります。

struct compare
{
    bool operator () (const Map2D& a, const Map2D& b)
    {
        return lessThan(a.getX(), b.getX());
    }
};

その後

std::sort(map2d.begin(), map2d.end(), compare());

しかし、xを直接比較できるため、実際には、lessThan、greaterThanを使用するのは適切なスタイルではありません。また、Map2Dの特別な比較が必要な場合は、これらの比較関数をMap2Dオブジェクトに対してのみ作成することをお勧めします。

Upd：コンパレータとして関数ポインタだけを使用することもできます。

bool compare(const Map2D& a, const Map2D& b)
{
    return lessThan(a.getX(), b.getX());
}

その後

std::sort(m.begin(), m.end(), compare);

ただし、パフォーマンスが低下する可能性があります（以下のコメントを参照）。

score 1 · Accepted Answer

あなたは本当にできません。必要な特定のオブジェクトとメンバーの比較を行うには、ファンクター (関数、またはoperator()適切にオーバーロードするクラス) を定義する必要がありますが、関数テンプレートはそれを行いません。次のようなものが必要です：

struct compare_x_less {
    // NOTE: you'll need to declare `get_X() const` for this to work.
    // You should do that anyway.
    bool operator()(Map2D const & a, Map2D const & b) {
        return a.get_X() < b.get_X();
    }
};

// and similarly for `compare_x_greater` and any other comparisons you need

std::sort(map2d.begin(),map2d.end(),compare_x_less());

C++11 では、ラムダ式を使用すると入力の手間を少し省くことができます。

std::sort(map2d.begin(),map2d.end(),[](Map2D const & a, Map2D const & b) {
        return a.get_X() < b.get_X();
    });

score 1 · Accepted Answer

最初に operator をオーバーロードし、テンプレートで使用する必要<があり>ます==。Map2D

class Map2D
{
protected:
   int x;
   int y;
public:
   Map2D();
   Map2D(int,int);
   int getX();
   int getY();
   bool operator<(const Map2D& other)const //less then
   {
      return x < other.x;
   }
   //other operators is same manner
}

完了したら、それを使用するだけです：

sort(map2d.begin(),map2d.end(),lessThan<Map2D>);

score 0 · Accepted Answer

良い方法ですが、最善とは思いません。クラスで演算子 (<) & (!=) をオーバーロードできます。Xのみをソートしたい場合sort(map2d.begin(), map2d.end())。昇順のみに使用します。そしてsort(map2d.rbegin(), map2d.rend())下降のために..そしてそれはあなたの問題を解決します。

OR: 2 つの関数を作成して、x に関連するものと Y に関連するものを比較できます。

int cmpx(const void* A, const void *B){
    Map2D a = *(Map2D *)A;
    Map2D b = *(Map2D *)B;
    if(a.x < b.x) return -1;
    if(a.x == b.x) return 0;
    return 1;
}
// And use
qsort(map2d.begin(), (int)map2d.size(), sizeof(Map2D), cmpx);

Yについてmap2d.rbegin()も同様です。これを降順でソートするか、自分でソートする必要があるかはわかりません。

score 0 · Accepted Answer

sort(map2d.begin(),map2d.end(),lessThan<map2d>);

lessThan は、型の T 値の代わりに返す必要がある prediacte 関数であることに注意してくださいbool

追加の説明:

// usage
    /* Some moments to mention: if you omit third argument, default argument less<T> will be used,
    which is enough for built-in types, also you can use predicates already defined in STL:
    greater<T>, less<T> or you can provide your own predicate */
    sort(map2d.begin(),map2d.end(),lessThan<map2d>);

// header file, where we define predicats which we shall provide as argument to algorithm sort

// predicate expected by function sort has to obey the following rules:
// 1. return bool 2. accept 2 parameters

/*2 variants of predicat*/

// 1) operator< is overloaded for class T, so we can use it to compare instances of that class
template<typename T>
bool lessThan(T a,T b)
{
return a < b;
}

/* 2) operator< not overloaded, when we have to get values of class members by which we are going to compare them
this could be done in various ways, for ex. by means of getters();*/

template<typename T>
bool lessThan(T a,T b)
{
return a.getValueOfMember() < b.getValueOfMember();
}

c++ - C++ テンプレートを使用してベクトルをソートする方法

8 に答える 8

Related

Reference