C++メモ

競技プログラミング用の備忘録なので，

```C++
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
```

という前提です．悪しからず．

## 整数・実数の範囲に関する定数

面倒がらずに使おう．

```C++
  int i1 = INT_MAX;
  int i2 = INT_MIN;
  long long l1 = LLONG_MAX;
  long long l2 = LLONG_MIN;
  double d1 = DBL_MAX;
  double d2 = DBL_MIN;

  // 自分の普段の環境では:
  assert(i1 == (((1 << 30) - 1) << 1) + 1);
  assert(l1 == (2 * ((1LL << 62) - 1) + 1));
  assert(i2 == -i1 - 1);
  assert(l2 == -l1 - 1);
  assert(1e308 < d1);
  assert(0 < d2 && d2 < 3e-308);
```

他の定数たち: [整数](http://www.cplusplus.com/reference/climits/), [実数](http://www.cplusplus.com/reference/cfloat/)

## exception

文法をすぐ忘れちゃう...

```C++
struct MyException : exception {};

void func1(int x) {
  if (x == 1) throw MyException();
}

int main() {
  int i;
  try {
    for (i = 0; i < 2; i++) func1(i);
  }catch(const MyException& e) {
  }
  assert(i == 1);
}
```

## setのerase

イタレータ指定の erase() は，消去した次の要素を返す．なるほど．

```C++
  set<int> s({5,6,7,8,9});
  auto it = s.erase(s.find(6), s.find(8));
  assert(it == s.find(8));
  it = s.erase(s.find(9));
  assert(it == s.end());
```

したがって，要素を消しながらループさせたいときには，次のように書けば良い．

```C++
  set<int> s({1,2,3,4,5});
  for (auto it = s.begin(); it != s.end(); ) {
    if (*it % 2 == 0) it = s.erase(it);
    else              it++;
  }
  assert(s == set<int>({1,3,5}));
```

range-based for だと，メモリエラーになる:

```C++
  // これは不可
  set<int> s({1,2,3,4,5});
  for (int t : s) {
    if (t % 2 == 0) s.erase(t);
  }
  assert(s == set<int>({1,3,5}));
```

## lower_bound, upper_bound

* lower_bound(b, e, x) は，$\min \\{ t \in [b,e) \mid t \not< x \\}$ へのイタレータ．
  つまり，全順序だったら，$\min \\{ t \in [b,e) \mid x \leq t \\}$．
* upper_bound(b, e, x) は，$\min \\{ t \in [b,e) \mid x < t \\}$     へのイタレータ．

いずれも，条件を満たすものが無ければ e が返る．s はソート済みである必要がある．

```C++
  //             0  1  2  3  4  5
  vector<int> v({2, 4, 6, 6, 6, 8});
  auto b = v.begin();
  auto e = v.end();

  // x が v の中になければ，両者は同じ．つまり，v の中で x より大きいものの下限．
  assert(lower_bound(b, e, 5) == b + 2);
  assert(upper_bound(b, e, 5) == b + 2);

  // x が v の中にあるときには，
  // lower_bound は，それらの一番下．
  assert(lower_bound(b, e, 6) == b + 2);
  // upper_bound は，それらの次
  assert(upper_bound(b, e, 6) == b + 5);

  // そもそも x が v の上界になっているときには，e 
  assert(lower_bound(b, e, 9) == e);
  assert(upper_bound(b, e, 9) == e);
```

リファレンス: [lower_bound](http://www.cplusplus.com/reference/algorithm/lower_bound/), [upper_bound](http://www.cplusplus.com/reference/algorithm/upper_bound/)

## set の逆順イタレータ

たとえば，`set<int>` の中にある `x` 以上の値を小さい順に印字するとすれば，自然に次のようになる．

```C++
  for (auto it = s.lower_bound(x); it != s.end(); it++) cout << *it << endl;
```

一方で，`x` 以下の値を大きい順に印字したい場合には，次のようにすればできる．

```C++
  auto it0 = s.upper_bound(x);
  auto revit = reverse_iterator<decltype(it0)>(it0);
  for (; revit != s.rend(); revit++) cout << *revit << endl;
```

3行目にあるように，逆順のイタレータを作って，`s.rend()` まで読んでいく．逆順イタレータは，`std::reverse_iterator<T>` というクラスのオブジェクトを作れば良い．`T` は省略できないので，`decltype(it0)` と書いている．コンストラクタには，逆順にするイタレータ (`it0`) を渡すのだが，このコンストラクタは，イタレータの位置を一つ左にずらす．`s.begin()` と `s.rend()` の位置や `s.end()` と `s.rbegin()` の位置が一つずれていることと対応しているのだと思う．したがって，`s` が `x` を含む場合にも，その位置から始められるように，`it0` は，`lower_bound` ではなく，`upper_bound` を使っておく必要がある．

なお，lower_bound や upper_bound は，set の場合，メンバ関数になっている．(std::lower_bound などとは引数が異なる．意味は同じ．)

リファレンス: [set](http://www.cplusplus.com/reference/set/set/), [reverse_iterator](http://www.cplusplus.com/reference/iterator/reverse_iterator/)

## closure

* ラムダ式に`[&]` をつけることによってclosureを作れる．
* セミコロンに注意

```C++
  int N = 6;
  auto foo = [&](int x) {
    return N + x;
  };
  assert(foo(5) == 11);
```

* 再帰するときには[指摘](http://koturn.hatenablog.com/entry/2018/06/10/060000)に従って，次のように書くと良いようだ．良く理解していない．
* まず，以下のように fix 関数を定義する．(FixPoint クラスも定義されているが，これは fix の中で使われている)

```C++
template<typename F>
class FixPoint : private F {
public:
  explicit constexpr FixPoint(F&& f) noexcept : F(forward<F>(f)) {}

  template<typename... Args>
  constexpr decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, forward<Args>(args)...);
  }
};

template<typename F>
static inline constexpr decltype(auto) fix(F&& f) noexcept {
  return FixPoint<F>{forward<F>(f)};
}
```

* fix 関数を使って，次のように書く．

```C++
  auto func = fix([&](auto recF, type1 var1, ...) -> typeRet {
            // 関数定義を書く．この中では，再帰呼び出しは func ではなく
            // recF を使って呼び出す．
            // 返却値型は省略できない．
        });
  func(exp1, ...);
```

* 例:

```C++
  int t0 = 5;
  auto func1 = fix([&](auto recF, int n) -> int {
          if (n == 0) return t0;
          else        return n + recF(n-1);
        });
  assert(func1(4) == 15);
```

## priority queue で，比較関数にラムダ式を使う

(Using a lambda function for the comparison function (comparator) in a priority queue)

比較関数を (closureを使っても良くて) lambda で書いて comp という変数に入れてあるとして，priority_queue の第3引数 (比較の定義) のところに decltype(comp) と書き，さらに，constructor の引数としても comp を渡す．ネタ元は [stackoverflow](https://stackoverflow.com/questions/5807735/c-priority-queue-with-lambda-comparator-error).

```C++
vector<int> x(10); 
...
auto comp = [&](int i, int j) { return x.at(i) < x.at(j); };
// pop すると，ベクトル x の値が最も大きい添字を返すような優先度付きキュー
priority_queue<int, vector<int>, decltype(comp)> pque(comp);
// もちろん，この後で 勝手に x の値を変更して良いわけではない．
```