Kapitel 15. Boost.Unordered

Boost.Unordered stellt die Klassen boost::unordered_set, boost::unordered_multiset, boost::unordered_map und boost::unordered_multimap zur Verfügung. Die Klassen sind identisch mit den Hash-Containern, die mit C++11 in die Standardbibliothek aufgenommen wurden. Sie können die Container aus Boost.Unordered ignorieren, wenn Sie in einer C++11-Entwicklungsumgebung arbeiten.

#include <boost/unordered_set.hpp>
#include <string>
#include <iostream>

int main()
{
  typedef boost::unordered_set<std::string> unordered_set;
  unordered_set set;

  set.emplace("cat");
  set.emplace("shark");
  set.emplace("spider");

  for (const std::string &s : set)
    std::cout << s << '\n';

  std::cout << set.size() << '\n';
  std::cout << set.max_size() << '\n';

  std::cout << std::boolalpha << (set.find("cat") != set.end()) << '\n';
  std::cout << set.count("shark") << '\n';
}

boost::unordered_set könnte im Beispiel 15.1 durch std::unordered_set ersetzt werden. boost::unordered_set unterscheidet sich nicht von std::unordered_set.

#include <boost/unordered_map.hpp>
#include <string>
#include <iostream>

int main()
{
  typedef boost::unordered_map<std::string, int> unordered_map;
  unordered_map map;

  map.emplace("cat", 4);
  map.emplace("shark", 0);
  map.emplace("spider", 8);

  for (const auto &p : map)
    std::cout << p.first << ";" << p.second << '\n';

  std::cout << map.size() << '\n';
  std::cout << map.max_size() << '\n';

  std::cout << std::boolalpha << (map.find("cat") != map.end()) << '\n';
  std::cout << map.count("shark") << '\n';
}

Im Beispiel 15.2 wird boost::unordered_map verwendet, um zusätzlich zum Namen die Anzahl der Beine jedes Tiers zu speichern. Auch in diesem Fall könnte boost::unordered_map durch std::unordered_map ersetzt werden.

#include <boost/unordered_set.hpp>
#include <string>
#include <cstddef>

struct animal
{
  std::string name;
  int legs;
};

bool operator==(const animal &lhs, const animal &rhs)
{
  return lhs.name == rhs.name && lhs.legs == rhs.legs;
}

std::size_t hash_value(const animal &a)
{
  std::size_t seed = 0;
  boost::hash_combine(seed, a.name);
  boost::hash_combine(seed, a.legs);
  return seed;
}

int main()
{
  typedef boost::unordered_set<animal> unordered_set;
  unordered_set animals;

  animals.insert({"cat", 4});
  animals.insert({"shark", 0});
  animals.insert({"spider", 8});
}

Im Beispiel 15.3 sollen Elemente vom Typ animal in einem Container vom Typ boost::unordered_set gespeichert werden. Weil die Hashfunktion von boost::unordered_set die Klasse animal nicht kennt, können keine Hashwerte für Elemente dieses Typs automatisch errechnet werden. Deswegen muss eine Hashfunktion definiert werden – andernfalls würde der Code nicht kompilieren.

Der Name der Hashfunktion, die definiert werden muss, lautet hash_value(). Sie muss als einzigen Parameter ein Objekt des Typs erwarten, von dem ein Hashwert gebildet werden soll. Der Typ des Rückgabewerts von hash_value() muss std::size_t sein.

Die Funktion hash_value() wird automatisch aufgerufen, wenn der Hashwert für ein Objekt errechnet werden soll. Diese Funktion ist für verschiedene Typen in den Boost-Bibliotheken definiert – unter anderem für std::string. Für benutzerdefinierte Typen wie animal muss sie vom Entwickler definiert werden.

Die Definition von hash_value() ist üblicherweise sehr einfach: Der Hashwert wird gebildet, indem nacheinander auf die verschiedenen Bestandteile des Objekts zugegriffen wird. Dies geschieht über die Funktion boost::hash_combine(), die aus der Bibliothek Boost.Hash stammt und in der Headerdatei boost/functional/hash.hpp definiert ist. Sie müssen diese Headerdatei nicht einbinden, wenn Sie Boost.Unordered verwenden, da sämtliche Container in dieser Bibliothek zum Errechnen von Hashwerten auf Boost.Hash zugreifen.

Neben der Definition der Funktion hash_value() muss es außerdem möglich sein, zwei Objekte mit == zu vergleichen. Deswegen ist für die Klasse animal im Beispiel 15.3 der Operator operator== überladen.

Die Hash-Container der C++11-Standardbibliothek verwenden eine Hashfunktion aus der Headerdatei functional. Die Hash-Container aus Boost.Unordered erwarten die Hashfunktion hash_value(). Ob Sie innerhalb von hash_value() auf Boost.Hash zugreifen, spielt keine Rolle. Boost.Hash bietet sich an, da Funktionen wie boost::hash_combine() es einfacher machen, einen Hashwert schrittweise basierend auf mehreren Eigenschaften zu errechnen. Hierbei handelt es sich jedoch um ein Implementationsdetail von hash_value(). Abgesehen von den unterschiedlichen Hashfunktionen, die erwartet werden, sind die Hash-Container in Boost.Unordered und der Standardbibliothek grundsätzlich gleich.