std::ranges:: search

From cppreference.net

헤더 파일에 정의됨 `<algorithm>`
함수 시그니처
template < std:: forward_iterator I1, std:: sentinel_for < I1 > S1, std:: forward_iterator I2, std:: sentinel_for < I2 > S2, class Pred = ranges:: equal_to , class Proj1 = std:: identity , class Proj2 = std:: identity > requires std:: indirectly_comparable < I1, I2, Pred, Proj1, Proj2 > constexpr ranges:: subrange < I1 > search ( I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = { } , Proj1 proj1 = { } , Proj2 proj2 = { } ) ;	(1)	(C++20부터)
template < ranges:: forward_range R1, ranges:: forward_range R2, class Pred = ranges:: equal_to , class Proj1 = std:: identity , class Proj2 = std:: identity > requires std:: indirectly_comparable < ranges:: iterator_t < R1 > , ranges:: iterator_t < R2 > , Pred, Proj1, Proj2 > constexpr ranges:: borrowed_subrange_t < R1 > search ( R1 && r1, R2 && r2, Pred pred = { } , Proj1 proj1 = { } , Proj2 proj2 = { } ) ;	(2)	(C++20부터)

1) 범위

first1

last1

에서 요소 시퀀스

first2

last2

의 첫 번째 발생을 검색합니다. 요소들은 각각 proj2 와 proj1 으로 투영된 후 이진 조건자 pred 를 사용하여 비교됩니다.

2) (1) 과 동일하지만, r1 을 첫 번째 소스 범위로, r2 를 두 번째 소스 범위로 사용합니다. 마치 ranges:: begin ( r1 ) 를 first1 으로, ranges:: end ( r1 ) 를 last1 으로, ranges:: begin ( r2 ) 를 first2 으로, ranges:: end ( r2 ) 를 last2 로 사용하는 것과 같습니다.

이 페이지에서 설명하는 함수형 개체들은 algorithm function objects (일반적으로 niebloids 로 알려진)입니다. 즉:

명시적 템플릿 인수 목록은 이들 중 어느 것을 호출할 때도 지정할 수 없습니다.
이들 중 어느 것도 인수 의존 이름 검색 에 보이지 않습니다.
이들 중 어느 것이 함수 호출 연산자 왼쪽의 이름으로 일반 비한정 이름 검색 에 의해 발견될 때, 인수 의존 이름 검색 이 억제됩니다.

first1, last1	-	검사할 요소들의 범위 를 정의하는 반복자-센티넬 쌍 (일명 haystack )
first2, last2	-	검색할 요소들의 범위 를 정의하는 반복자-센티넬 쌍 (일명 needle )
r1	-	검사할 요소들의 범위 (일명 haystack )
r2	-	검색할 요소들의 범위 (일명 needle )
pred	-	투영된 요소들에 적용할 이항 조건자
proj1	-	첫 번째 범위의 요소들에 적용할 투영
proj2	-	두 번째 범위의 요소들에 적용할 투영

반환값

1) 범위

first1

last1

(일명 haystack )에서 시퀀스

first2

last2

(일명 needle )의 첫 번째 발생을 나타내는 ranges:: subrange 값을 반환합니다. 이때 각 시퀀스의 요소에 proj1 과 proj2 투영을 적용한 후, 투영된 요소들을 비교하기 위해 이항 조건자 pred 를 적용합니다.

해당 발생이 발견되지 않으면, ranges:: subrange { last1, last1 } 이 반환됩니다.

검색 대상 범위(일명 needle )가 비어 있는 경우, 즉 first2 == last2 인 경우, ranges:: subrange { first1, first1 } 이 반환됩니다.

2) (1) 과 동일하지만 반환 타입은 ranges:: borrowed_subrange_t < R1 > 입니다.

복잡도

최대 S * N 번의 해당 predicate 및 각 projection 적용, 여기서
(1) S = ranges:: distance ( first2, last2 ) 및 N = ranges:: distance ( first1, last1 ) ;
(2) S = ranges:: distance ( r2 ) 및 N = ranges:: distance ( r1 ) .

가능한 구현

