ラムダ式でstd::sort

はじめに

C++初心者です。いつも使おうとして忘れてしまうのでラムダ式を使ったソート方法を書きこのしておきます。間違いがありましたらコメントを残していただけると幸いです。

std::sort

sortは引数に2つイテレータ¹を取り、イテレータで指定された範囲をソートする標準関数です。

例

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
  vector<int> arr = {2, 4, 1, 3, 5};
  sort(arr.begin(), arr.end());
  for_each(arr.begin(), arr.end(), [](int const& ele){
    cout << ele << endl;
  });
}

std::sortはイントロソート²を用いてコンテナをソートします。計算量はO(NlogN)になります。
std::sortはデフォルトで要素を昇順に並べ替えますが、比較関数を自分で用意することも可能です。

ラムダ式

C++11から追加された関数オブジェクトをその場で定義するための機能です³。次に簡単なラムダ式の例を示します。

lambda

// 引数を2つ取りその和を返すラムダ式
auto func = [](int p, int q) -> int { return p + q; }
cout << func(2,3) << endl; // 5

JavaScriptの関数リテラルのように書けますね。
C++14からは引数を推論させることもできます。

引数の推論

auto plus = [](auto a, auto b)->int { return a + b; };

ラムダ式は関数オブジェクトを引数に取る関数に渡すことができます。最初の例ではfor_eachにラムダ式を渡してコンテナを標準出力しています。

for_each

for_each(arr.begin(), arr.end(), [](int const& ele){
  cout << ele << endl;
});

同様にstd:sortにラムダ式を渡し、比較方法を指定することが可能です。

ラムダ式を用いたsortの例

###コンテナを降順に並び替える
sortに要素を比較してboolを返すラムダ式を渡して降順に並び替えます。

#include <iostream>
#include <algorithm>
#include <array>
#include <numeric>
using namespace std;

int main() {
  array<int, 5> arr;
  iota(arr.begin(), arr.end(), 1);
  sort(arr.begin(), arr.end(), [](auto const& lhs, auto const& rhs) {
    return lhs > rhs; // 左の方が大きい...というイメージ。
  });
  for_each(arr.begin(), arr.end(), [](auto const& ele){
    cout << ele << endl; // 5,4,3,2,1
  });
}

比較演算子を持たない構造体のソート

比較演算子を持たない場合のソートの例です。

// MyStructのfirstを基準に昇順に並べる。
// もしfirstが等しい場合secondを降順に並べる。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct MyStruct {
  int first, second;
};

int main() {
  vector<MyStruct> vec{{1, 2}, {1, 3}, {3, 1}, {3, 2}};
  sort(vec.begin(), vec.end(), [](auto const& lhs, auto const& rhs) {
    if (lhs.first != rhs.first) return lhs.first < rhs.first;
    else if (lhs.second != rhs.second) return lhs.second > rhs.second;
    return true;
  });
  for_each(vec.begin(), vec.end(), [](auto const& lhs){
    cout << lhs.first << " " << lhs.second << endl;
  });
}
// 出力
// 1 3
// 1 2
// 3 2
// 3 1

まとめ

• 関数オブジェクトはラムダ式で渡せる。
• ラムダ式の引数はC++14からautoで推論できる。

参考文献

cpprefjp
cppreference.com
wandbox

1. 厳密にはRandomAccessIteratorである必要があります。そのためBidirectionalIteratorを持つsetなどは使えません。 ↩

2. https://ja.wikipedia.org/wiki/イントロソート ↩

3. https://cpprefjp.github.io/lang/cpp11/lambda_expressions.html ↩