Namespaces
Variants

std::ranges::search

cppreference.net에서
 
 
알고리즘 라이브러리
제약된 알고리즘 및 범위에 대한 알고리즘 (C++20)
제약된 알고리즘, 예: ranges::copy, ranges::sort, ...
정렬 및 관련 연산
분할 연산
(C++11)    

정렬 연산
이진 탐색 연산
(분할된 범위에 대해)
집합 연산 (정렬된 범위에 대해)
병합 연산 (정렬된 범위에 대해)
힙 연산
최소/최대 연산
(C++11)
(C++17)
사전식 비교 연산
순열 연산


 
제약된 알고리즘
이 메뉴의 모든 이름은 네임스페이스 std::ranges
에 속합니다. 비수정 시퀀스 연산
수정 시퀀스 연산
분할 연산
정렬 연산
이진 탐색 연산 (정렬된 범위에 대해)
       
       
집합 연산 (정렬된 범위에 대해)
힙 연산
최소/최대 연산
       
       
순열 연산
폴드 연산
수치 연산
(C++23)            
초기화되지 않은 저장소에 대한 연산
반환 유형
 
헤더 <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)
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 = {} );
(C++20부터) (2)
(C++20부터)1) 에서 첫[first2, last2) 번째 요소 시퀀스의 발생을 [first1, last1) 범위 pred 내에서 검색합니다. 요소는 이진 조건자 proj2으로 투영된 후 proj1 및
을(를) 각각 사용하여 비교됩니다.2) (와)과 동일(1)r1하지만 r2을(를) 첫 번째 소스 범위로 사용하고 ranges::begin(r1)을(를) 두 번째 소스 범위로 사용하며, first1을(를) ranges::end(r1)(으)로, last1을(를) ranges::begin(r2)(으)로, first2을(를) ranges::end(r2)(으)로, last2을(를)

(으)로 사용하는 것과 같습니다.이 페이지에 설명된 함수형 엔티티는 알고리즘 함수 객체 (비공식적으로 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}

같이 보기

처음으로 같거나 주어진 조건을 만족하는 두 개의 인접한 항목을 찾습니다
(알고리즘 함수 객체)
특정 조건을 만족하는 첫 번째 요소를 찾습니다
(알고리즘 함수 객체)
특정 범위에서 요소들의 마지막 시퀀스를 찾습니다
(알고리즘 함수 객체)
요소 집합 중 하나를 검색합니다
(알고리즘 함수 객체)
범위가 주어진 요소 또는 부분 범위를 포함하고 있는지 확인합니다
(알고리즘 함수 객체)
하나의 시퀀스가 다른 시퀀스의 부분 시퀀스인지 판별합니다
(알고리즘 함수 객체)
두 범위가 달라지는 첫 번째 위치를 찾습니다
(알고리즘 함수 객체)
범위에서 요소의 연속된 복사본의 수가 나타나는 첫 번째 위치를 검색합니다
(알고리즘 함수 객체)
요소의 범위가 처음으로 나타나는 위치를 검색합니다
(함수 템플릿)