WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

Heterogene Suche mit einem transparenten Komparator

Durchsuche einen geordneten assoziativen Container mit einem anderen Typ als dem Schlüsseltyp, ohne einen temporären Schlüssel zu erzeugen. Entscheidend sind die von `std::less<>` aktivierten Überladungen und eine konsistente Vergleichsordnung.

Version: 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;

Bei der heterogenen Suche darf die Suchanfrage einen Typ K haben, der vom gespeicherten Schlüsseltyp Key abweicht. In std::map, std::multimap, std::set und std::multiset gibt es heterogene Überladungen von find, count, lower_bound, upper_bound und equal_range seit C++14, von contains seit C++20. Der gespeicherte Schlüsseltyp bleibt unverändert.

Das gewöhnliche find nimmt const Key& entgegen. Die Funktionsvorlage find(const K&) nimmt nur dann an der Überladungsauflösung teil, wenn Compare::is_transparent gültig ist und einen Typ bezeichnet. std::less<> aus <functional> ist std::less<void>: Es stellt diesen Markertyp bereit und wendet < auf die übergebenen Operanden an, deren Typen verschieden sein dürfen. Der Standardkomparator einer Map, std::less<Key>, hat keinen solchen Marker. Mit ihm muss für die Suche mit std::string_view in std::string-Schlüsseln explizit ein Schlüssel erzeugt werden, etwa mit find(std::string{query}).

Der Marker prüft den Vergleich nicht. Für find müssen Schlüssel und Suchanfrage in beiden Richtungen vergleichbar sein, und zwar im Einklang mit der strikten schwachen Ordnung der Schlüssel. Ein Treffer bedeutet !comp(key, query) && !comp(query, key), nicht key == query. Vergleiche Schlüssel nicht unter Beachtung der Groß- und Kleinschreibung und gemischte Paare ohne diese Unterscheidung: Die gemischten Vergleiche könnten die sortierten Schlüssel nicht konsistent in Bereiche aufteilen. std::less<> verwendet für std::string und std::string_view dieselbe lexikografische Ordnung.

Bei der Suche mit der View entsteht kein temporärer std::string. Der View gehören die Zeichen nicht: Sie müssen während des gesamten Aufrufs gültig bleiben, und find speichert die View nicht. find arbeitet logarithmisch in der Elementzahl und liefert einen Iterator auf einen Treffer oder end(); prüfe das Ergebnis vor dem Dereferenzieren. Geltungsbereich: ISO C++23; die Unterstützung kann je nach Implementierung variieren. Das Beispiel nutzt std::string_view aus C++17 und setzt mindestens C++17 voraus.

Beispiele

#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");
}

Ergebnis

pear: 7
plum: not found

Die Map speichert Schlüssel vom Typ `std::string`. Die erste View umfasst nur die ersten vier Zeichen von `pear tart`. Die Suche findet daher `pear` und gibt `pear: 7` aus. Für `plum` liefert `find` den Iterator `end()`, und das Programm gibt `plum: not found` aus.

Zugehörige Lektionen

  • C++ · Lektion 31 · Fortgeschritten · Version: 3

Quellen