모두의 코드
C++ 레퍼런스 - find_end 함수 (<algorithm>)

작성일 : 2019-02-04 이 글은 13429 번 읽혔습니다.

아직 C++ 에 친숙하지 않다면 씹어먹는 C++ 은 어때요?

find_end

<algorithm> 에 정의됨

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2, ForwardIterator2 last2);
/* 두 원소를 비교하는 pred 를 사용한 버전 */
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2, ForwardIterator2 last2,
                          BinaryPredicate pred);

범위 안에 맨 마지막으로 등장하는 부분 원소열(subsequence)을 찾는다.

first2 부터 last2 까지의 원소들이 first1 에서 last1 까지의 원소열에서 마지막으로 등장하는 위치를 찾습니다. 이 때, 원소열의 시작 위치를 가리키는 반복자를 리턴합니다. 만일, 일치하는 원소열이 없다면 last1 이 리턴됩니다.

예를 들어서 cdbabcdabdabc 라는 원소열에서 abc 라는 부분 원소열은 cdb(abc)dabd(abc) 이와 같이 괄호 친 부분에 등장하는데, find_end 의 경우 마지막으로 등장하는 위치, 즉 10 을 리턴하게 됩니다.

두 개의 원소열의 원소들은 operator== 혹은 pred 함수가 주어진다면, pred(/* 원소1 */, /* 원소 2*/) 꼴을 통해서 비교됩니다. 부분 원소열이 완벽하게 포함되어 있어야지만, 포함되어 있다고 인정됩니다.

이 함수는 마지막으로 나타나는 위치를 찾지만, 첫 번째로 등장하는 원소열을 찾고 싶다면 search 함수를 이용하면 됩니다.

인자들

  • first1, last1 : 부분 원소열을 찾을 목표가 되는 원소열의 시작과 끝점 바로 뒤를 가리키는 반복자들. 즉 [first1, last1) 로 생각하면 된다.

  • first2, last2 : 어떤 부분 원소열을 찾을 것인지. 범위 역시 시작과 끝점 바로 뒤를 가리키는 반복자들이다.

  • pred : 두 원소열의 원소들을 비교하는 함수로, 각 원소열의 원소들을 하나씩 인자로 받는 (총 인자로 2 개의 원소를 받는) 함수이다. 이 때 리턴값은 bool 이거나 bool 로 변환할 수 있는 타입이어야 한다. 리턴값은 두 원소가 일치하는지 아니지를 판별하는데 사용된다.

참고로 pred 를 전달하지 않는다면 그냥 operator== 를 통해 원소들을 비교하게 된다.

리턴값

마지막으로 [first2, last2)[first1, last1) 에서 나타나는 위치를 리턴한다. 만일 해당 위치를 찾을 수 없다면 last1 을 리턴한다.

만일 [first2, last2) 가 빈 원소열이라면 어떤 결과가 리턴될지는 정의되어있지 않다.

구현 예시

template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1,
                          ForwardIterator2 first2, ForwardIterator2 last2) {
  if (first2 == last2) return last1;  // specified in C++11

  ForwardIterator1 ret = last1;

  while (first1 != last1) {
    ForwardIterator1 it1 = first1;
    ForwardIterator2 it2 = first2;
    while (*it1 == *it2) {  // or: while (pred(*it1,*it2)) for version (2)
      ++it1;
      ++it2;
      if (it2 == last2) {
        ret = first1;
        break;
      }
      if (it1 == last1) return ret;
    }
    ++first1;
  }
  return ret;
}

실행 예제

// find_end example
#include <algorithm>  // std::find_end
#include <iostream>   // std::cout
#include <vector>     // std::vector

bool myfunction(int i, int j) { return (i == j); }

int main() {
  int myints[] = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};
  std::vector<int> haystack(myints, myints + 10);

  int needle1[] = {1, 2, 3};

  // using default comparison:
  std::vector<int>::iterator it;
  it = std::find_end(haystack.begin(), haystack.end(), needle1, needle1 + 3);

  if (it != haystack.end())
    std::cout << "needle1 의 마지막 등장 위치 " << (it - haystack.begin())
              << '\n';

  int needle2[] = {4, 5, 1};

  // using predicate comparison:
  it = std::find_end(haystack.begin(), haystack.end(), needle2, needle2 + 3,
                     myfunction);

  if (it != haystack.end())
    std::cout << "needle2 의 마지막 등장 위치 " << (it - haystack.begin())
              << '\n';

  return 0;
}

실행 결과

실행 결과

needle1 의 마지막 등장 위치 5
needle2 의 마지막 등장 위치 3

참고 자료

  • search : 어떤 원소들의 나열을 검색한다.

  • find : 범위 안에 원소들 중 이 일치하는 원소를 찾는다.

  • find_if : 범위 안에 원소들 중 조건과 일치하는 원소를 찾는다.

첫 댓글을 달아주세요!
프로필 사진 없음
강좌에 관련 없이 궁금한 내용은 여기를 사용해주세요

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