std::find_end

헤더 `<algorithm>`
template< class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	에 정의됨 (1)	(C++20부터 constexpr)
template< class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(2)	(C++20부터 constexpr)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 );	(3)	(C++17부터)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class BinaryPred > ForwardIt1 find_end( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2, BinaryPred p );	(4)	(C++17부터)

소스 범위 [first2, last2) 에서 대상 범위 [first1, last1) 의 마지막 출현을 검색합니다.

1) 요소들은 operator== 을 사용하여 비교됩니다.

2) 요소들은 주어진 이진 술어 p 을 사용하여 비교됩니다.

3,4) (1,2) 와 동일하지만 policy 에 따라 실행됩니다.

이 오버로드들은 다음 표현식의 값이 true 인 경우에만 오버로드 해결에 참여합니다:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(C++20까지)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(C++20부터)

매개변수

first1, last1	-	소스 범위
를 정의하는 반복자 쌍	first2, last2	- 대상
범위	를 정의하는 반복자 쌍	p `true`- 요소가 동일한 것으로 간주되어야 하면 `bool pred(const Type1 &a, const Type2 &b);` 를 반환하는 이진 술어. `const &`술어 함수의 시그니처는 다음과 동등해야 합니다: `Type1`시그니처에 `Type2` 가 있을 필요는 없지만, 함수는 전달된 객체를 수정해서는 안 되며, 값 카테고리 에 관계없이 (const 가능) `Type1 &` 및 타입의 모든 값을 받아들일 수 있어야 합니다 (따라서 `Type1` 는 허용되지 않으며`Type1`, 도 이동이 복사와 동등하지 않는 한 허용되지 않습니다(C++11부터) ).`Type1` 타입 `Type2` 및 `ForwardIt1` 는 `ForwardIt2` 및 `Type1` 의 객체를 역참조한 후 암시적으로 각각 `Type2` 및
로 변환될 수 있어야 합니다.	policy	- 사용할 실행 정책

타입 요구사항 `ForwardIt1`- 는 LegacyForwardIterator
의 요구사항을 충족해야 합니다. `ForwardIt2`- 는 LegacyForwardIterator

의 요구사항을 충족해야 합니다.

반환값

소스 범위에서 대상 범위의 마지막 출현의 시작을 가리키는 반복자. last1대상 범위가 비어 있거나 소스 범위에 나타나지 않으면

가 반환됩니다.

복잡도$\scriptsize N_1$ $N 1$ 을 std::distance(first1, last1) 로 하고 $\scriptsize N_2$ $N 2$ 을 std::distance(first2, last2) 로 할 때:

1) 최대

N 2 \cdot(N 1 -N 2 +1)

번의 operator== 비교.

2) 최대

N 2 \cdot(N 1 -N 2 +1)

번의 p 적용.

3)

𝓞(N 2 \cdot(N 1 -N 2 +1))

번의 operator== 비교.

4)

𝓞(N 2 \cdot(N 1 -N 2 +1))

번의 p 적용.

예외

3,4) 실행 과정 중:

병렬화에 필요한 임시 메모리 자원을 사용할 수 없는 경우 std::bad_alloc 이 발생합니다.
알고리즘 인수를 통해 객체에 접근하는 중에 잡히지 않은 예외가 발생하면 실행 정책에 따라 동작이 결정됩니다 (표준 정책의 경우 std::terminate 가 호출됩니다).

가능한 구현

find_end (1)

