search

<algorithm> 에 정의됨

// 참고로 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 를 리턴하는 함수로, 아래와 같은 형태여야 한다.

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 에 따라 달라진다.

구현 예시

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;
      }
    }
  }
}

다른 버전

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;
      }
    }
  }
}

실행 예제

#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";
}

실행 결과

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 : 특정 원소가 여러번 반복되는 위치를 찾는다.

첫 댓글을 달아주세요!

강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요

다음으로 로그인

또는 직접 입력하세요 (댓글 수정시 비밀번호가 필요합니다)

댓글 달기

댓글을 불러오는 중입니다..