----------------
title : C++ 레퍼런스 - std::search (<algorithm>)
cat_title : search
ref_title : std::search, search
path : /C++ Reference/algorithm
publish_date : 2020-10-16
----------------

##@ cpp-ref-start

#@ search

`<algorithm>` 에 정의됨

```cpp-formatted
// 참고로 C++ 20 부터 아래 모든 함수들은 constexpr 함수 이다.
// (1)
template <class ForwardIt1, class ForwardIt2>
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first,
                  ForwardIt2 s_last);

// C++ 17 에 추가됨
// (2)
template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2>
ForwardIt1 search(ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                  ForwardIt2 s_first, ForwardIt2 s_last);

// (3)
template <class ForwardIt1, class ForwardIt2, class BinaryPredicate>
ForwardIt1 search(ForwardIt1 first, ForwardIt1 last, ForwardIt2 s_first,
                  ForwardIt2 s_last, BinaryPredicate p);

// C++ 17 에 추가됨
// (4)
template <class ExecutionPolicy, class ForwardIt1, class ForwardIt2,
          class BinaryPredicate>
ForwardIt1 search(ExecutionPolicy&& policy, ForwardIt1 first, ForwardIt1 last,
                  ForwardIt2 s_first, ForwardIt2 s_last, BinaryPredicate p);

// C++ 17 에 추가됨
// (5)
template <class ForwardIt, class Searcher>
ForwardIt search(ForwardIt first, ForwardIt last, const Searcher& searcher);
```

**범위 내의 문자열을 검색해서 그 첫 번째로 발견된 위치를 리턴한다.**

(1) 부터 (4) 까지의 함수들의 경우 `[first, last)` 구간 에서 (즉 `first` 부터 `last` 직전 원소들 까지) `[s_first, s_last)` 까지에 해당하는 원소열이 존재하는지 확인한다. 이 때 (1) 의 경우 `operator==` 를 사용해서 비교를 하고, (3) 의 경우 비교할 두 원소를 받아 `bool` 타입을 리턴하는 함수를 통해 비교를 한다.

참고로 (2) 와 (4) 의 경우 실행 방식을 추가로 받을 수 있는데, `policy` 의 경우 반드시 `std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` 를 만족해야 한다.

(5) 의 경우 `[first, last)` 까지의 원소들에 대해 인자로 제공된 `searcher` 를 통해서 검색을 수행한다. 사실상 `return searcher(first, last).first` 를 실행하는 것과 동일하다.

참고로 표준 라이브러리에서 제공하는 `searcher` 들은 다음과 같다.

* `default_searcher` : 표준 C++ 라이브러리의 `search` 함수 작동 방식과 동일
* `boyer_moore_searcher` : Boyer-Moore 검색 알고리즘을 사용
* `boyer_moore_horspool_searcher` : Boyer-Moore-Horspool 검색 알고리즘을 사용

### 인자들

* `first, last` : 탐색 수행할 원소들의 범위
* `s_first, s_last`	: 찾고자 하는 원소들을 나타내는 범위
* `searcher` : 검색 알고리즘을 제공하는 `searcher`
* p : 비교할 두 원소가 같을 경우 `true` 를 리턴하는 함수로, 아래와 같은 형태여야 한다.

```cpp-formatted
bool pred(const Type1 &a, const Type2 &b);
```

참고로 인자의 타입의 경우 반드시 `const&` 일 필요는 없지만, `pred` 함수는 반드시 인자로 전달받은 객체를 변경하면 안된다. 또한 `search` 함수에 인자로 `const` 객체가 전달 될 수 도 있으므로 **왠만하면 `const&` 형태로 인자를 정의하자**. `Type1` 과 `Type2` 의 경우 각각 `ForwardIt1` 과 `ForwardIt2` 의 역참조 타입에서 변환 가능한 타입이어야만 한다.

### 리턴값

