© Sergiy Tryapitsyn / 123RF.com

Assoziative Container in C++ unterscheiden sich hinsichtlich ihrer Performance deutlich. Was ist die gebräuchlichste Wahl, und wann greift man besser zu Alternativen?

Im vorangegangenen Artikel dieser Serie [1] zeigte der Autor, dass in 99 Prozent aller Anwendungsfälle »std::array« oder »std::vector« die beste Wahl für einen sequenziellen Container sind. Diese Regel basiert auf den C++ Core Guidelines [2].

Eine ähnliche Faustregel lässt sich für assoziative Container aufstellen: In 95 Prozent aller Anwendungsfälle sind »std::map« oder »std::unordered_map« die beste Wahl. Gelegentlich wird der mit dem Schlüssel assoziierte Wert nicht gebraucht – das sind die verbleibenden 5 Prozent.

Bevor der Artikel auf die Details eingeht und einen Überblick und Messergebnisse zu den beiden assoziativen Container-Typen präsentiert, ist hier meine Faustregel: Wenn man einen Container mit einer Schlüssel-Wert-Assoziation benötigt und die Schlüssel sortiert sein sollen, verwendet man »std::map«, anderenfalls »std::unordered_map«. Doch zuerst einmal gilt es, Ordnung in die acht assoziativen Container zu bringen.

Die acht Variationen

Die Tabelle “Assoziative Container” bringt alle acht assoziativen Container auf den Punkt. Um Ordnung in dieser Gegenüberstellung der acht assoziativen Containern zu schaffen, gilt es, drei Fragen zu mit ja oder nein zu beantworten: Ist der Container geordnet (hinsichtlich der Ordnung auf den Schlüsseln)? Besitzt der Schüssel einen assoziierten Wert? Und sind mehrere identische Schlüssel möglich?

Wenn der Container nicht geordnet ist, nennt man ihn »unordered«. Ist mit dem Schlüssel ein Wert assoziiert, wird der Container »map« genannt, sonst »set«. Kann der Container mehr als einen identischen Schlüssel besitzen, trägt er zusätzlich »multi« im Namen.

Zugegeben, diese Zusammenfassung der assoziativen Container ist sehr kompakt. Mehr Information liefert der Artikel zu C++11 aus Ausgabe 12/2013 [3]. Ist im Folgenden von einem geordneten Container die Rede, geht es um die Ordnung auf den Schlüsseln. Das Ganze will ich im Folgenden noch einmal – und weniger formal – erklären.

Ein Telefonbuch

Die acht Variationen assoziativer Container stehen für verschiedene Versionen eines Telefonbuchs. Was ist ein Telefonbuch? Dabei handelt es sich um eine Sequenz von Schlüssel-Wert-Paaren. Darin wird der Schlüssel (Name) verwendet, um auf den Wert (Telefonnummer) zuzugreifen.

Die Namen in einem Telefonbuch können geordnet oder nicht geordnet sein. Das Telefonbuch ordnet jedem Namen eine Telefonnummer zu oder auch nicht. Darüber hinaus kann es mehrere identische Namen erlauben. Dies ist sehr praktisch, denn dadurch wird es möglich, sowohl die Handy- als auch die Festnetznummer zu hinterlegen.

Nun dreht sich alles um den zentralen Unterschied zwischen geordneten und ungeordneten assoziativen Containern: Die Zugriffszeit auf einen geordneten assoziativen Container ist logarithmisch, die auf einen ungeordneten assoziativen Container im Durchschnitt konstant. Exemplarisch verwende ich im Folgenden ein »std::map« als geordneten assoziativen Container und eine »std::unordered_map« als ungeordneten assoziativen Container.

Performance-Vergleich

Was meint die im Durchschnitt konstante Zugriffszeit für einen ungeordneten assoziativen Container wie »std::unordered_map«? Die Abfrage einer Telefonnummer ist unabhängig von der Größe des Telefonbuchs. Wirklich? Hier ein kleiner Leistungstest: Das Telefonbuch besitzt anfangs circa 89 000 Einträge und wird im Lauf des Tests in Zehnerschritten bis auf 89 000 000 Einträge erweitert. Nach jedem Schritt findet eine Abfrage des Telefonbuchs nach allen Telefonnummern statt. Das heißt, dass die Namen in einer beliebigen Reihenfolge verwendet werden.

Der folgende Auszug in Abbildung 1 zeigt einen Teil der initialen Version des Telefonbuchs. Ein Doppelpunkt trennt die Name-Nummer-Paare, ein Komma Name und Nummer. In Listing 1 liest zuerst die »main«-Funktion den Inhalt der Datei ein, erzeugt das Telefonbuch (»std::map« oder »std::unordered_map«, je nach Inhalt der Zeilen 11 und 12), erhält eine zufällige Permutation der Namen und testet letztlich die Performance. Eine »std::unordered_map« unterstützt eine Obermenge des Interfaces einer »std::map«.

Abbildung 1: Ein Ausschnitt des Telefonbuchs.

