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
- C++ working draft — General associative container requirements [associative.reqmts.general]
- C++ working draft — Class template less [comparisons.less]
- C++ working draft — Class template map overview [map.overview]
- Feature-testing recommendations for C++
- C++ working draft — String view non-member comparison functions [string.view.comparison]
- C++ working draft — String accessors [string.accessors]
- C++ working draft — Class template basic_string_view [string.view.template]
- P0254R1 — Integrating std::string_view and std::string
- C++ Draft International Standard (C++20) — N4860