std::ranges:: binary_search

Damit ranges::binary_search erfolgreich ist, muss der Bereich [ first , last ) mindestens teilweise geordnet sein in Bezug auf value , d.h. er muss alle folgenden Anforderungen erfüllen:

• partitioniert in Bezug auf std:: invoke ( comp, std:: invoke ( proj, element ) , value ) (d.h. alle projizierten Elemente, für die der Ausdruck true ist, stehen vor allen Elementen, für die der Ausdruck false ist).
• partitioniert in Bezug auf ! std:: invoke ( comp, value, std:: invoke ( proj, element ) ) .
• für alle Elemente gilt: wenn std:: invoke ( comp, std:: invoke ( proj, element ) , value ) true ist, dann ist auch ! std:: invoke ( comp, value, std:: invoke ( proj, element ) ) true .

Ein vollständig sortierter Bereich erfüllt diese Kriterien.

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 Funktionsaufrufoperator gefunden wird, wird argument-dependent lookup unterdrückt.

Parameter

Rückgabewert

true falls ein Element gleich value gefunden wird, false andernfalls.

Komplexität

Die Anzahl der durchgeführten Vergleiche und Projektionen ist logarithmisch im Abstand zwischen first und last (höchstens log 2 (last - first) + O(1) Vergleiche und Projektionen). Für Iterator-Sentinel-Paare, die nicht std::random_access_iterator modellieren, ist die Anzahl der Iterator-Inkremente jedoch linear.

Hinweise

std::ranges::binary_search gibt keinen Iterator auf das gefundene Element zurück, wenn ein Element gefunden wird, dessen Projektion gleich value ist. Wenn ein Iterator benötigt wird, sollte stattdessen std::ranges::lower_bound verwendet werden.

Mögliche Implementierung

struct binary_search_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S,
             class Proj = std::identity, class T = std::projected_value_t<I, Proj>,
             std::indirect_strict_weak_order
                 <const T*, std::projected<I, Proj>> Comp = ranges::less>
    constexpr bool operator()(I first, S last, const T& value,
                              Comp comp = {}, Proj proj = {}) const
    {
        auto x = ranges::lower_bound(first, last, value, comp, proj);
        return (!(x == last) && !(std::invoke(comp, value, std::invoke(proj, *x))));
    }
    template<ranges::forward_range R, class Proj = std::identity,
             class T = std::projected_value_t<ranges::iterator_t<R>, Proj>,
             std::indirect_strict_weak_order
                 <const T*, std::projected<ranges::iterator_t<R>,
                                           Proj>> Comp = ranges::less>
    constexpr bool operator()(R&& r, const T& value, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), value,
                       std::move(comp), std::move(proj));
    }
};
inline constexpr binary_search_fn binary_search;

Beispiel

#include <algorithm>
#include <cassert>
#include <complex>
#include <iostream>
#include <ranges>
#include <vector>
int main()
{
    constexpr static auto haystack = {1, 3, 4, 5, 9};
    static_assert(std::ranges::is_sorted(haystack));
    for (const int needle : std::views::iota(1)
                          | std::views::take(3))
    {
        std::cout << "Suche nach " << needle << ": ";
        std::ranges::binary_search(haystack, needle)
            ? std::cout << "gefunden " << needle << '\n'
            : std::cout << "kein Treffer!\n";
    }
    using CD = std::complex<double>;
    std::vector<CD> nums{{1, 1}, {2, 3}, {4, 2}, {4, 3}};
    auto cmpz = [](CD x, CD y){ return abs(x) < abs(y); };
    #ifdef __cpp_lib_algorithm_default_value_type
        assert(std::ranges::binary_search(nums, {4, 2}, cmpz));
    #else
        assert(std::ranges::binary_search(nums, CD{4, 2}, cmpz));
    #endif
}

Suche nach 1: gefunden 1
Suche nach 2: kein Treffer!
Suche nach 3: gefunden 3

Siehe auch