KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / C++

Heterogeen zoeken met een transparante comparator

Zoek in een geordende associatieve container met een ander type dan het sleuteltype, zonder een tijdelijke sleutel te maken. Leer hoe `std::less<>` de zoekoverloads beschikbaar maakt en waarom gemengde vergelijkingen de sleutelvolgorde moeten respecteren.

Versie: ISO C++23; implementation support may vary

Syntax

using Index = std::map<std::string, int, std::less<>>;
// Heterogeneous std::map::find member overloads (shown inside the class):
template<class K> iterator find(const K& x);
template<class K> const_iterator find(const K& x) const;

Bij heterogeen zoeken kan de zoekwaarde een type K hebben dat afwijkt van het opgeslagen sleuteltype Key. In std::map, std::multimap, std::set en std::multiset bestaan heterogene overloads van find, count, lower_bound, upper_bound en equal_range sinds C++14, en van contains sinds C++20. Het type van de opgeslagen sleutels verandert niet.

De gewone find neemt een const Key& aan. De functietemplate find(const K&) doet alleen mee aan overloadresolutie als Compare::is_transparent geldig is en een type aanduidt. std::less<> uit <functional> is std::less<void>: het stelt dit markeertype beschikbaar en past < toe op de meegegeven operanden, die verschillende typen mogen hebben. De standaardcomparator van een map, std::less<Key>, heeft dit markeertype niet. Met die comparator moet je om met een std::string_view tussen std::string-sleutels te zoeken expliciet een sleutel maken, bijvoorbeeld met find(std::string{query}).

Het markeertype controleert de vergelijking niet. Voor find moeten de sleutel en de zoekwaarde in beide richtingen vergelijkbaar zijn, in overeenstemming met de strikt zwakke ordening van de sleutels. Een overeenkomst betekent !comp(key, query) && !comp(query, key), niet key == query. Vergelijk sleutels onderling niet hoofdlettergevoelig als je gemengde paren hoofdletterongevoelig vergelijkt: de gemengde vergelijkingen delen de gesorteerde sleutels dan mogelijk niet op in consistente bereiken. std::less<> gebruikt dezelfde lexicografische volgorde voor std::string en std::string_view.

Zoeken met de view maakt geen tijdelijke std::string. De view is geen eigenaar van de tekens: die moeten gedurende de hele aanroep geldig blijven, en find bewaart de view niet. find is logaritmisch in het aantal elementen en geeft een iterator naar een overeenkomst of end() terug; controleer het resultaat voordat je het dereferentieert. Reikwijdte: ISO C++23; ondersteuning kan per implementatie verschillen. Het voorbeeld gebruikt std::string_view uit C++17 en vereist ten minste C++17.

Voorbeelden

#include <functional>
#include <iostream>
#include <map>
#include <string>
#include <string_view>

int main() {
    const std::map<std::string, int, std::less<>> stock{
        {"apple", 3}, {"pear", 7}
    };

    const auto report = [&stock](std::string_view query) {
        if (const auto it = stock.find(query); it != stock.end()) {
            std::cout << it->first << ": " << it->second << '\n';
        } else {
            std::cout << query << ": not found\n";
        }
    };

    report(std::string_view{"pear tart", 4});
    report("plum");
}

Resultaat

pear: 7
plum: not found

De map bewaart `std::string`-sleutels. De eerste view omvat alleen de eerste vier tekens van `pear tart`, dus de zoekactie vindt `pear` en drukt `pear: 7` af. Voor `plum` geeft `find` de iterator `end()` terug en drukt het programma `plum: not found` af.

Gerelateerde lessen

  • C++ · Les 31 · Gevorderd · Versie: 3

Bronnen