----------------
title : C++ 레퍼런스 - find_end 함수 (<algorithm>)
cat_title : find_end
ref_title : find_end, std::find_end
path : /C++ Reference/algorithm
publish_date : 2019-02-04
----------------

##@ cpp-ref-start

#@ find_end

`<algorithm>` 에 정의됨

```cpp-formatted
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)` 가 빈 원소열이라면 어떤 결과가 리턴될지는 정의되어있지 않다.


### 구현 예시

```cpp-formatted
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;
}
```

### 실행 예제

```cpp-formatted
// 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;
}
```

실행 결과

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

### 참고 자료

* `search` : 어떤 원소들의 나열을 검색한다.
* `find$algorithm` : 범위 안에 원소들 중 **값**이 일치하는 원소를 찾는다.
* `find_if` : 범위 안에 원소들 중 **조건**과 일치하는 원소를 찾는다.