Namespaces
Variants

std::ranges::search

Von de.cppreference.net
 
 
Algorithmenbibliothek
Eingeschränkte Algorithmen und Algorithmen auf Bereichen (C++20)
Eingeschränkte Algorithmen, z.B. ranges::copy, ranges::sort, ...
Nicht modifizierende Sequenzoperationen    
Batch-Operationen
(C++17)
Suchoperationen
Modifizierende Sequenzoperationen
Kopieroperationen
(C++11)
(C++11)
Swap-Operationen
Transformationsoperationen
Generierungsoperationen
Entfernungsoperationen
Reihenfolgeändernde Operationen
(bis C++17)(C++11)
(C++20)(C++20)
Stichprobenoperationen
(C++17)

Sortier- und verwandte Operationen
Partitionierungsoperationen
(C++11)    

Sortieroperationen
Binäre Suchoperationen
(auf partitionierten Bereichen)
Mengenoperationen (auf sortierten Bereichen)
Mischoperationen (auf sortierten Bereichen)
Heap-Operationen
Minimum/Maximum-Operationen
(C++11)
(C++17)
Lexikografische Vergleichsoperationen
Permutationsoperationen


 
Eingeschränkte Algorithmen
Alle Namen in diesem Menü gehören zum Namensraum std::ranges
Nicht modifizierende Sequenzoperationen
Modifizierende Sequenzoperationen
Partitionierungsoperationen
Sortieroperationen
Binäre Suchoperationen (auf sortierten Bereichen)
       
       
Mengenoperationen (auf sortierten Bereichen)
Heap-Operationen
Minimum/Maximum-Operationen
       
       
Permutationsoperationen
Faltungsoperationen
Numerikoperationen
(C++23)            
Operationen auf nicht initialisiertem Speicher
Rückgabetypen
 
Definiert in Header <algorithm>
Aufrufsignatur
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) (seit 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) (seit C++20)
1) Sucht nach dem ersten Auftreten der Folge von Elementen [first2, last2) im Bereich [first1, last1). Die Elemente werden mit dem binären Prädikat pred verglichen, nachdem sie mit proj2 bzw. proj1 projiziert wurden.
2) Wie (1), verwendet jedoch r1 als ersten Quellbereich und r2 als zweiten Quellbereich, als ob ranges::begin(r1) als first1, ranges::end(r1) als last1, ranges::begin(r2) als first2 und ranges::end(r2) als last2 verwendet würden.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloids bekannt), das heißt:

Parameter

first1, last1 - das Iterator-Sentinel-Paar, das den Bereich der zu untersuchenden Elemente definiert (auch haystack genannt)
first2, last2 - das Iterator-Sentinel-Paar, das den Bereich der zu suchenden Elemente definiert (auch needle genannt)
r1 - der Bereich der zu untersuchenden Elemente (auch haystack genannt)
r2 - der Bereich der zu suchenden Elemente (auch needle genannt)
pred - binäres Prädikat, das auf die projizierten Elemente angewendet wird
proj1 - Projektion, die auf die Elemente im ersten Bereich angewendet wird
proj2 - Projektion, die auf die Elemente im zweiten Bereich angewendet wird

Rückgabewert

1) Gibt einen ranges:: subrange -Wert zurück, der das erste Vorkommen der Sequenz [ first2 , last2 ) (auch Nadel genannt) im Bereich [ first1 , last1 ) (auch Heuhaufen genannt) darstellt, nach Anwendung der Projektionen proj1 und proj2 auf die Elemente beider Sequenzen bzw. mit anschließender Anwendung des binären Prädikats pred zum Vergleich der projizierten Elemente.

Falls kein solches Vorkommen gefunden wird, wird ranges:: subrange { last1, last1 } zurückgegeben.

Falls der zu durchsuchende Bereich (auch Nadel genannt) leer ist, d.h. first2 == last2 , dann wird ranges:: subrange { first1, first1 } zurückgegeben.
2) Gleich wie (1) aber der Rückgabetyp ist ranges:: borrowed_subrange_t < R1 > .

Komplexität

Höchstens S * N Anwendungen des entsprechenden Prädikats und jeder Projektion, wobei
(1) S = ranges:: distance ( first2, last2 ) und N = ranges:: distance ( first1, last1 ) ;
(2) S = ranges:: distance ( r2 ) und N = ranges:: distance ( r1 ) .

Mögliche Implementierung

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 {};

Beispiel

#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};
    // the search uses iterator pairs begin()/end():
    constexpr auto found1 = std::ranges::search(
        haystack.begin(), haystack.end(),
        needle.begin(), needle.end());
    print(1, haystack, needle, found1);
    // the search uses ranges r1, r2:
    constexpr auto found2 = std::ranges::search(haystack, needle);
    print(2, haystack, needle, found2);
    // 'needle' range is empty:
    constexpr auto none {""sv};
    constexpr auto found3 = std::ranges::search(haystack, none);
    print(3, haystack, none, found3);
    // 'needle' will not be found:
    constexpr auto awl {"efg"sv};
    constexpr auto found4 = std::ranges::search(haystack, awl);
    print(4, haystack, awl, found4);
    // the search uses custom comparator and projections:
    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);
}

Ausgabe:

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}

Siehe auch

findet die ersten beiden benachbarten Elemente, die gleich sind (oder ein gegebenes Prädikat erfüllen)
(Algorithmus-Funktionsobjekt)
findet das erste Element, das bestimmte Kriterien erfüllt
(Algorithmus-Funktionsobjekt)
findet die letzte Folge von Elementen in einem bestimmten Bereich
(Algorithmus-Funktionsobjekt)
sucht nach einem beliebigen Element aus einer Menge
(Algorithmus-Funktionsobjekt)
prüft, ob der Bereich das angegebene Element oder den angegebenen Teilbereich enthält
(Algorithmus-Funktionsobjekt)
bestimmt, ob eine Sequenz eine Teilsequenz einer anderen ist
(Algorithmus-Funktionsobjekt)
findet die erste Position, an der sich zwei Bereiche unterscheiden
(Algorithmus-Funktionsobjekt)
sucht nach dem ersten Vorkommen einer Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich
(Algorithmus-Funktionsobjekt)
sucht nach dem ersten Vorkommen eines Bereichs von Elementen
(Funktionstemplate)