(1) 부터 (4) 까지의 함수들의 경우 `[first, last)` 안에서 가장 먼저 등장한 `[s_first, s_last)` 의 위치를 리턴한다. 만일 매칭되는 것이 없다면 `last` 가 리턴된다. 만약에 `[s_first, s_last)` 가 빈 구간이라면 `first` 가 리턴된다.

(5) 의 경우 `searcher.operator()` 의 결과값이 리턴된다. 즉, 찾은 원소열의 시작 위치가 리턴되고, 검색 결과가 없을 경우 `last` 가 리턴된다.

### 시간 복잡도

(1) 부터 (4) 까지의 함수들의 경우 최대 $$S*N$$ 번의 비교가 수행되는데 이 때 $$S$$ 는 `[s_first, s_last)` 구간의 크기이고 $$N$$ 은 `[first, last)` 구간의 크기 이다.

(5) 의 경우 시간 복잡도는 `searcher` 에 따라 달라진다.

### 구현 예시

```cpp-formatted
template <class ForwardIt1, class ForwardIt2>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last) {
  for (;; ++first) {
    ForwardIt1 it = first;
    for (ForwardIt2 s_it = s_first;; ++it, ++s_it) {
      if (s_it == s_last) {
        return first;
      }
      if (it == last) {
        return last;
      }
      if (!(*it == *s_it)) {
        break;
      }
    }
  }
}
```

다른 버전

```cpp-formatted
template <class ForwardIt1, class ForwardIt2, class BinaryPredicate>
constexpr ForwardIt1 search(ForwardIt1 first, ForwardIt1 last,
                            ForwardIt2 s_first, ForwardIt2 s_last,
                            BinaryPredicate p) {
  for (;; ++first) {
    ForwardIt1 it = first;
    for (ForwardIt2 s_it = s_first;; ++it, ++s_it) {
      if (s_it == s_last) {
        return first;
      }
      if (it == last) {
        return last;
      }
      if (!p(*it, *s_it)) {
        break;
      }
    }
  }
}
```

### 실행 예제

```cpp-formatted
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>

// cont 안에 s 가 있는지 없는지를 리턴한다.
template <typename Container>
bool in_quote(const Container& cont, const std::string& s) {
  return std::search(cont.begin(), cont.end(), s.begin(), s.end()) !=
         cont.end();
}

int main() {
  std::string str = "why waste time learning, when ignorance is instantaneous?";
  // str.find() can be used as well
  std::cout << std::boolalpha << in_quote(str, "learning") << '\n'
            << in_quote(str, "lemming") << '\n';

  std::vector<char> vec(str.begin(), str.end());
  std::cout << std::boolalpha << in_quote(vec, "learning") << '\n'
            << in_quote(vec, "lemming") << '\n';

  std::string in =
    "Lorem ipsum dolor sit amet, consectetur adipiscing elit,"
    " sed do eiusmod tempor incididunt ut labore et dolore magna aliqua";
  std::string needle = "pisci";

  // Boyer-Moore 알고리즘을 사용해서 검색을 수행한다.
  auto it =
    std::search(in.begin(), in.end(),
                std::boyer_moore_searcher(needle.begin(), needle.end()));
  if (it != in.end())
    std::cout << "The string " << needle << " found at offset "
              << it - in.begin() << '\n';
  else
    std::cout << "The string " << needle << " not found\n";
}
```

```exec
true
false
true
false
The string pisci found at offset 43
```

### 연관된 함수

* `find_end` : 주어진 범위에서 어떤 원소가 가장 마지막으로 등장하는 위치를 찾는다.
* `includes` : 어떤 원소열이 다른 원소열을 포함하고 있는지 확인한다.
* `equal` : 두 원소열이 같은지 다른지를 확인한다.
* `find`, `find_if`, `find_if_not` : 특정 조건을 만족하는 원소를 찾는다.
* `lexicographical_compare` : 두 원소열의 사전적 크기 비교를 수행한다.
* `mismatch` : 두 원소열에서 서로 다른 첫 번째 위치를 찾는다.
* `search_n` : 특정 원소가 여러번 반복되는 위치를 찾는다.