降順にsortする

stlのalgorithm::sortに関数を渡して、ソートの挙動を変更することができます。例えば、vector のソートはデフォルトでは昇順ですが、

int main(void)
{
  std::vector <int> vi;
  vi.push_back(1);
  vi.push_back(10);
  vi.push_back(3);
  sort(vi.begin(), vi.end());

  for (int i=0; i" ";       // 1 3 10
  std::cout << std::endl;

  return 0;
}

以下のようにすると降順に並べ替えられます。

bool desc (int a, int b)
{
  return a > b;
}

int main(void)
{
  std::vector <int> vi;
  vi.push_back(1);
  vi.push_back(10);
  vi.push_back(3);
  sort(vi.begin(), vi.end(), desc);    // desc() を渡す
  for (int i=0; i// 10 3 1
    std::cout << vi[i] << std::endl;

  return 0;
}

sort()の3つ目の引数に、2つの要素を比較してbool値を返す関数を渡すと、要素の比較の際にその関数を使ってソートしてくれます。このようなboolを返す関数をpredicate function(叙述関数)と呼ぶそうです。ソートの場合、叙述関数の1つ目の引数(int a)が前側の要素、2つ目の引数(int b)が後ろ側の要素です。ちなみに今回のようなintの昇順、降順の変更くらいだと、よく使うユーティリティの関数として、greater()とかless_equal()などがすでに用意されています。

sort(vi.begin(), vi.end(), greater<int>())

functional - C++ Reference

また余談ですが、今回のケースだとリバースイテレータを渡すのも手です。

sort(vi.rbegin(), vi.rend())

任意のオブジェクトのソート

上記の機能を利用すると、任意のオブジェクトをsort()でソートすることができます。例えば、座標を表す構造体pointを、x座標値を降順でソートして、xがtieならy座標値を昇順でソートするという場合、次のようにできます。

typedef struct point
{
  int x;
  int y;
};

bool cmp(point a, point b)
{
  if (a.x == b.x)
    return a.y < b.y;
  else
    return a.x > b.x;
}

int main(void)
{
  std::vector  pointVec;

  // ...
  
  std::sort (pointVec.begin(), pointVec.end(), cmp);

  // ...

  return 0;
}

predicate function以外でのソート

ソートの挙動を変更する方法は、predicate functionを渡す方法だけではありません。例えば、"<" operatorをオーバーロードしたり、関数オブジェクトを使ったりもできます。

typedef struct point
{
  int x;
  int y;

  bool operator<(const struct s & a) const {
    if (x == a.x)
  	return y < a.y;
    else
 	return x < a.x;
  }
};

int main(void)
{
  // ...

  sort(pointVec.begin(), pointVec.end());   // cmpは渡さない

  // ...
}

クラス内でのpredicate

例えば、クラス内でpredicate functionを定義し、それをメンバ関数から呼び出して使おうとしても、コンパイル時にエラーが出てうまくいきません。（エラーメッセージもstlらしくとても長いです。）

class sample {
public:
  struct point {
    int x;
    int y;
  };

  static bool cmp (struct s a, struct s b) {
    if (a.x == b.x)
      return a.y < b.y;
    else
      return a.x < b.x;
  }

  int func(void) {
    std::vector  vec;

    // ...

    std::sort(vec.begin(), vec.end(), cmp);  // compilation error
    
    // ...

    return 0;
  }
};

int main(void) {
  sample *smp = new sample();
  smp->func();
  return 0;
}

この現象は、cmp()がsampleクラスのメンバ関数なので、それを呼ぶ際にthisポインタが必要になることが原因で起こっています。よって、以下のようにする必要があります．

1. static 関数にする。staticだとthisポインタが必要ない。
2. "<" operator や関数オブジェクトを使う方法に変更する。
3. クラスの外で struct point と cmp() を宣言する。

参考

C++ std::sort with predicate function in Class - Stack Overflow