#include <chrono>
#include <fstream>
#include <iostream>
#include <map>
#include <random>
#include <regex>
#include <sstream>
#include <string>
#include <unordered_map>
#include <vector>
// using map = std::map<std::string, int>;
using map = std::unordered_map<std::string, int>;
std::ifstream openFile(const std::string& myFile){
  std::ifstream file(myFile, std::ios::in);
  if ( !file ){
    std::cerr << "Can't open file "+ myFile + "!" << '\n';
    exit(EXIT_FAILURE);
  }
  return file;
}
std::string readFile(std::ifstream file){
  std::stringstream buffer;
  buffer << file.rdbuf();
  return buffer.str();
}
map createTeleBook(const std::string& fileCont){
  map teleBook;
  std::regex regColon(":");
  std::sregex_token_iterator fileContIt(fileCont.begin(), fileCont.end(), regColon, -1);
  const std::sregex_token_iterator fileContEndIt;
  std::string entry;
  std::string key;
  int value;
  while (fileContIt != fileContEndIt){
    entry = *fileContIt++;
    auto comma = entry.find(",");
    key = entry.substr(0, comma);
    value = std::stoi(entry.substr(comma + 1, entry.length() -1));
    teleBook[key] = value;
  }
  return teleBook;
}
std::vector<std::string> getRandomNames(const map& teleBook){
  std::vector<std::string> allNames;
  for (const auto& pair: teleBook) allNames.push_back(pair.first);
  std::random_device randDev;
  std::mt19937 generator(randDev());
  std::shuffle(allNames.begin(), allNames.end(), generator);
  return allNames;
}
void measurePerformance(const std::vector<std::string>& names, map& m){
  auto start = std::chrono::steady_clock::now();
  for (const auto& name: names) m[name];
  std::chrono::duration<double> dur= std::chrono::steady_clock::now() - start;
  std::cout << "Access time: " << dur.count() << " seconds" << '\n';
}
int main(int argc, char* argv[]){
  std::cout << '\n';
  // get the filename
  std::string myFile;
  if ( argc == 2 ){
    myFile= {argv[1]};
  }
  else{
    std::cerr << "Filename missing !" << '\n';
    exit(EXIT_FAILURE);
  }
  std::ifstream file = openFile(myFile);
  std::string fileContent = readFile(std::move(file));
  map teleBook = createTeleBook(fileContent);
  std::cout << "teleBook.size(): " <<  teleBook.size() << '\n';
  std::vector<std::string> randomNames = getRandomNames(teleBook);
  measurePerformance(randomNames, teleBook);
  std::cout << '\n';
}

Die Zeilen 11 und 12 sind die interessanteste Zeilen. Kommentiert man Zeile 12 aus, kommt eine Map (»std::map«) zum Einsatz. Bei Auskommentieren der Zeile 11 verwendet das Testprogramm dagegen eine »std::unordered_map«. Die entsprechenden Beziehungen gelten auch für die Paare »std::set« und »std::unordered_set«, »std::multiset« und »std::unordered_multiset« sowie »std::multimap« und »std::unordered_multimap«. Die ungeordnete Variante bietet eine Schnittstelle an, die auch das geordnete Pendant unterstützt.

Es gibt aber noch einige weitere interessante Funktionen. In »createTeleBook()« iteriert die While-Schleife über alle Name-Nummer-Tokens, erzeugt durch den regulären Ausdruck »regColon« (Zeile 28). Jedes Token wird durch ein Komma separiert (Zeile 36). Am Ende fügt die Funktion das Name-Nummer-Paar dem Telefonbuch hinzu (Zeile 39). »getRandomNames()« schiebt alle Namen auf den Vektor (Zeile 45) und erzeugt eine Permutation der Namen (Zeile 49).

Zu guter Letzt fragt »measurePerformance()« nach dem Namen im Telefonbuch (Zeile 53) und ermittelt so die Leistungswerte. Abbildung 2 und Abbildung 3 zeigen die Performance für die »std::map« und die »std::unordered_map«. Die Ausgabe der Programmläufe stellt exakt dar, wie groß die Telefonbücher sind.

Abbildung 2: Ein Programmdurchlauf mit einer »std::map«.

Abbildung 3: Ein Durchlauf mit einer »std::unordered_map«.

Die Zahlen bestätigen die Angaben der Tabelle “Assoziative Container”: Die Zugriffszeit auf eine »std::map« hängt logarithmisch von der Anzahl der Elemente ab, die Zugriffszeit auf eine »std::unordered_map« ist im Durchschnitt konstant. Der Plot in Abbildung 4 stellt die Performance der »std::map« jener der »std::unordered_map« gegenüber. Für 100 000 Einträge ist die »std::map« dreimal langsamer als die »std::unordered_map«, für 100 000 000 Einträge 7,5-mal langsamer.

Abbildung 4: Eine Gegenüberstellung der Performance von »std::map« im Vergleich zu »std::unordered_map«.

Ausblick

Performance ist nicht alles. Der typische Fehler beim Umgang mit Containern aus der Standard Template Library besteht darin, einen Zugriff außerhalb des Bereichs vorzunehmen. Das provoziert ein undefiniertes Verhalten, sodass keine Aussagen über das Programm mehr zulässig sind. Dank des »at«-Operators für »std::string« sowie der sequenziellen und assoziativen Container lässt sich dieser Fehler jedoch leicht vermeiden. (jcb/jlu)