Kapitel 13. Boost.Bimap

Die Bibliothek Boost.Bimap basiert auf Boost.MultiIndex und bietet einen Container an, den Sie sofort verwenden können. Es handelt sich hierbei um einen Container ähnlich wie std::map, wobei nicht einseitig nach Schlüsseln, sondern auch nach Werten gesucht werden kann. Auf die Map kann also von beiden Seiten zugegriffen werden. Was jeweils Schlüssel und Wert ist, hängt davon ab, von welcher Seite der Zugriff erfolgt.

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

int main()
{
  typedef boost::bimap<std::string, int> bimap;
  bimap animals;

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

  std::cout << animals.left.count("cat") << '\n';
  std::cout << animals.right.count(8) << '\n';
}

Der Container boost::bimap, definiert in der Headerdatei boost/bimap.hpp, bietet zwei Eigenschaften left und right an. Über diese kann auf die beiden Container vom Typ std::map zugegriffen werden, die boost::bimap in sich vereint. Während im Beispiel 13.1 über left auf den Container zugegriffen wird, der Strings als Schlüssel verwendet, wird über right auf den Container zugegriffen, der Zahlen als Schlüssel verwendet.

Neben dem Zugriff auf Elemente sowohl über einen linken als auch rechten Container gestattet boost::bimap, Schlüssel/Wert-Paare als Relationen zu betrachten. Sehen Sie sich dazu Beispiel 13.2 an.

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

int main()
{
  typedef boost::bimap<std::string, int> bimap;
  bimap animals;

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

  for (auto it = animals.begin(); it != animals.end(); ++it)
    std::cout << it->left << " has " << it->right << " legs\n";
}

Es ist nicht notwendig, jeweils über left oder right auf Elemente im Container zuzugreifen. Sie können auch direkt über Elemente iterieren und über den Iterator auf die linke oder rechte Seite des jeweiligen Elements zugreifen.

Während es für std::map einen Container namens std::multimap gibt, der mehrere Elemente mit gleichem Schlüssel speichern kann, gibt es keinen entsprechenden Container neben boost::bimap. Das bedeutet jedoch nicht, dass es nicht möglich ist, Elemente mit gleichem Schlüssel in einem Container vom Typ boost::bimap zu speichern.

Die beiden Template-Parameter, die boost::bimap übergeben werden, geben genaugenommen nicht Typen an, die gespeichert werden sollen, sondern Containertypen, die für left und right verwendet werden sollen. Wird wie in den bisherigen Beispielen kein Containertyp angegeben, sondern lediglich std::string und int, wird automatisch der Containertyp boost::bimaps::set_of verwendet. Und dieser erlaubt ähnlich wie std::map nur Elemente mit eindeutigem Schlüssel.

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

int main()
{
  typedef boost::bimap<boost::bimaps::set_of<std::string>,
    boost::bimaps::set_of<int>> bimap;
  bimap animals;

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

  std::cout << animals.left.count("spider") << '\n';
  std::cout << animals.right.count(8) << '\n';
}

Im Beispiel 13.3 wird boost::bimaps::set_of explizit verwendet.

Neben der Klasse boost::bimaps::set_of, die Elemente wie std::map sortiert und darauf achtet, dass Schlüssel eindeutig sind, stehen andere Containertypen zur Verfügung, mit denen boost::bimap angepasst werden kann.

#include <boost/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <string>
#include <iostream>

int main()
{
  typedef boost::bimap<boost::bimaps::set_of<std::string>,
    boost::bimaps::multiset_of<int>> bimap;
  bimap animals;

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

  std::cout << animals.left.count("dog") << '\n';
  std::cout << animals.right.count(4) << '\n';
}

Im Beispiel 13.4 wird der Containertyp boost::bimaps::multiset_of verwendet, der in der Headerdatei boost/bimap/multiset_of.hpp definiert ist. Er funktioniert ähnlich wie boost::bimaps::set_of, nur dass Schlüssel nicht mehr eindeutig sein müssen. Somit gibt Beispiel 13.4 für die Anzahl der vierbeinigen Tiere 2 aus.

