std::ranges:: search_n

From cppreference.net

(Anmerkung: Der bereitgestellte HTML-Code enthält keinen übersetzbaren Text, da alle Tags leer sind oder nur Klassenattribute enthalten, die gemäß den Anweisungen nicht übersetzt werden dürfen.)

Definiert in Header `<algorithm>`
Aufrufsignatur
	(1)
template < std:: forward_iterator I, std:: sentinel_for < I > S, class T, class Pred = ranges:: equal_to , class Proj = std:: identity > requires std:: indirectly_comparable < I, const T * , Pred, Proj > constexpr ranges:: subrange < I > search_n ( I first, S last, std:: iter_difference_t < I > count, const T & value, Pred pred = { } , Proj proj = { } ) ;			(seit C++20) (bis C++26)
template < std:: forward_iterator I, std:: sentinel_for < I > S, class Pred = ranges:: equal_to , class Proj = std:: identity , class T = std :: projected_value_t < I, Proj > > requires std:: indirectly_comparable < I, const T * , Pred, Proj > constexpr ranges:: subrange < I > search_n ( I first, S last, std:: iter_difference_t < I > count, const T & value, Pred pred = { } , Proj proj = { } ) ;			(seit C++26)
		(2)
template < ranges:: forward_range R, class T, class Pred = ranges:: equal_to , class Proj = std:: identity > requires std:: indirectly_comparable < ranges:: iterator_t < R > , const T * , Pred, Proj > constexpr ranges:: borrowed_subrange_t < R > search_n ( R && r, ranges:: range_difference_t < R > count, const T & value, Pred pred = { } , Proj proj = { } ) ;				(seit C++20) (bis C++26)
template < ranges:: forward_range R, class Pred = ranges:: equal_to , class Proj = std:: identity , class T = std :: projected_value_t < ranges:: iterator_t < R > , Proj > > requires std:: indirectly_comparable < ranges:: iterator_t < R > , const T * , Pred, Proj > constexpr ranges:: borrowed_subrange_t < R > search_n ( R && r, ranges:: range_difference_t < R > count, const T & value, Pred pred = { } , Proj proj = { } ) ;				(seit C++26)

1) Durchsucht den Bereich

first

last

nach der ersten Sequenz von count Elementen, deren projizierte Werte jeweils gleich dem gegebenen value sind, gemäß dem binären Prädikat pred .

2) Gleich wie (1) , verwendet jedoch r als Quellbereich, als ob ranges:: begin ( r ) als first und ranges:: end ( r ) als last verwendet würde.

Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind algorithm function objects (informell bekannt als Niebloids ), das heißt:

Explizite Template-Argumentlisten können beim Aufruf keiner von ihnen angegeben werden.
Keiner von ihnen ist sichtbar für argument-dependent lookup .
Wenn einer von ihnen durch normal unqualified lookup als Name links vom Funktionsaufruf-Operator gefunden wird, wird argument-dependent lookup unterdrückt.

Inhaltsverzeichnis

Parameter

first, last	-	das Iterator-Sentinel-Paar, das den Bereich der zu untersuchenden Elemente definiert (auch haystack genannt)
r	-	der Bereich der zu untersuchenden Elemente (auch haystack genannt)
count	-	die Länge der zu suchenden Sequenz
value	-	der zu suchende Wert (auch needle genannt)
pred	-	das binäre Prädikat, das die projizierten Elemente mit value vergleicht
proj	-	die Projektion, die auf die Elemente des zu untersuchenden Bereichs angewendet wird

Rückgabewert

1) Gibt ein std :: ranges:: subrange -Objekt zurück, das ein Paar von Iteratoren im Bereich

first

last

enthält, die die gefundene Teilsequenz bezeichnen.

Falls keine solche Teilsequenz gefunden wird, wird std :: ranges:: subrange { last, last } zurückgegeben.

Falls count <= 0 , wird std :: ranges:: subrange { first, first } zurückgegeben.

2) Gleich wie (1) aber der Rückgabetyp ist ranges:: borrowed_subrange_t < R > .

Komplexität

Linear: höchstens ranges:: distance ( first, last ) Anwendungen des Prädikats und der Projektion.

Hinweise

Eine Implementierung kann die Effizienz der Suche im Durchschnitt verbessern, wenn die Iteratoren das Konzept std:: random_access_iterator modellieren.

Feature-Test Makro	Wert	Std	Feature
`__cpp_lib_algorithm_default_value_type`	`202403`	(C++26)	Listeninitialisierung für Algorithmen

Mögliche Implementierung