struct search_fn
{
    template<std::forward_iterator I1, std::sentinel_for<I1> S1,
             std::forward_iterator I2, std::sentinel_for<I2> S2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
    constexpr ranges::subrange<I1>
        operator()(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        for (;; ++first1)
        {
            I1 it1 = first1;
            for (I2 it2 = first2;; ++it1, ++it2)
            {
                if (it2 == last2)
                    return {first1, it1};
                if (it1 == last1)
                    return {it1, it1};
                if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2)))
                    break;
            }
        {
    }
    template<ranges::forward_range R1, ranges::forward_range R2,
             class Pred = ranges::equal_to,
             class Proj1 = std::identity,
             class Proj2 = std::identity>
    requires std::indirectly_comparable<ranges::iterator_t<R1>,
                                        ranges::iterator_t<R2>, Pred, Proj1, Proj2>
    constexpr ranges::borrowed_subrange_t<R1>
        operator()(R1&& r1, R2&& r2, Pred pred = {},
                   Proj1 proj1 = {}, Proj2 proj2 = {}) const
    {
        return (*this)(ranges::begin(r1), ranges::end(r1),
                       ranges::begin(r2), ranges::end(r2),
                       std::move(pred), std::move(proj1), std::move(proj2));
    }
};
inline constexpr search_fn search {};

예제

이 코드 실행

#include <algorithm>
#include <cctype>
#include <iostream>
#include <iterator>
#include <string_view>
using namespace std::literals;
void print(int id, const auto& haystack, const auto& needle, const auto& found)
{
    std::cout << id << ") search(\"" << haystack << "\", \"" << needle << "\"); ";
    const auto first = std::distance(haystack.begin(), found.begin());
    const auto last = std::distance(haystack.begin(), found.end());
    if (found.empty())
        std::cout << "not found;";
    else
    {
        std::cout << "found: \"";
        for (const auto x : found)
            std::cout << x;
        std::cout << "\";";
    }
    std::cout << " subrange: {" << first << ", " << last << "}\n";
}
int main()
{
    constexpr auto haystack {"abcd abcd"sv};
    constexpr auto needle {"bcd"sv};
    // 검색은 반복자 쌍 begin()/end()를 사용합니다:
    constexpr auto found1 = std::ranges::search(
        haystack.begin(), haystack.end(),
        needle.begin(), needle.end());
    print(1, haystack, needle, found1);
    // 검색은 범위 r1, r2를 사용합니다:
    constexpr auto found2 = std::ranges::search(haystack, needle);
    print(2, haystack, needle, found2);
    // 'needle' 범위가 비어 있습니다:
    constexpr auto none {""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);
    // 'needle'을 찾을 수 없습니다:
    constexpr auto awl {"efg"sv};
    constexpr auto found4 = std::ranges::search(haystack, awl);
    print(4, haystack, awl, found4);
    // 검색은 사용자 정의 비교 함수와 투영 함수를 사용합니다:
    constexpr auto bodkin {"234"sv};
    auto found5 = std::ranges::search(haystack, bodkin,
        [](const int x, const int y) { return x == y; }, // pred
        [](const int x) { return std::toupper(x); }, // proj1
        [](const int y) { return y + 'A' - '1'; }); // proj2
    print(5, haystack, bodkin, found5);
}

출력:

1) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
2) search("abcd abcd", "bcd"); found: "bcd"; subrange: {1, 4}
3) search("abcd abcd", ""); not found; subrange: {0, 0}
4) search("abcd abcd", "efg"); not found; subrange: {9, 9}
5) search("abcd abcd", "234"); found: "bcd"; subrange: {1, 4}

참고 항목

ranges::adjacent_find (C++20)	서로 인접한 두 항목 중 첫 번째로 같은 항목(또는 주어진 조건자를 만족하는 항목)을 찾음 (알고리즘 함수 객체)
ranges::find ranges::find_if ranges::find_if_not (C++20) (C++20) (C++20)	특정 기준을 만족하는 첫 번째 요소를 찾음 (알고리즘 함수 객체)
ranges::find_end (C++20)	특정 범위에서 마지막 요소 시퀀스를 찾음 (알고리즘 함수 객체)
ranges::find_first_of (C++20)	요소 집합 중 하나를 검색함 (알고리즘 함수 객체)
ranges::contains ranges::contains_subrange (C++23) (C++23)	범위가 주어진 요소나 부분 범위를 포함하는지 확인함 (알고리즘 함수 객체)
ranges::includes (C++20)	한 시퀀스가 다른 시퀀스의 부분 시퀀스이면 true 를 반환함 (알고리즘 함수 객체)
ranges::mismatch (C++20)	두 범위가 처음으로 달라지는 위치를 찾음 (알고리즘 함수 객체)
ranges::search_n (C++20)	범위에서 연속된 여러 개의 요소가 처음 나타나는 위치를 검색함 (알고리즘 함수 객체)
search	요소 범위가 처음 나타나는 위치를 검색함 (함수 템플릿)

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Diagnostics library
Memory management library
Metaprogramming library (C++11)
General utilities library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library (C++17)
Concurrency support library (C++11)
Execution control library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.net

Namespaces

Variants

std::ranges:: search

목차

매개변수

반환값

복잡도

가능한 구현

예제

참고 항목