Beachten Sie, dass Sie für andere Containertypen als boost::bimaps::set_of die entsprechenden Headerdateien einbinden müssen. Weil boost::bimaps::set_of standardmäßig in Containern vom Typ boost::bimap verwendet wird, müssen Sie die entsprechende Headerdatei boost/bimap/set_of.hpp nicht einbinden.

Neben den bisher kennengelernten Containertypen bietet Boost.Bimap die Klassen boost::bimaps::unordered_set_of, boost::bimaps::unordered_multiset_of, boost::bimaps::list_of, boost::bimaps::vector_of und boost::bimaps::unconstrainted_set_of an. Bis auf die Klasse boost::bimaps::unconstrainted_set_of, die weiterer Erläuterungen bedarf, funktionieren alle genannten Containertypen wie die aus der Standardbibliothek bekannten Klassen.

#include <boost/bimap.hpp>
#include <boost/bimap/unconstrained_set_of.hpp>
#include <boost/bimap/support/lambda.hpp>
#include <string>
#include <iostream>

int main()
{
  typedef boost::bimap<std::string,
    boost::bimaps::unconstrained_set_of<int>> bimap;
  bimap animals;

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

  auto it = animals.left.find("cat");
  animals.left.modify_key(it, boost::bimaps::_key = "dog");

  std::cout << it->first << '\n';
}

Mit boost::bimaps::unconstrainted_set_of kann wie im Beispiel 13.5 eine Seite von boost::bimap deaktiviert werden. Es ist dann nicht mehr möglich, über right auf die rechte Seite des Containers zuzugreifen und Tiere nach der Anzahl ihrer Beine zu durchsuchen. In diesem Fall verhält sich der Container vom Typ boost::bimap wie std::map.

Warum es trotzdem sinnvoll sein kann, statt std::map boost::bimap zu verwenden, sehen Sie anhand des Beispiels. Da Boost.Bimap auf Boost.MultiIndex basiert, stehen aus Boost.MultiIndex bekannte Methoden zur Verfügung. So wird im Beispiel 13.5 über modify_key() ein Schlüssel geändert – etwas, was mit std::map nicht möglich ist.

Beachten Sie außerdem, wie der Schlüssel im Detail geändert wird: Über boost::bimaps::_key, das in der Headerdatei boost/bimap/support/lambda.hpp definiert ist, wird auf den aktuellen Schlüssel zugegriffen und ihm ein neuer Wert zugewiesen. Es handelt sich hierbei um eine Lambda-Funktion, die ohne C++11 und andere Boost-Bibliotheken auskommt.

Neben boost::bimaps::_key ist in der Headerdatei boost/bimap/support/lambda.hpp auch boost::bimaps::_data definiert. Beim Aufruf der Methode modify_data() können Sie entsprechend einen Wert in einem Container vom Typ boost::bimap ändern.

#include <boost/optional.hpp>
#include <string>
#include <vector>
#include <iostream>

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

    animal(std::string n, int l) : name(n), legs(l) {}
};

class animals_container
{
public:
    void add(animal a)
    {
        // TODO: Implement this member function.
    }

    boost::optional<animal> find_by_name(const std::string &name) const
    {
        // TODO: Implement this member function.
        return {};
    }

    std::vector<animal> find_by_legs(int from, int to) const
    {
        // TODO: Implement this member function.
        return {};
    }
};

int main()
{
    animals_container animals;
    animals.add({ "cat", 4 });
    animals.add({ "ant", 6 });
    animals.add({ "spider", 8 });
    animals.add({ "shark", 0 });

    auto shark = animals.find_by_name("shark");
    if (shark)
        std::cout << "shark has " << shark->legs << " legs\n";

    auto animals_with_4_to_6_legs = animals.find_by_legs(4, 7);
    for (auto animal : animals_with_4_to_6_legs)
        std::cout << animal.name << " has " << animal.legs << " legs\n";
}