KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

std::ranges::equal_range — bereik van gelijkwaardige elementen

std::ranges::equal_range vindt het halfopen bereik van elementen die volgens een vergelijker gelijkwaardig zijn aan een zoekwaarde. Het ondersteunt bereiken, iterator-sentinelparen en projecties; de gegevens moeten passend gepartitioneerd zijn, wat sorteren garandeert.

Versie: C++23; repository compiler flag, production runtime not attested

Syntax

std::ranges::equal_range(first, last, value)
std::ranges::equal_range(first, last, value, comp)
std::ranges::equal_range(first, last, value, comp, proj)
std::ranges::equal_range(range, value)
std::ranges::equal_range(range, value, comp)
std::ranges::equal_range(range, value, comp, proj)

std::ranges::equal_range, gedeclareerd in <algorithm>, bepaalt het bereik [lower_bound, upper_bound) zonder de gegevens te wijzigen. Gelijkwaardigheid betekent dat beide vergelijkingen comp(proj(element), value) en comp(value, proj(element)) onwaar zijn; dit hoeft niet overeen te komen met operator==. Als er geen overeenkomst is, is het resultaat een leeg bereik op de invoegpositie van de waarde.

De aanroep accepteert een iterator-sentinelpaar of een volledig bereik. Er zijn ten minste forward-iteratoren vereist en comp moet voldoen aan de eisen voor een strikte zwakke ordening. De standaardwaarden zijn std::ranges::less en std::identity. De projectie transformeert elementen, niet de zoekwaarde. De gegevens moeten zo gepartitioneerd zijn dat de booleaanse resultaten van elk van de expressies comp(proj(element), value) en !comp(value, proj(element)) eerst een waar prefix en daarna een onwaar suffix vormen. Sorteren met dezelfde vergelijker en projectie is voldoende; het schenden van de voorwaarden leidt tot ongedefinieerd gedrag.

De iteratoroverload retourneert std::ranges::subrange<I>, terwijl de bereikoverload std::ranges::borrowed_subrange_t<R> retourneert. Voor een tijdelijk bereik dat niet aan borrowed_range voldoet, is het laatstgenoemde type std::ranges::dangling, geen bruikbaar deelbereik. Het resultaat bewaart geen kopieën van elementen: de gegevens moeten blijven bestaan en de iterators moeten geldig blijven.

Voor N elementen zijn er hoogstens 2 * log2(N) + O(1) vergelijkingen en projecties; zonder iterators met willekeurige toegang kan het verplaatsen van iterators lineair zijn. Het voorbeeld zoekt sleutels via &Item::key: drie overeenkomsten beslaan de indices [1, 4), terwijl sleutel 3 een leeg resultaat oplevert. Dit voorbeeld is bedoeld voor een C++23-buildconfiguratie; compatibiliteit met productie-uitvoering is niet bevestigd.

Voorbeelden

#include <algorithm>
#include <array>
#include <iostream>

struct Item {
    int key;
};

int main() {
    const std::array<Item, 5> items{{{1}, {2}, {2}, {2}, {4}}};
    const auto matches = std::ranges::equal_range(items, 2, {}, &Item::key);
    std::cout << "count=" << matches.size() << '\n';
    std::cout << "begin=" << (matches.begin() - items.begin()) << '\n';
    std::cout << "end=" << (matches.end() - items.begin()) << '\n';
    const auto missing = std::ranges::equal_range(items, 3, {}, &Item::key);
    std::cout << "missing=" << missing.empty() << '\n';
}

Resultaat

count=3
begin=1
end=4
missing=1

De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.

Bronnen