LoginSignup
1
1

More than 3 years have passed since last update.

@HnniTns(Tns Hnni)

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

Last updated at Posted at 2020-06-24

最初に

　この記事はalgorithmにある、全ての関数の使い方・簡単な例・計算量などを書いています。一応C++er初心者向けに書いています。出来る限りリファレンスより分かり易く書いているつもりですが、「そんなことより、厳選されて分かり易いのはどれ！」という方にはこの記事をお勧めします1。

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

　この記事はラムダ式2・イテレーター3を使っているのでそこだけは注意してください。最後にこの動画も見てみて下さい。英語ですが図が書かれていて分かり易いと思います。

補足説明

　この記事はリファレンスにそって説明していきます4。計算量はO記法で載せています5。なお、説明はリファレンスをベースにして、補足を入れています。
　あと、C++11・14・17以降で動く関数もいくつか存在するので注意してください。

目次

章 タイトル 対応バージョン
第１章 シーケンスを変更しない操作 ---
1. std::all_of C++11以降
1. std::any_of C++11以降
1. std::none_of C++11以降
1. std::for_each
1. std::for_each_n C++17以降
1. std::find
1. std::find_if
1. std::find_if_not C++11以降
1. std::find_end
1. std::find_first_of
1. std::adjacent_find
1. std::count
1. std::count_if
1. std::mismatch
1. std::equal
1. std::search
1. std::search_n
第２章 シーケンスを変更する操作：前半（近日中に公開します） ---
第３章 シーケンスを変更する操作：後半（近日中に公開します） ---
第４章 ソートや、それに関連した操作（近日中に公開します） ---

※目次を作ること自体、先ほどの記事から参考にしました。ありがとうございます！

1.シーケンスを変更しない操作

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

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

使い方

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

std::all_of：リファレンスページ

引数

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

戻り値

　boolが戻ります。条件に一致しない要素を発見したらその時点でfalseを返します。なお、空の配列はtrueが返されます。

計算量

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

簡単な例

#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：リファレンスページ

引数

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

戻り値

　boolが戻ります。条件に一致する要素を発見したらその時点でtrueを返します。空の配列はfalseが返されます。

計算量

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

簡単な例

#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：リファレンスページ

引数

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

戻り値

　boolが戻ります。条件に一致する要素を発見したらその時点でfalseを返します。空の配列はtrueが返されます。

計算量

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

簡単な例


#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：リファレンスページ

引数

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

戻り値

　引数と同じ関数オブジェクトが戻ります6。

計算量

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

簡単な例


#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：リファレンスページ

引数

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

戻り値

　場所を示すイテレーターが返ります。
　「終えた位置 + 1」の位置のイテレーターが返ります。配列が空の場合はend()が返ります。

計算量

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

簡単な例


#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になります。といっても、別の手段でやろうと思えばいけますが...7。正直、それなら後述の「std::find_ifを使え」と思います。

std::find：リファレンスページ

引数

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

戻り値

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

計算量

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

簡単な例


#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：リファレンスページ

引数

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

戻り値

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

計算量

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

簡単な例


#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：リファレンスページ

引数

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

戻り値

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

計算量

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

簡単な例


#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 (２つ目の配列に合う最後の要素を探すぜ)

使い方

　ややこしいですが、「対象配列」の中から「検索用配列」の要素「全て」に合う、「対象配列」の「最後の要素」を検索します。「全ての配列から条件を満たす最後の要素を探す」ではないので注意して下さい。

std::find_end：リファレンスページ

引数

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

戻り値

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

Find End.png
※画像元

計算量

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

簡単な例


#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のほぼ逆です。「対象配列」の中から「検索用配列」の要素の「一部」 に合う、「対象配列」の「最初の要素」を検索します。

std::find_first_of：リファレンスページ

引数

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

戻り値

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

Find First Of.png
※画像元

計算量

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

簡単な例


#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：リファレンスページ

引数

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

戻り値

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

計算量

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

簡単な例


#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になります。といっても、別の手段でやろうと思えばいけますが...7。正直、それなら後述の「std::count_ifを使え」と思います。

std::count：リファレンスページ

引数

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

戻り値

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

計算量

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

簡単な例

#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：リファレンスページ

引数

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

戻り値

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

計算量

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

簡単な例


#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：リファレンスページ

引数

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

戻り値

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

mismatch.png
※画像元

計算量

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

簡単な例


#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：リファレンスページ

引数

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

戻り値

　bool型が返ります。

計算量

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

簡単な例


#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と似ていますが、この関数は「対象配列」の中から「検索用配列」の要素「全て」に合う、「対象配列」の「最初の要素」を検索します。簡単に言うと、std::find_first_ofより正確にマッチするような検索になります。
　なお、C++17以降は検索器（ボイヤー・ムーア法）を使用した検索が可能になっています。

std::search：リファレンスページ

引数

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

・検索器を指定する使い方の場合（リファレンス）
1.対象配列のbegin()
2.対象配列のend()
3.検索器

戻り値

　場所を示すイテレーターが返ります。
　「検索用配列」に完全一致する「対象配列」の、「最初の要素」の「要素中の最初」のイテレータを返します9。発見出来なかった場合・「対象配列」が空の場合は、「対象配列」のend()を返します。
　※検索用配列が空の場合、std::find_first_ofはend()を返すのに比べて、std::searchはbegin()を返します。11

Search.png
※画像元

計算量

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

簡単な例


#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の様な使い方で使おうとすると「あれ？」となります12。簡単に言うと、std::findとstd::find_ifを混ぜて、検索の値を複数対応させた関数になります。

std::search_n：リファレンスページ

引数

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

戻り値

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

Search_n.png
※画像元

計算量

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

簡単な例


#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」「std::find_first_of」「std::search」はかなり分かりにくいと思います。といっても、実際に使うことはあまりなさそうですが(笑)
　リファレンスに沿うようにしているので、間違いは無いと思いたいですが、間違っている可能性は十分にあります。疑問点や「ここ おかしいだろ」ポイントがあれば、ぜひコメント・編集リクエストください。修正します。

次回へ続く

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

  1. といっても、「使えない」と「使わない」は違うので、少なくとも大体の関数の使い方を知っておくことをお勧めします。 ↩

  2. ラムダ式はかなり有能なので、知らない人は各々調べてみて下さい。知らなくてもとりあえず、関数をある関数の引数に持ってこれると思ってください。勿論、それだけじゃないですけど、面白いですよ。  ↩

  3. イテレーターの存在理由の一つに、「コンテナクラス×関数の数」から「コンテナクラス+関数の数」に減らせるからというのがあります。 ↩

  4. 暇なら試しに読んでみて下さい、結構面白いですよ。 ↩

  5. 自分はO記法の理解がふんわりしているので、具体的な時間の方が分かり（ゲフンゲフン...）  ↩

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

  7. 演算子オーバーロードをするとか色々あります。 ↩

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

  9. わけがわからないよ...。 ↩

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

  11. なぜ、この仕様にしたんだ...  ↩

  12. 「～_n」シリーズの使い方に一致していない気がするのは気のせいでしょうか？ ↩

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

1
1
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1