template<class ForwardIt1, class ForwardIt2>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2)
{
    if (first2 == last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, last2);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

find_end (2)

template<class ForwardIt1, class ForwardIt2, class BinaryPred>
constexpr //< since C++20
ForwardIt1 find_end(ForwardIt1 first1, ForwardIt1 last1,
                    ForwardIt2 first2, ForwardIt2 last2, BinaryPred p)
{
    if (first2== last2)
        return last1;
    
    ForwardIt1 result = last1;
    while (true)
    {
        ForwardIt1 new_result = std::search(first1, last1, first2, first2, p);
        if (new_result == last1)
            break;
        else
        {
            result = new_result;
            first1 = result;
            ++first1;
        }
    }
    return result;
}

예제

이 코드 실행

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>

auto print_result = [](auto result, const auto& v)
{
    result == v.end()
        ? std::cout << "Sequence not found\n"
        : std::cout << "Last occurrence is at: " << std::distance(v.begin(), result)
                    << '\n';
};

int main()
{
    const auto v = {1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4};
    
    for (const auto& x : {std::array{1, 2, 3}, {4, 5, 6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end()); // overload (1)
        print_result(iter, v);
    }
    
    for (const auto& x : {std::array{-1, -2, -3}, {-4, -5, -6}})
    {
        auto iter = std::find_end(v.begin(), v.end(), x.begin(), x.end(), // overload (3)
                                  [](int x, int y)
                                  {
                                      return std::abs(x) == std::abs(y);
                                  });
        print_result(iter, v);
    }
}

출력:

Last occurrence is at: 8
Sequence not found
Last occurrence is at: 8
Sequence not found

결함 보고서

다음 동작 변경 결함 보고서가 이전에 발행된 C++ 표준에 소급하여 적용되었습니다.

DR	적용 대상	발행 시 동작	올바른 동작
LWG 1205	C++98	대상 범위가 비어 있을 때 반환값이 명확하지 않았음	이 경우 `last1` 반환
LWG 2150	C++98	"출현" 조건이 올바르지 않았음	수정됨

참조

ranges::find_end (C++20)	특정 범위에서 마지막 요소 시퀀스를 찾습니다 (알고리즘 함수 객체)
search	요소 범위의 첫 번째 출현을 검색합니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::search (C++20)	요소 범위의 첫 번째 출현을 검색합니다 (함수 템플릿 & 알고리즘 함수 객체)
includes	하나의 시퀀스가 다른 시퀀스의 부분 시퀀스인지 판별합니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::includes (C++20)	하나의 시퀀스가 다른 시퀀스의 부분 시퀀스인지 판별합니다 (함수 템플릿 & 알고리즘 함수 객체)
adjacent_find	동일하거나 주어진 술어를 충족하는 처음 두 개의 인접한 항목을 찾습니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::adjacent_find (C++20)
findfind_iffind_if_not (C++11)	특정 기준을 충족하는 첫 번째 요소를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::findranges::find_ifranges::find_if_not (C++20)(C++20)(C++20)	특정 기준을 충족하는 첫 번째 요소를 찾습니다 (함수 템플릿 & 알고리즘 함수 객체)
find_first_of	요소 집합 중 하나를 검색합니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::find_first_of (C++20)	요소 집합 중 하나를 검색합니다 (함수 템플릿 & 알고리즘 함수 객체)
search_n	범위에서 요소의 연속된 복사본의 첫 번째 출현을 검색합니다 (함수 템플릿 & 알고리즘 함수 객체)
ranges::search_n (C++20)	범위에서 요소의 연속된 복사본의 첫 번째 출현을 검색합니다 (함수 템플릿 & 알고리즘 함수 객체)

컴파일러 지원
프리스탠딩 및 호스티드
언어
표준 라이브러리
표준 라이브러리 헤더
명명된 요구사항
기능 테스트 매크로 (C++20)
언어 지원 라이브러리
개념 라이브러리 (C++20)
진단 라이브러리
메모리 관리 라이브러리
메타프로그래밍 라이브러리 (C++11)
일반 유틸리티 라이브러리
컨테이너 라이브러리
반복자 라이브러리
범위 라이브러리 (C++20)
알고리즘 라이브러리
문자열 라이브러리
텍스트 처리 라이브러리
수치 라이브러리
날짜 및 시간 라이브러리
입출력 라이브러리
파일시스템 라이브러리 (C++17)
동시성 지원 라이브러리 (C++11)
실행 제어 라이브러리 (C++26)
기술 사양
기호 인덱스
외부 라이브러리

ko.cppreference.net

Namespaces

Variants