struct search_n_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S,
             class Pred = ranges::equal_to, class Proj = std::identity,
             class T = std::projected_value_t<I, Proj>>
    requires std::indirectly_comparable<I, const T*, Pred, Proj>
    constexpr ranges::subrange<I>
        operator()(I first, S last, std::iter_difference_t<I> count,
                   const T& value, Pred pred = {}, Proj proj = {}) const
    {
        if (count <= 0)
            return {first, first};
        for (; first != last; ++first)
            if (std::invoke(pred, std::invoke(proj, *first), value))
            {
                I start = first;
                std::iter_difference_t<I> n{1};
                for (;;)
                {
                    if (n++ == count)
                        return {start, std::next(first)}; // gefunden
                    if (++first == last)
                        return {first, first}; // nicht gefunden
                    if (!std::invoke(pred, std::invoke(proj, *first), value))
                        break; // nicht gleich value
                }
            }
        return {first, first};
    }
    template<ranges::forward_range R,
             class Pred = ranges::equal_to, class Proj = std::identity,
             class T = std::projected_value_t<ranges::iterator_t<R>, Proj>>
    requires std::indirectly_comparable<ranges::iterator_t<R>, const T*, Pred, Proj>
    constexpr ranges::borrowed_subrange_t<R>
        operator()(R&& r, ranges::range_difference_t<R> count,
                   const T& value, Pred pred = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r),
                       std::move(count), value,
                       std::move(pred), std::move(proj));
    }
};
inline constexpr search_n_fn search_n {};

Beispiel

Diesen Code ausführen

#include <algorithm>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
int main()
{
    namespace ranges = std::ranges;
    static constexpr auto nums = {1, 2, 2, 3, 4, 1, 2, 2, 2, 1};
    constexpr int count{3};
    constexpr int value{2};
    typedef int count_t, value_t;
    constexpr auto result1 = ranges::search_n
    (
        nums.begin(), nums.end(), count, value
    );
    static_assert // gefunden
    (
        result1.size() == count &&
        std::distance(nums.begin(), result1.begin()) == 6 &&
        std::distance(nums.begin(), result1.end()) == 9
    );
    constexpr auto result2 = ranges::search_n(nums, count, value);
    static_assert // gefunden
    (
        result2.size() == count &&
        std::distance(nums.begin(), result2.begin()) == 6 &&
        std::distance(nums.begin(), result2.end()) == 9
    );
    constexpr auto result3 = ranges::search_n(nums, count, value_t{5});
    static_assert // nicht gefunden
    (
        result3.size() == 0 &&
        result3.begin() == result3.end() &&
        result3.end() == nums.end()
    );
    constexpr auto result4 = ranges::search_n(nums, count_t{0}, value_t{1});
    static_assert // nicht gefunden
    (
        result4.size() == 0 &&
        result4.begin() == result4.end() &&
        result4.end() == nums.begin()
    );
    constexpr char symbol{'B'};
    auto to_ascii = [](const int z) -> char { return 'A' + z - 1; };
    auto is_equ = [](const char x, const char y) { return x == y; };
    std::cout << "Finde eine Teilsequenz " << std::string(count, symbol) << " im ";
    std::ranges::transform(nums, std::ostream_iterator<char>(std::cout, ""), to_ascii);
    std::cout << '\n';
    auto result5 = ranges::search_n(nums, count, symbol, is_equ, to_ascii);
    if (not result5.empty())
        std::cout << "Gefunden an Position "
                  << ranges::distance(nums.begin(), result5.begin()) << '\n';
    std::vector<std::complex<double>> nums2{{4, 2}, {4, 2}, {1, 3}};
    #ifdef __cpp_lib_algorithm_default_value_type
        auto it = ranges::search_n(nums2, 2, {4, 2});
    #else
        auto it = ranges::search_n(nums2, 2, std::complex<double>{4, 2});
    #endif
    assert(it.size() == 2);
}

Ausgabe:

Finde eine Teilsequenz BBB in der ABBCDABBBA
Gefunden an Position 6

Siehe auch

ranges::adjacent_find (C++20)	findet die ersten zwei benachbarten Elemente, die gleich sind (oder ein gegebenes Prädikat erfüllen) (Algorithmus-Funktionsobjekt)
ranges::find ranges::find_if ranges::find_if_not (C++20) (C++20) (C++20)	findet das erste Element, das bestimmte Kriterien erfüllt (Algorithmus-Funktionsobjekt)
ranges::find_end (C++20)	findet die letzte Sequenz von Elementen in einem bestimmten Bereich (Algorithmus-Funktionsobjekt)
ranges::find_first_of (C++20)	sucht nach einem beliebigen Element aus einer Menge von Elementen (Algorithmus-Funktionsobjekt)
ranges::includes (C++20)	gibt true zurück, wenn eine Sequenz eine Teilsequenz einer anderen ist (Algorithmus-Funktionsobjekt)
ranges::mismatch (C++20)	findet die erste Position, an der zwei Bereiche sich unterscheiden (Algorithmus-Funktionsobjekt)
ranges::search (C++20)	sucht nach dem ersten Vorkommen eines Bereichs von Elementen (Algorithmus-Funktionsobjekt)
search_n	sucht nach dem ersten Vorkommen einer Anzahl aufeinanderfolgender Kopien eines Elements in einem Bereich (Funktionstemplate)

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