Algorithmを使っていますか？【シーケンスを変更しない操作編】

# 最初に
　この記事は[algorithm](https://cpprefjp.github.io/reference/algorithm.html)にある、全ての関数の使い方・簡単な例・計算量などを書いています。一応C++er初心者向けに書いています。出来る限り[リファレンス](https://cpprefjp.github.io/reference.html)より分かり易く書いているつもりですが、「そんなことより、厳選されて分かり易いのはどれ！」という方には[この記事](https://qiita.com/e869120/items/518297c6816adb67f9a5 "簡潔にまとめられて、非常にお勧めですよ！")をお勧めします[^1]。

　C++上級者はリファレンスで十分かと思いますが、初心者～中級者はこの記事を見ても損はさせ無いように作成しています。
　リファレンスは分かり易いですが、一部に分かりにくいのも混じっていたり、一部に若干の情報不足を感じます。なので、「リファレンスを読まない人」の為にもこの記事を作成するに至りました。

　この記事は[ラムダ式](https://gintenlabo.hatenablog.com/entry/20130516/1368711542 "「ラムダ式って何？」という人はこの記事を読んでみて下さい。")[^2]・[イテレーター](https://qiita.com/yumetodo/items/245e94a0e85db9bf5cbb "「イテレーターって何？」という人はこの記事を読んでみて下さい。")[^13]を使っているのでそこだけは注意してください。最後に[この動画](https://youtu.be/bFSnXNIsK4A "Algorithmを英語で解説している動画ですが、図もあってかなり分かり易いと思います。")も見てみて下さい。英語ですが図が書かれていて分かり易いと思います。

[^1]: といっても、「使えない」と「使わない」は違うので、少なくとも大体の関数の使い方を知っておくことをお勧めします。
[^2]: ラムダ式はかなり有能なので、知らない人は各々調べてみて下さい。知らなくてもとりあえず、関数をある関数の引数に持ってこれると思ってください。勿論、それだけじゃないですけど、面白いですよ。 
[^13]: イテレーターの存在理由の一つに、「コンテナクラス×関数の数」から「コンテナクラス+関数の数」に減らせるからというのがあります。

# 補足説明
　この記事は[リファレンス](https://cpprefjp.github.io/reference/algorithm.html)にそって説明していきます[^3]。計算量は[O記法](https://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c)で載せています[^4]。なお、説明はリファレンスをベースにして、補足を入れています。
　あと、<font color="Red">C++11・14・17以降</font>で動く関数もいくつか存在するので注意してください。

[^3]: 暇なら試しに読んでみて下さい、結構面白いですよ。
[^4]: 自分はO記法の理解がふんわりしているので、具体的な時間の方が分かり（ゲフンゲフン...） 

# 目次
| 章 | タイトル | 対応バージョン |
| :-: | :-: | :-: |
|第１章| [シーケンスを変更しない操作](#1シーケンスを変更しない操作) | --- |
|1.| [std::all_of](#stdall_of-全ての要素が一致するぜ "全ての要素が一致するぜ") | C++11以降 |
|1.| [std::any_of](#stdany_of-どれかの要素が一致するぜ "どれかの要素が一致するぜ") | C++11以降 |
|1.| [std::none_of](#stdnone_of-全ての要素が一致しないぜ "全ての要素が一致しないぜ") | C++11以降|
|1.| [std::for_each](#stdfor_each-全ての要素を処理するぜ "全ての要素を処理するぜ") |
|1.| [std::for_each_n](#stdfor_each_n-先頭からn個の数だけ処理するぜ "先頭からN個の数だけ処理するぜ") | C++17以降 |
|1.| [std::find](#stdfind-条件を満たす最初の単純な型の要素を探すぜ "条件を満たす最初の単純な型の要素を探すぜ") |
|1.| [std::find_if](#stdfind_if-条件を満たす最初の要素を探すぜ "条件を満たす最初の要素を探すぜ") |
|1.| [std::find_if_not](#stdfind_if_not-条件を満たさない最初の要素を探すぜ "条件を満たさない最初の要素を探すぜ") | C++11以降 |
|1.| [std::find_end](#stdfind_end-２つ目の配列に合う最後の要素を探すぜ "２つ目の配列に合う最後の要素を探すぜ") |
|1.| [std::find_first_of](#stdfind_first_of-２つ目の配列に合う最初の要素を探すぜ "２つ目の配列に合う最初の要素を探すぜ") |
|1.| [std::adjacent_find](#stdadjacent_find-隣同士が一致する最初の要素を探すぜ "隣同士が一致する最初の要素を探すぜ") |
|1.| [std::count](#stdcount-条件を満たす単純な型の要素を数えるぜ "条件を満たす単純な型の要素を数えるぜ") |
|1.| [std::count_if](#stdcount_if-条件を満たす要素を数えるぜ "条件を満たす要素を数えるぜ") |
|1.| [std::mismatch](#stdmismatch-２つ目の配列と比べて要素が一致しない最初の要素を探すぜ "２つ目の配列と比べて、要素が一致しない最初の要素を探すぜ") |
|1.| [std::equal](#stdequal-２つ目の配列と比べて要素が全て一致するかを調べるぜ "２つ目の配列と比べて、要素が全て一致するかを調べるぜ") |
|1.| [std::search](#stdsearch-２つ目の配列全てに合う最初の要素を探すぜ "２つ目の配列全てに合う最初の要素を探すぜ") |
|1.| [std::search_n](#stdsearch_n-条件を満たすn個連続した最初の要素を探すぜ "条件を満たすN個連続した最初の要素を探すぜ") |
|第２章| シーケンスを変更する操作：前半（近日中に公開します）| --- |
|第３章| シーケンスを変更する操作：後半（近日中に公開します）| --- |
|第４章| ソートや、それに関連した操作（近日中に公開します）| --- |
※目次を作ること自体、先ほどの[記事](https://qiita.com/e869120/items/518297c6816adb67f9a5)から参考にしました。ありがとうございます！

# 1.シーケンスを変更しない操作
　早速「シーケンスを変更しない」ってなに？ ってなった人に言うと...「俺様はこの関数内で自分から配列を変更しないぜ」ということです。

## ・std::all_of (全ての要素が一致するぜ)

### 使い方
　この関数はとてもシンプルで、全ての要素が条件に一致するかどうかを確かめます。それだけの機能です。つまり、全ての要素が条件に一致するならtrue、一つでも要素が条件に一致しないならfalseになります。対応バージョンはC++11以降です。

[std::all_of：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/all_of.html)

### 引数
1.配列のbegin()
2.配列のend()
3.条件関数（ここではラムダ式を使っていますが、勿論普通の関数でもOKです。）
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　boolが戻ります。条件に一致しない要素を発見したらその時点でfalseを返します。なお、<font color="Red">**空の配列はtrueが返されます**</font>。

### 計算量
　計算時間は最大で「O(n)」になります。つまり、最大で配列のサイズ分を試行します。

### 簡単な例
```c++
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 3, 1, 4 };

  std::cout << std::boolalpha; // bool型を数字出力から、文字列出力に変更

  // 全ての要素が 5 より小さいか
  bool result1 = std::all_of(v.begin(), v.end(), [](int x) { return x < 5; });
  std::cout << result1 << std::endl;

  // 全ての要素が 1 であるか
  bool result2 = std::all_of(v.begin(), v.end(), [](int x) { return x == 1; });
  std::cout << result2 << std::endl;
}
```

### 出力
```
true
false
```

[目次へ戻る](#目次)

## ・std::any_of (どれかの要素が一致するぜ)

### 使い方
　この関数はとてもシンプルで、いずれかの要素が条件に一致するかどうかを確かめます。それだけの機能です。つまり、一つでも要素が条件に一致するならtrue、全ての要素が条件に一致しないならfalseになります。対応バージョンはC++11以降です。

[std::any_of：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/any_of.html)

### 引数
1.配列のbegin()
2.配列のend()
3.条件関数（ここではラムダ式を使っていますが、勿論普通の関数でもOKです。）
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　boolが戻ります。条件に一致する要素を発見したらその時点でtrueを返します。<font color="Red">**空の配列はfalseが返されます**</font>。

### 計算量
　計算時間は最大で「O(n)」になります。つまり、最大で配列のサイズ分を試行します。

### 簡単な例
```c++
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 3, 1, 4 };

  std::cout << std::boolalpha; // bool型を数字出力から、文字列出力に変更

  // 5 以上の要素が存在するかどうか
  bool result1 = std::any_of(v.begin(), v.end(), [](int x) { return x >= 5; });
  std::cout << result1 << std::endl;

  // 1 の要素が存在するかどうか
  bool result2 = std::any_of(v.begin(), v.end(), [](int x) { return x == 1; });
  std::cout << result2 << std::endl;
}
```

### 出力
```
false
true
```

[目次へ戻る](#目次)

## ・std::none_of (全ての要素が一致しないぜ)

### 使い方
　この関数はとてもシンプルで、全ての要素が条件に一致しないかどうかを確かめます。それだけの機能です。つまり、全ての要素が条件に一致しないならtrue、一つでも要素が条件に一致するならfalseになります。対応バージョンはC++11以降です。

[std::none_of：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/none_of.html)

### 引数
1.配列のbegin()
2.配列のend()
3.条件関数（ここではラムダ式を使っていますが、勿論普通の関数でもOKです。）
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　boolが戻ります。条件に一致する要素を発見したらその時点でfalseを返します。<font color="Red">**空の配列はtrueが返されます**</font>。

### 計算量
　計算時間は最大で「O(n)」になります。つまり、最大で配列のサイズ分を試行します。

### 簡単な例
```c++

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 3, 1, 4 };

  std::cout << std::boolalpha; // bool型を数字出力から、文字列出力に変更

   // 全ての要素が 3 以上であるか
  bool result1 = std::none_of(v.begin(), v.end(), [](int x) { return x < 3; });
  std::cout << result1 << std::endl;

  // 全ての要素が 0 以外であるか
  bool result2 = std::none_of(v.begin(), v.end(), [](int x) { return x == 0; });
  std::cout << result2 << std::endl;
}
```

### 出力
```
false
true
```
[目次へ戻る](#目次)

## ・std::for_each (全ての要素を処理するぜ)

### 使い方
　この関数はとてもシンプルで、全ての要素に引数の関数オブジェクトを適用します。それだけの機能です。

[std::for_each：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/for_each.html)

### 引数
1.配列のbegin()
2.配列のend()
3.処理関数（ここではラムダ式を使っていますが、勿論普通の関数でもOKです。）
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　引数と同じ関数オブジェクトが戻ります[^5]。

[^5]: 素直に疑問で、戻り値の必要性を感じないんですが(笑)、１回も使ったことはないですし。

### 計算量
　計算時間は「O(n)」になります。つまり、配列のサイズ分を試行します。じゃなかったら困りますが(笑)

### 簡単な例
```c++

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 3, 1, 4 };

  // vの全ての要素にラムダ式を適用する
  auto func = std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << std::endl; });

  func(10); // 後で、引数と同じ関数オブジェクトを使うことはるのだろうか？

  std::cout << "----" << std::endl;

  // 要素の内容を書き換えても構わないし、呼び出し順序に依存した処理を書いても構わない
  int n = 0;
  std::for_each(v.begin(), v.end(), [n](int& x) { x += n++; });
  std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << std::endl; });
}
```

### 出力
```
3
1
4
10
----
3
2
6
```

[目次へ戻る](#目次)

## ・std::for_each_n (先頭からN個の数だけ処理するぜ)

### 使い方
　この関数はとてもシンプルで、先頭からN個分だけ引数の関数オブジェクトを適用します。それだけの機能です。対応バージョンはC++17以降です。
　あと、全てに言えることなんですが、「begin() + 1」ってしてやれば、一様、開始位置をずらせたりできます。使うかどうかは分かりませんが。

[std::for_each_n：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/for_each_n.html)

### 引数
1.配列のbegin()
2.要素を進める回数（勿論ですが、配列のサイズを超えた値を入れないようにしてください。）
3.処理関数（ここではラムダ式を使っていますが、勿論普通の関数でもOKです。）
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)」を使う必要があります。

### 戻り値
　場所を示すイテレーターが返ります。
　「<font color="Red">終えた位置 + 1</font>」の位置のイテレーターが返ります。配列が空の場合は**end()**が返ります。

### 計算量
　計算時間は最大で「O(n)」になります。つまり、最大でも配列のサイズ分を試行します。といっても「進める回数」で変わるので、あくまでも最大計算量です。

### 簡単な例
```c++

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 3, 1, 4 };

  // コンテナvの先頭3要素に、ラムダ式で記述した関数オブジェクトを適用する。
  // このラムダ式は要素の変更を行う
  auto itr = std::for_each_n(v.begin(), 3, [](int& num) { num *= 2; });

  // std::cout << *itr << std::endl; // このイテレーターはendなので実行するとお亡くなりなります。
  std::cout << *(--itr) << std::endl; // 終了した位置のイテレーターにするなら、一つ戻る必要があります。（括弧はいらないんですが、流石に見にくいので...。）

  std::cout << "----" << std::endl;

  // コンテナvの先頭3要素に、ラムダ式で記述した関数オブジェクトを適用する
  std::for_each_n(v.begin(), 3, [](int x) { std::cout << x << std::endl; });
}
```

### 出力
```
8
----
6
2
8
```

[目次へ戻る](#目次)

## ・std::find (条件を満たす最初の単純な型の要素を探すぜ)

### 使い方
　この関数はとてもシンプルで、全ての要素から条件に一致する最初の要素を発見します。それだけの機能です。
　ここでいう単純な型とは、intとかfloatとかになります。「単純な型でも少し複雑な事をしたい」や「構造体を探したい」とかは、下記のstd::find_ifになります。といっても、別の手段でやろうと思えばいけますが...[^6]。正直、それなら後述の「std::find_ifを使え」と思います。

[std::find：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/find.html)

### 引数
1.配列のbegin()
2.配列のend()
3.条件要素
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　場所を示すイテレーターが返ります。
　条件に一致する要素を発見次第、その位置のイテレータを返します。発見出来なかった場合・配列が空の場合は、**end()**を返します。

### 計算量
　最大計算時間は「O(n)」になります。つまり、最大で配列のサイズ分を試行します。

### 簡単な例
```c++

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 3, 1, 4, 1 };

 // １である最初の要素を検索する
 auto result = std::find(v.begin(), v.end(), 1);

  if (result == v.end()) {
    std::cout << "not found" << std::endl;
  } else {
    INT64 index{ std::distance(v.begin(), result) }; // イテレーター間の距離を求める関数（この場合は発見した添え値を求める）
    std::cout << "found: index==" << index << ", num==" << *result << std::endl;
  }
}
```

### 出力
```
found: index==1, num==1
```

[目次へ戻る](#目次)

## ・std::find_if (条件を満たす最初の要素を探すぜ)

### 使い方
　この関数はとてもシンプルで、全ての要素から条件に一致する最初の要素を発見します。それだけの機能です。こっちの方がよく使います。

[std::find_if：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/find_if.html)

### 引数
1.配列のbegin()
2.配列のend()
3.条件関数
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　場所を示すイテレーターが返ります。
　条件に一致する要素を発見次第、その位置のイテレーターを返します。発見出来なかった場合・配列が空の場合は、**end()**を返します。

### 計算量
　最大計算時間は「O(n)」になります。つまり、最大で配列のサイズ分を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 3, 1, 4, 1 };

  // 3ではない最初の要素を検索する
  auto result = std::find_if(v.begin(), v.end(), [](int x) { return x != 3; });

  if (result == v.end()) {
    std::cout << "not found" << std::endl;
  } else {
    INT64 index{ std::distance(v.begin(), result) }; // イテレーター間の距離を求める関数（この場合は発見した添え値を求める）
    std::cout << "found: index==" << index << ", num==" << *result << std::endl;
  }
}
```

### 出力
```
found: index==1, num==1
```

[目次へ戻る](#目次)

## ・std::find_if_not (条件を満たさない最初の要素を探すぜ)

### 使い方
　この関数はとてもシンプルで、全ての要素から条件に一致しない最初の要素を発見します。それだけの機能です。find_ifの逆になる関数になります。対応バージョンはC++11以降です。

[std::find_if_not：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/find_if_not.html)

### 引数
1.配列のbegin()
2.配列のend()
3.条件関数
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　場所を示すイテレーターが返ります。
　条件に一致しない要素を発見次第、その位置のイテレーターを返します。発見出来なかった場合・配列が空の場合は、**end()**を返します。

### 計算量
　最大計算時間は「O(n)」になります。つまり、最大で配列のサイズ分を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 3, 1, 4, 1 };

  // 3ではない最初の要素を検索する
  auto result = std::find_if_not(v.begin(), v.end(), [](int x) { return x == 3; });

  if (result == v.end()) {
    std::cout << "not found" << std::endl;
  } else {
    INT64 index{ std::distance(v.begin(), result) }; // イテレーター間の距離を求める関数（この場合は発見した添え値を求める）
    std::cout << "found: index==" << index << ", num==" << *result << std::endl;
  }
}
```

### 出力
```
found: index==1, num==1
```

[目次へ戻る](#目次)

## ・std::find_end (２つ目の配列に合う最後の要素を探すぜ)

### 使い方
　ややこしいですが、「対象配列」の中から「検索用配列」の要素「<font color="Red">**全て**</font>」に合う、「対象配列」の「**最後**の要素」を検索します。「全ての配列から条件を満たす最後の要素を探す」ではないので注意して下さい。

[std::find_end：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/find_end.html)

### 引数
1.対象配列のbegin()
2.対象配列のend()
3.検索用配列のbegin()
4.検索用配列のend()
5.比較関数[^7] ※この引数を使うことはあまりないです。
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

[^7]: 単純に比較できない場合・比較基準を変更したい場合は書かないといけません。書かない場合は内部でstd::equal_toを使っています。

### 戻り値
　場所を示すイテレーターが返ります。
　「検索用配列」に一致する「対象配列」の、「最後の要素」の「要素中の最初」のイテレータを返します[^8]。発見出来なかった場合・両配列が一つでも空の場合は、「対象配列」の**end()**を返します。

[^8]: わけがわからないよ...。

![Find End.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/b87ebc80-32fd-2a3e-bff1-a892493ac356.png)
※[画像元](https://youtu.be/bFSnXNIsK4A "某英語解説動画です。")

### 計算量
　最大計算時間は「対象配列：O(n)」*「検索用配列：O(n)」になります。つまり、最大で「対象配列のサイズ分」×「検索用配列のサイズ分」を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>

int main() {
  std::vector<int> v{ 1,2,1,2,3 };
  std::vector<int> ls{ 1,2 };

  // 1,2 と連続している最後のシーケンスを探す
  auto it = std::find_end(v.begin(), v.end(), ls.begin(), ls.end());

  // 同じ意味になります
  it = std::find_end(v.begin(), v.end(), ls.begin(), ls.end(), [](int left, int right) { return left == right; });

  // v[2] の位置を指すイテレータが見つかる。
  // v[0] の位置を指すイテレータではない。
  if (it == v.end()) {
    std::cout << "not found" << std::endl;
  } else {
    INT64 index{ std::distance(v.begin(), it) }; // イテレーター間の距離を求める関数（この場合は発見した添え値を求める）
    std::cout << "found: index==" << index << ", num==" << *it << std::endl;
  }
}
```

### 出力
```
found: index==2, num==1
```

[目次へ戻る](#目次)

## ・std::find_first_of (２つ目の配列に合う最初の要素を探すぜ)

### 使い方
　これは、上記のstd::find_endのほぼ逆です。「対象配列」の中から「検索用配列」の要素の「<font color="Red">**一部**</font>」 に合う、「対象配列」の「**最初**の要素」を検索します。

[std::find_first_of：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/find_first_of.html)

### 引数
1.対象配列のbegin()
2.対象配列のend()
3.検索用配列のbegin()
4.検索用配列のend()
5.比較関数[^7] ※この引数を使うことはあまりないです。
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　場所を示すイテレーターが返ります。
　「検索用配列」の一部に一致する「対象配列」の、「最初の要素」のイテレータを返します。発見出来なかった場合・両配列が一つでも空の場合は、「対象配列」の**end()**を返します。


![Find First Of.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/a61d4c94-9e9f-4118-e2f5-33b17923256d.png)
※[画像元](https://youtu.be/bFSnXNIsK4A "某英語解説動画です。")

### 計算量
　最大計算時間は「対象配列：O(n)」*「検索用配列：O(n)」になります。つまり、最大で「対象配列のサイズ分」×「検索用配列のサイズ分」を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 1,3,7,4,2 };
  std::vector<int> ls{ 2,4,6,8 };

  // 2,4,6,8 のどれかと一致する最初の要素を返す
  auto it = std::find_first_of(v.begin(), v.end(), ls.begin(), ls.end());

  // 同じ意味になります。
  it = std::find_first_of(v.begin(), v.end(), ls.begin(), ls.end(), [](int left, int right) { return left == right; });

  if (it == v.end()) {
    std::cout << "not found" << std::endl;
  } else {
    std::cout << "found: index==" << std::distance(v.begin(), it) << ", value==" << *it << std::endl;
  }
}
```

### 出力
```
found: index==3, value==4
```

[目次へ戻る](#目次)

## ・std::adjacent_find (隣同士が一致する最初の要素を探すぜ)

### 使い方
　この関数はとてもシンプルで、配列中の隣接する要素同士が一致する最初の要素を検索します。それだけの機能です。

[std::adjacent_find：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/adjacent_find.html)

### 引数
1.配列のbegin()
2.配列のend()
3.比較関数[^7] ※この引数を使うことはあまりないです。
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　場所を示すイテレーターが返ります。
　隣接する要素同士が一致した時点で、その位置のイテレーターを返します。発見出来なかった場合・配列が空の場合は**end()**を返します。

### 計算量
　最大計算時間は：O(n)になります。つまり、最大で配列のサイズ分を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>

int main() {
  std::vector<int> v = { 1,4,3,3,1,2,2 };

  // 同じ値が連続している最初の要素を検索する
  auto it = std::adjacent_find(v.begin(), v.end());

  // 同じ意味になります。
  it = std::adjacent_find(v.begin(), v.end(), [](int left, int right) { return left == right; });

  if (it == v.end()) {
    std::cout << "not found" << std::endl;
  }
  else {
    std::cout << "found: index==" << std::distance(v.begin(), it) << ", num==" << *it << ", next num==" << *(it + 1) << std::endl;
    std::cout << std::boolalpha << "*it == *(it+1): " << (*it == *(it + 1)) << std::endl;
  }
}
```

### 出力
```
found: index==2, num==3, next num==3
*it == *(it+1): true
```

[目次へ戻る](#目次)

## ・std::count (条件を満たす単純な型の要素を数えるぜ)
### 使い方
　この関数はとてもシンプルで、全ての要素から条件に一致する要素を数えます。それだけの機能です。
　std::findと同じように、ここでいう単純な型とは、intとかfloatとかになります。「単純な型でも少し複雑な事をしたい」や「構造体を数えたい」とかは、下記のstd::count_ifになります。といっても、別の手段でやろうと思えばいけますが...[^6]。正直、それなら後述の「std::count_ifを使え」と思います。

[std::count：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/count.html)

[^6]: 演算子オーバーロードをするとか色々あります。

### 引数
1.配列のbegin()
2.配列のend()
3.条件の値
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　個数が返ります。条件に一致する総数を返します。

### 計算量
　計算時間は：O(n)になります。つまり、配列のサイズ分を試行します。

### 簡単な例
```cpp
#include <algorithm>
#include <iostream>
#include <vector>
#include <list>

int main() {
    std::vector<int> v = { 1,4,3,3,1,2,2,1 };

  // 値が 1 の要素がいくつあるかを数える
  std::cout << "count of 1: " << std::count(v.begin(), v.end(), 1) << std::endl;
}
```

### 出力
```
count of 1: 3
```

[目次へ戻る](#目次)

## ・std::count_if (条件を満たす要素を数えるぜ)

### 使い方
　この関数はとてもシンプルで、全ての要素から条件に一致する要素を数えます。それだけの機能です。
　通常はこちらを使うことになると思います。

[std::count_if：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/count_if.html)

### 引数
1.配列のbegin()
2.配列のend()
3.条件関数
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　個数が返ります。条件に一致する総数を返します。

### 計算量
　計算時間は：O(n)になります。つまり、配列のサイズ分を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>

int main() {
 std::vector<int> v = { 1,4,3,3,1,2,2,1 };

  // 値が 1 または 3 の要素がいくつあるかを数える
  auto count = std::count_if(v.begin(), v.end(), [](int x) { return x == 1 || x == 3; });
  std::cout << "count of 1 or 3: " << count << std::endl;
}
```

### 出力
```
count of 1 or 3: 5
```

[目次へ戻る](#目次)

## ・std::mismatch (２つ目の配列と比べて、要素が一致しない最初の要素を探すぜ)

### 使い方
　「対象配列」と「比較用配列」をそれぞれ比べて、「対象配列」が「比較用配列」と異なる最初の要素を調べます。

[std::mismatch：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/mismatch.html)

### 引数
1.対象配列のbegin()
2.対象配列のend()
3.比較用配列のbegin()
4.比較用配列のend()[^9]
5.比較関数[^7] ※この引数を使うことはあまりないです。
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

[^9]: リファレンスにはこの引数が存在しないものもあります。ですが、C++14以降を使っているなら、ここは書くべきです。理由は後述します。

### 戻り値
　戻り値は「std::pair<「対象配列」のイテレーター, 「比較用配列」のイテレーター>」が返ります。
　「対象配列」が「比較用配列」と異なる要素を発見次第、その位置の「first: 対象配列イテレーター」と「second: 比較用配列イテレーター」をstd::pairとしたものを返します。発見できなかった場合は「first: **対象配列のend()**」と「second: **比較用配列のend()**」のstd::pairが返ります。なお、空の配列の場合は、その配列の**end()**が返ります。当たり前か(笑)

![mismatch.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/cc3c8ca1-1b16-8cbb-3e5e-d394fd9e2232.png)
※[画像元](https://youtu.be/bFSnXNIsK4A "某英語解説動画です。")

### 計算量
　最大計算時間は：「対象配列」のO(n)になります。つまり、最大で「対象配列」のサイズ分を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
#include <iterator> // std::begin(), std::end()の為
#include <string>   // to_string()の為

// mismatch の結果で得られた pair に対する情報を出力する
template <class Range1, class Range2, class Pair>
void print_mismatch_value(const Range1& r1, const Range2& r2, const Pair& p) {
  std::cout << "mismatch index: " << std::distance(std::begin(r1), p.first) << std::endl;
  std::cout << "mismatch value: (" << (std::end(r1) == p.first  ? "end" : std::to_string(*p.first)) << ","
                                   << (std::end(r2) == p.second ? "end" : std::to_string(*p.second)) << ")"
            << std::endl << std::endl;
}

int main() {
  const std::vector<int> v{ 1,2,3,4,3,2 };
  const std::vector<int> v2{ 1,2,4,3,2,1 };
  const std::vector<int> v3{ 1,2,3,4,3, };

  // v と v2 で異なる場所を探す
  auto pair = std::mismatch(v.begin(), v.end(), v2.begin(), v2.end());

  // 同じ意味になります。
  pair = std::mismatch(v.begin(), v.end(), v2.begin(), v2.end(), [](int left, int right) { return left == right; });

  print_mismatch_value(v, v2, pair);

  // v と v3 で異なる場所を探す。
  auto pair2 = std::mismatch(v3.begin(), v3.end(), v.begin(), v.end());
  print_mismatch_value(v3, v, pair2);

  // 第４引数を書かないと下になった場合、v.size() > v3.size() になるので途中で死にます。
  // auto pair3 = std::mismatch(v.begin(), v.end(), v3.begin());

  // 第４引数を書いているとv3.end()になった時点で終了し、戻り値はend()が返ります。なので途中で死ななくなります。
  auto pair3 = std::mismatch(v.begin(), v.end(), v3.begin(), v3.end()); // 第４引数を書いているのでOK
  print_mismatch_value(v, v3, pair3);
}
```

### 出力
```
mismatch index: 2
mismatch value: (3,4)

mismatch index: 5
mismatch value: (end,2)

mismatch index: 5
mismatch value: (2,end)
```

[目次へ戻る](#目次)

## ・std::equal (２つ目の配列と比べて、要素が全て一致するかを調べるぜ)

### 使い方
　この関数はとてもシンプルで、「対象配列」と「比較用配列」が同じかどうかを確かめます。それだけの機能です。

[std::equal：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/equal.html)

### 引数
1.対象配列のbegin()
2.対象配列のend()
3.比較用配列のbegin()
4.比較用配列のend()[^9]
5.比較関数[^7] ※この引数を使うことはあまりないです。
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

### 戻り値
　bool型が返ります。

### 計算量
　「対象配列」か「比較用配列」の少ない方の配列のO(n)になります。つまり、最大で「対象配列」か「比較用配列」の少ない方の配列のサイズ分を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v{ 1,2,3,4,3,2 };
  std::vector<int> v2{ 1,2,3,4,2,1 };
  std::vector<int> v3{ 1,2,3,4,2 };

  // コンテナの中身が同じかどうか調べる
  bool result = std::equal(v.begin(), v.end(), v2.begin(), v2.end());

  // 同じ意味になります。
  result = std::equal(v.begin(), v.end(), v2.begin(), v2.end(), [](int left, int right) { return left == right; });

  std::cout << std::boolalpha << result << std::endl;

  // 第４引数を書かないと下になった場合、v.size() > v3.size() になるので途中で死にます。
  // bool result2 = std::equal(v.begin(), v.end(), v3.begin());

  // 第４引数を書いているとどちらかがend()になった時点で終了し、戻り値はend()が返ります。なので途中で死ななくなります。
  bool result2 = std::equal(v.begin(), v.end(), v3.begin(), v3.end()); // 第４引数を書いているのでOK

  std::cout << std::boolalpha << result2 << std::endl;

  // x±1 の誤差を許すようにする
  bool result3 = std::equal(v.begin(), v.end(), v2.begin(), v2.end(),
                            [](int left, int right) { return left - 1 <= right && right <= left + 1; });
  std::cout << std::boolalpha << result3 << std::endl;
}
```

### 出力
```
false
false
true
```

[目次へ戻る](#目次)

## ・std::search (２つ目の配列全てに合う最初の要素を探すぜ)

### 使い方
　この関数はstd::find_first_ofと似ていますが、この関数は「対象配列」の中から「検索用配列」の要素「<font color="Red">**全て**</font>」に合う、「対象配列」の「**最初**の要素」を検索します。簡単に言うと、std::find_first_ofより正確にマッチするような検索になります。
　なお、C++17以降は検索器（[ボイヤー・ムーア法](http://capm-network.com/?tag=C%E8%A8%80%E8%AA%9E%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0-BM%E6%B3%95)）を使用した検索が可能になっています。

[std::search：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/search.html)

### 引数
1.対象配列のbegin()
2.対象配列のend()
3.検索用配列のbegin()
4.検索用配列のend()
5.比較関数[^7] ※この引数を使うことはあまりないです。
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

・検索器を指定する使い方の場合（[リファレンス](https://cpprefjp.github.io/reference/functional/boyer_moore_searcher.html)）
1.対象配列のbegin()
2.対象配列のend()
3.検索器

### 戻り値
　場所を示すイテレーターが返ります。
　「検索用配列」に完全一致する「対象配列」の、「最初の要素」の「要素中の最初」のイテレータを返します[^8]。発見出来なかった場合・「対象配列」が空の場合は、「対象配列」の**end()**を返します。
　※検索用配列が空の場合、std::find_first_ofは**end()**を返すのに比べて、std::searchは<font color="Red">**begin()**</font>を返します。[^10]

[^10]: なぜ、この仕様にしたんだ... 

![Search.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/161048c5-d22d-177f-ec0a-83dcc4c47b6d.png)
※[画像元](https://youtu.be/bFSnXNIsK4A "某英語解説動画です。")

### 計算量
　最大計算時間は「対象配列：O(n)」*「検索用配列：O(n)」になります。つまり、最大で「対象配列のサイズ分」×「検索用配列のサイズ分」を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  // 通常検索
  {
    std::vector<int> v{ 1,2,1,2,3 };
    std::vector<int> ls{ 1,2 };

    // 1,2 と連続している最初のシーケンスを探す
    auto it = std::search(v.begin(), v.end(), ls.begin(), ls.end());

    // v[0] の位置を指すイテレータが見つかる。
    if (it == v.end()) {
      std::cout << "not found" << std::endl;
    } else {
      std::cout << "found: index==" << std::distance(v.begin(), it) << ", num==" << *it << std::endl;
    }
  }

  std::cout << std::endl;

  // 検索器を使った検索の仕方
  {
    std::string text = "babcabaabaac";
    std::string pattern = "abaa";

    // ボイヤー・ムーア法で、文字列 (text) 内のサブ文字列 (pattern) を検索する。
    // patternを登録
    std::boyer_moore_searcher searcher {
      pattern.cbegin(),
      pattern.cend()
    };

    // textと検索器を指定して検索を実行
    auto result = std::search(text.cbegin(), text.cend(), searcher);

    // 見つかった
    if (result != text.cend()) {
      // 見つかった位置を取得
      std::ptrdiff_t n = std::distance(text.cbegin(), result);

      // 見つかった文字列 (pattern) を取得
      std::string s {result, result + pattern.size()};

      std::cout << "fount: index==" << n << ", pattern==\"" << s << "\"" << std:
:endl;
    }
    // 見つからなかった
    else {
      std::cout << "not found" << std::endl;
    }
  }
}
```

### 出力
```
found: index==0, num==1

found: index==4, pattern=="aabb"
```

[目次へ戻る](#目次)

## ・std::search_n (条件を満たすN個連続した最初の要素を探すぜ)

### 使い方
　この関数は、全ての要素から条件に一致する連続した最初の要素を発見します。[std::for_each_n](#stdfor_each_n-先頭からn個の数だけ処理するぜ "先頭からN個の数だけ処理するぜ")の様な使い方で使おうとすると「あれ？」となります[^11]。簡単に言うと、[std::find](#stdfind-条件を満たす最初の単純な型の要素を探すぜ "条件を満たす最初の単純な型の要素を探すぜ")と[std::find_if](#stdfind_if-条件を満たす最初の要素を探すぜ "条件を満たす最初の要素を探すぜ")を混ぜて、検索の値を複数対応させた関数になります。

[std::search_n：リファレンスページ](https://cpprefjp.github.io/reference/algorithm/search_n.html)

[^11]: 「～_n」シリーズの使い方に一致していない気がするのは気のせいでしょうか？

### 引数
1.配列のbegin()
2.配列のend()
3.連続要素数
4.検索要素元[^12]
5.比較関数7 ※この引数を使うことはあまりないです。
※int vec[5]のような配列の場合は「[iterator](https://cpprefjp.github.io/reference/iterator.html)」の「[std::begin()](https://cpprefjp.github.io/reference/iterator/begin.html)・[std::end()](https://cpprefjp.github.io/reference/iterator/end.html)」を使う必要があります。

[^12]: この引数自体は、実際は「単純な型」になることが多いと思います。ただ、ここに構造体を使い「比較関数」で比べるという、std::find_ifの機能も備わっています。

### 戻り値
　場所を示すイテレーターが返ります。
　検索の値が連続要素数分に連続して一致した要素の内、「最初の要素」の「要素中の最初」のイテレータを返します[^8]。発見出来なかった場合・配列が空の場合は、**end()**を返します。

![Search_n.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/540257/8a500538-2038-0648-ba3f-3c9ec8d6303f.png)
※[画像元](https://youtu.be/bFSnXNIsK4A "某英語解説動画です。")

### 計算量
　最大計算時間はO(n)になります。つまり、最大で配列のサイズ分を試行します。

### 簡単な例
```cpp

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
  std::vector<int> v = { 1,2,3,2,1,3,3,2,3,3,1 };

  // 3 が 2 つ連続している最初のシーケンスを探す
  auto it1 = std::search_n(v.cbegin(), v.cend(), 2, 3);

  // v[5] の位置を指すイテレータが見つかる。
  if (it1 == v.cend()) {
    std::cout << "not found" << std::endl;
  } else {
    std::cout << "found: index==" << std::distance(v.cbegin(), it1) << ", num==" << *it1 << std::endl;
  }

  // 3 未満が 2 つ連続している最初のシーケンスを探す
  auto it2 = std::search_n(v.cbegin(), v.cend(), 2, 3, [](int left, int right) { return left < right; });

  // v[0] の位置を指すイテレータが見つかる。
  if (it2 == v.cend()) {
    std::cout << "not found" << std::endl;
  } else {
    std::cout << "found: index==" << std::distance(v.cbegin(), it2) << ", num==" << *it2 << std::endl;
  }
}
```

### 出力
```
found: index==5, num==3
found: index==0, num==1
```

[目次へ戻る](#目次)

# 今回のまとめのようなもの
　今回は「std::find～」関係が難しい気がしますね。特に「[std::find_end](#stdfind_end-２つ目の配列に合う最後の要素を探すぜ "２つ目の配列に合う最後の要素を探すぜ")」「[std::find_first_of](#stdfind_first_of-２つ目の配列に合う最初の要素を探すぜ "２つ目の配列に合う最初の要素を探すぜ")」「[std::search](#stdsearch-２つ目の配列全てに合う最初の要素を探すぜ "２つ目の配列全てに合う最初の要素を探すぜ")」はかなり分かりにくいと思います。といっても、実際に使うことはあまりなさそうですが(笑)
　リファレンスに沿うようにしているので、間違いは無いと思いたいですが、間違っている可能性は十分にあります。疑問点や「ここ おかしいだろ」ポイントがあれば、ぜひコメント・編集リクエストください。修正します。

# 次回へ続く
　次回以降はリアルが忙しくならない限り近日中に公開します