Kapitel 12. Boost.MultiIndex

Die Bibliothek Boost.MultiIndex ermöglicht es, Container zu definieren, die beliebig viele Schnittstellen unterstützen. Während zum Beispiel std::vector die für Vektoren typische Schnittstelle anbietet, über die per Index ein direkter Zugriff auf Elemente möglich ist, und während zum Beispiel std::set eine Schnittstelle anbietet, über die Elemente sortiert dargestellt werden, kann mit Boost.MultiIndex ein Container definiert werden, der beide Schnittstellen unterstützt. So könnte auf Elemente in diesem Container sowohl direkt per Index als auch über eine sortierte Sichtweise zugegriffen werden.

Boost.MultiIndex bietet sich an, wenn auf Elemente unterschiedlich zugegriffen werden muss und sie deswegen in mehreren Containern gespeichert werden müssten. Anstatt Elemente sowohl in einem Vektor als auch in einem Set zu speichern und die Container laufend zu synchronisieren, kann ein Container mit Boost.MultiIndex definiert werden, der sowohl die von Vektoren als auch die von Sets bekannten Schnittstellen anbietet.

Boost.MultiIndex ist auch von Vorteil, wenn nicht nur mehrere Schnittstellen benötigt werden, sondern der Zugriff auf Elemente von unterschiedlichen Eigenschaften der Elemente abhängt. Sehen Sie sich dazu Beispiel 12.1 an, in dem Tiere sowohl über ihren Namen als auch über die Anzahl der Beine nachgeschlagen werden können. Ohne Boost.MultiIndex müssten zwei Hash-Container verwendet werden, wobei der eine Hash-Container Tiere nach Namen und der andere Hash-Container Tiere nach Anzahl der Beine speichern müsste.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>

using namespace boost::multi_index;

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

typedef multi_index_container<
  animal,
  indexed_by<
    hashed_non_unique<
      member<
        animal, std::string, &animal::name
      >
    >,
    hashed_non_unique<
      member<
        animal, int, &animal::legs
      >
    >
  >
> animal_multi;

int main()
{
  animal_multi animals;

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

  std::cout << animals.count("cat") << '\n';

  const animal_multi::nth_index<1>::type &legs_index = animals.get<1>();
  std::cout << legs_index.count(8) << '\n';
}

Wenn Sie Boost.MultiIndex verwenden, ist der erste Schritt, einen neuen Container zu definieren. So müssen Sie entscheiden, welche Schnittstellen Ihr neuer Container unterstützen soll und auf welche Eigenschaften von Elementen Schnittstellen zugreifen sollen.

Eine Klasse, die bei jeder Containerdefinition benötigt wird, ist boost::multi_index::multi_index_container. Sie ist in der Headerdatei boost/multi_index_container.hpp definiert. Bei boost::multi_index::multi_index_container handelt es sich um ein Template, dem mindestens zwei Parameter übergeben werden müssen. Der erste Parameter ist der Typ, der im Container gespeichert werden soll – im Beispiel 12.1 animal. Der zweite Parameter wird verwendet, um die verschiedenen Indizes festzulegen, die vom Container zur Verfügung gestellt werden sollen.

Der entscheidende Vorteil, den Container auf Basis von Boost.MultiIndex bieten, ist, dass auf Elemente über unterschiedliche Schnittstellen zugegriffen werden kann. Bei einer Containerdefinition muss angegeben werden, wie viele und welche Schnittstellen ein Container anbieten soll. Da für Beispiel 12.1 ein Container benötigt wird, mit dem sowohl über den Namen als auch über die Anzahl der Beine nach Tieren gesucht werden kann, werden zwei Schnittstellen definiert. Boost.MultiIndex nennt diese Schnittstellen Indizes – daher der Name dieser Bibliothek.

Die Definition von Schnittstellen erfolgt über die Klasse boost::multi_index::indexed_by. Auch bei dieser Klasse handelt es sich um ein Template, dem mehrere Parameter übergeben werden können, wobei jeder Parameter eine Schnittstelle definiert. Im Beispiel 12.1 werden zwei Schnittstellen vom Typ boost::multi_index::hashed_non_unique definiert, deren Definition sich in der Headerdatei boost/multi_index/hashed_index.hpp befindet. Diese Schnittstelle wird verwendet, wenn sich ein Container ähnlich wie ein std::unordered_set verhalten soll und Elemente über einen Hashwert gefunden werden sollen.

Auch die Klasse boost::multi_index::hashed_non_unique ist ein Template. Sie erwartet als einzigen Parameter eine Klasse, die sie zur Berechnung von Hashwerten verwenden kann. Da die beiden Schnittstellen des Containers den Zugriff auf Tiere über Namen und Beine ermöglichen sollen, soll die eine Schnittstelle Hashwerte für Namen und die andere Schnittstelle Hashwerte für Beine errechnen.

Boost.MultiIndex bietet für den Zugriff auf eine Eigenschaft eine Hilfsklasse boost::multi_index::member an. Sie ist in der Headerdatei boost/multi_index/member.hpp definiert. Da es sich auch bei dieser Klasse um ein Template handelt, müssen so wie im Beispiel 12.1 mehrere Parameter angegeben werden, damit boost::multi_index::member weiß, auf welche Eigenschaft von animal zugegriffen werden soll und welchen Typ die Eigenschaft hat.

Auch wenn die Klassendefinition von animal_multi auf den ersten Blick kompliziert aussieht: Die Klasse ähnelt einer Map. Der Name und die Anzahl der Beine eines Tiers können als Schlüssel/Wert-Paar betrachtet werden. Ein Vorteil des Containers animal_multi gegenüber einer Map wie std::unordered_map ist es, dass sowohl der Name als auch die Anzahl der Beine der Schlüssel sein kann, um nach einem Tier zu suchen. animal_multi unterstützt zwei Schnittstellen – und je nach Schnittstelle findet der Aufruf über den Namen oder über die Beine statt. Was der Schlüssel und was der Wert ist, hängt von der Schnittstelle ab, über die auf den Container zugegriffen wird.

Wenn Sie auf einen MultiIndex-Container zugreifen, müssen Sie sich entscheiden, welche Schnittstelle Sie für den Zugriff verwenden möchten. Wenn wie im Beispiel 12.1 per insert() oder count() direkt auf animals zugegriffen wird, wird automatisch die erste Schnittstelle verwendet – in diesem Fall also der Hash-Container für die Eigenschaft name. Möchten Sie über eine andere als die erste Schnittstelle auf einen MultiIndex-Container zugreifen, müssen Sie sie explizit auswählen.

Schnittstellen sind durchnummeriert, wobei die erste Schnittstelle den Index 0 besitzt. Wenn Sie wie im Beispiel 12.1 auf die zweite Schnittstelle zugreifen möchten, können Sie dies über get() machen. Sie müssen dieser Methode, die ein Template ist, den Index der gewünschten Schnittstelle als Template-Parameter übergeben.

Der Rückgabewert von get() sieht kompliziert aus: Sie greifen auf eine Klasse im MultiIndex-Container zu, die nth_index heißt. Weil es sich hier wiederum um ein Template handelt, müssen Sie den Index der Schnittstelle, die Sie verwenden wollen, als Template-Parameter angeben. Dieser Index muss der gleiche sein wie der, den Sie als Template-Parameter an get() übergeben haben. Wenn Sie dann auf die Typdefinition type der Klasse nth_index zugreifen, haben Sie es geschafft. type repräsentiert den Typ der entsprechenden Schnittstelle. In den nachfolgenden Beispielen wird das Schlüsselwort auto verwendet, um den Code lesbarer zu machen.

Sie müssen zwar nicht wissen, wie die Typdefinition einer Schnittstelle exakt aussieht, weil sie über nth_index und type automatisch abgeleitet werden kann. Sie sollten aber wissen, auf welche Art von Schnittstelle Sie zugreifen. Das sollte sich aber von selbst verstehen: Da Sie den Index der Schnittstelle an get() und nth_index übergeben und in der Containerdefinition nachsehen können, in welcher Reihenfolge Schnittstellen definiert sind, wissen Sie, welche Art von Schnittstelle Ihnen zur Verfügung steht. So gilt für obiges Beispiel: legs_index ist ebenfalls eine Hash-Schnittstelle, nur dass in diesem Fall nicht über den Namen, sondern über die Anzahl der Beine nach Tieren gesucht wird.

Wenn in einem MultiIndex-Container wie im Beispiel 12.1 Daten wie Name und Beine je nach Schnittstelle Schlüssel sein können, dürfen sie nicht beliebig geändert werden können. Wenn zum Beispiel nach einem Tier mit einem bestimmten Namen gesucht wird und die Anzahl der Beine des Tiers geändert werden könnte, wüsste die andere Schnittstelle, die die Anzahl der Beine als Schlüssel verwendet, nicht, dass einer der Schlüssel geändert wurde und ein neuer Hashwert gebildet werden muss.

So wie es nicht möglich ist, den Schlüssel in einem Container vom Typ std::unordered_map zu ändern, können Daten in einem MultiIndex-Container nicht geändert werden. Grundsätzlich sind alle Daten, die in einem MultiIndex-Container gespeichert wurden, konstant. Das schließt Eigenschaften ein, die von keiner Schnittstelle verwendet werden. Selbst wenn es keine Schnittstelle geben würde, die auf legs zugreift, könnte legs nicht verändert werden.

Damit Elemente nicht gelöscht und in geänderter Form wieder gespeichert werden müssen, bietet Boost.MultiIndex Methoden an, über die Elemente im Container direkt geändert werden können. Da diese Methoden für den MultiIndex-Container aufgerufen werden und Elemente im MultiIndex-Container nicht über einen direkten Zugriff auf diese geändert werden, ist diese Art der Datenänderung sicher. So werden in diesem Fall sämtliche Schnittstellen benachrichtigt und können zum Beispiel Hashwerte neu berechnen.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>

using namespace boost::multi_index;

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

typedef multi_index_container<
  animal,
  indexed_by<
    hashed_non_unique<
      member<
        animal, std::string, &animal::name
      >
    >,
    hashed_non_unique<
      member<
        animal, int, &animal::legs
      >
    >
  >
> animal_multi;

int main()
{
  animal_multi animals;

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

  auto &legs_index = animals.get<1>();
  auto it = legs_index.find(4);
  legs_index.modify(it, [](animal &a){ a.name = "dog"; });

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

Die Methode modify() wird von allen Schnittstellen in Boost.MultiIndex unterstützt. Sie kann immer direkt für einen MultiIndex-Container aufgerufen werden. Ihr muss als erster Parameter ein Iterator auf ein Element im Container übergeben werden, das geändert werden soll. Der zweite Parameter ist eine Funktion oder ein Funktionsobjekt, dem beim Aufruf als einziger Parameter ein Element aus dem MultiIndex-Container übergeben wird. In dieser Funktion kann das Element beliebig geändert werden.

Bisher haben Sie lediglich eine einzige Schnittstelle kennengelernt: Mit boost::multi_index::hashed_non_unique werden Elemente über einen Hashwert nachgeschlagen, wobei die Hashwerte nicht eindeutig sein müssen. Möchten Sie verhindern, dass mehrere Elemente mit dem gleichen Hashwert im Container gespeichert werden, können Sie boost::multi_index::hashed_unique verwenden.

Beachten Sie, dass Container Elemente nicht speichern können, wenn nicht alle Anforderungen aller Schnittstellen des Containers erfüllt sind. Wenn eine Schnittstelle ein Element nicht akzeptiert, hilft es nicht, wenn andere Schnittstellen dieses akzeptieren.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>

using namespace boost::multi_index;

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

typedef multi_index_container<
  animal,
  indexed_by<
    hashed_non_unique<
      member<
        animal, std::string, &animal::name
      >
    >,
    hashed_unique<
      member<
        animal, int, &animal::legs
      >
    >
  >
> animal_multi;

int main()
{
  animal_multi animals;

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

  auto &legs_index = animals.get<1>();
  std::cout << legs_index.count(4) << '\n';
}

Der MultiIndex-Container im Beispiel 12.3 verwendet als zweite Schnittstelle die Klasse boost::multi_index::hashed_unique. Das bedeutet, dass keine zwei Tiere die gleiche Anzahl an Beinen haben dürfen. Dann würde für beide Tiere der gleiche Hashwert errechnet werden – und der muss, was die zweite Schnittstelle betrifft, einmalig sein.

Weil im Beispiel versucht wird, einen Hund zu speichern, der wie die Katze vier Beine hat, werden die Anforderungen der zweiten Schnittstelle verletzt. Der Hund kann dem MultiIndex-Container nicht hinzugefügt werden und wird ignoriert. Wenn Sie das Beispiel ausführen, wird 1 ausgegeben, da der Container genau ein Tier mit vier Beinen speichert – die Katze.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/member.hpp>
#include <string>
#include <iostream>

using namespace boost::multi_index;

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

typedef multi_index_container<
  animal,
  indexed_by<
    sequenced<>,
    ordered_non_unique<
      member<
        animal, int, &animal::legs
      >
    >,
    random_access<>
  >
> animal_multi;

int main()
{
  animal_multi animals;

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

  auto &legs_index = animals.get<1>();
  auto it = legs_index.lower_bound(4);
  auto end = legs_index.upper_bound(8);
  for (; it != end; ++it)
    std::cout << it->name << '\n';

  const auto &rand_index = animals.get<2>();
  std::cout << rand_index[0].name << '\n';
}

Beispiel 12.4 stellt Ihnen die anderen drei Schnittstellen vor, die Boost.MultiIndex anbietet: boost::multi_index::sequenced, boost::multi_index::ordered_non_unique und boost::multi_index::random_access.

Über die Schnittstelle boost::multi_index::sequenced können Sie einen MultiIndex-Container wie eine Liste behandeln – also ähnlich wie std::list. Aus Sicht von boost::multi_index::sequenced werden Elemente genau in der Reihenfolge gespeichert, in der sie dem Container hinzugefügt werden.

Wenn Sie die Schnittstelle boost::multi_index::ordered_non_unique verwenden, werden Elemente automatisch sortiert. Für diese Schnittstelle müssen Sie bei der Definition des Containers angeben, wie die Sortierung erfolgen soll. So wird im Beispiel 12.4 angegeben, dass Objekte vom Typ animal über die Anzahl der Beine sortiert werden sollen. Dazu wird auf die bereits bekannte Hilfsklasse boost::multi_index::member zugegriffen.

Da boost::multi_index::ordered_non_unique Elemente sortiert, bietet die Schnittstelle spezielle Methoden an, um bestimmte Positionen innerhalb der sortierten Elemente zu finden. So werden im Beispiel 12.4 über lower_bound() und upper_bound() Tiere gesucht, die mindestens vier und höchstens acht Beine haben. Diese Methoden werden von keiner anderen Schnittstelle angeboten, da sie eine Sortierung voraussetzen.

Die dritte Schnittstelle, die im Beispiel 12.4 zur Containerdefinition eingesetzt wird, ist boost::multi_index::random_access. Über diese Schnittstelle kann ein MultiIndex-Container wie ein Vektor vom Typ std::vector behandelt werden. Die beiden prominentesten Methoden sind operator[] und at().

Beachten Sie, dass boost::multi_index::random_access die Schnittstelle boost::multi_index::sequenced einschließt. Wenn Sie zur Containerdefinition boost::multi_index::random_access verwenden, ist es wenig sinnvoll, zusätzlich boost::multi_index::sequenced einzusetzen, da sämtliche Methoden dieser Schnittstelle auch über boost::multi_index::random_access zur Verfügung stehen.

Nachdem Sie die vier Schnittstellen, die Boost.MultiIndex anbietet, kennengelernt haben, soll im Folgenden ein Blick auf Schlüsselentnehmer geworfen werden. Einen Schlüsselentnehmer haben Sie bereits kennengelernt: boost::multi_index::member aus der Headerdatei boost/multi_index/member.hpp. Diese Hilfsklasse wird Schlüsselentnehmer genannt, da mit ihr angegeben werden kann, welche Eigenschaft einer Klasse als Schlüssel in einer Schnittstelle verwendet werden soll.

Im Beispiel 12.5 lernen Sie zwei weitere Schlüsselentnehmer kennen.

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <string>
#include <utility>
#include <iostream>

using namespace boost::multi_index;

class animal
{
public:
  animal(std::string name, int legs) : name_{std::move(name)},
    legs_(legs) {}
  bool operator<(const animal &a) const { return legs_ < a.legs_; }
  const std::string &name() const { return name_; }
private:
  std::string name_;
  int legs_;
};

typedef multi_index_container<
  animal,
  indexed_by<
    ordered_unique<
      identity<animal>
    >,
    hashed_unique<
      const_mem_fun<
        animal, const std::string&, &animal::name
      >
    >
  >
> animal_multi;

int main()
{
  animal_multi animals;

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

  std::cout << animals.begin()->name() << '\n';

  const auto &name_index = animals.get<1>();
  std::cout << name_index.count("shark") << '\n';
}

Der Schlüsselentnehmer boost::multi_index::identity, definiert in der Headerdatei boost/multi_index/identity.hpp, wird verwendet, um den Typ, der im MultiIndex-Container gespeichert wird, selbst als Schlüssel zu verwenden. Für Beispiel 12.5 bedeutet dies, dass die Klasse animal sortiert werden können muss, weil der Typ selbst als Schlüssel für die Schnittstelle boost::multi_index::ordered_unique dient. Das ist der Grund, warum der Operator operator< für die Klasse animal definiert ist.

In der Headerdatei boost/multi_index/mem_fun.hpp sind die beiden Schlüsselentnehmer boost::multi_index::const_mem_fun und boost::multi_index::mem_fun definiert, mit denen der Rückgabewert einer Methode als Schlüssel verwendet werden kann. Im Beispiel 12.5 ist dies der Rückgabewert von name(). boost::multi_index::const_mem_fun wird für konstante Methoden verwendet, boost::multi_index::mem_fun für alle anderen Methoden.

Boost.MultiIndex bietet zwei weitere Schlüsselentnehmer namens boost::multi_index::global_fun und boost::multi_index::composite_key an. Während der erstgenannte Schlüsselentnehmer für freistehende Funktionen und statische Methoden verwendet werden kann, ermöglicht boost::multi_index::composite_key, einen Schlüsselentnehmer bestehend aus mehreren anderen Schlüsselentnehmern zu konstruieren.

#include <string>
#include <vector>
#include <iostream>

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

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

    const animal *find_by_name(const std::string &name) const
    {
        // TODO: Implement this member function.
        return nullptr;
    }

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

    std::vector<animal> find_by_tail(bool has_tail) const
    {
        // TODO: Implement this member function.
        return {};
    }
};

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

    const animal *a = animals.find_by_name("cat");
    if (a)
        std::cout << "cat has " << a->legs << " legs\n";

    auto animals_with_6_to_8_legs = animals.find_by_legs(6, 9);
    for (auto a : animals_with_6_to_8_legs)
        std::cout << a.name << " has " << a.legs << " legs\n";

    auto animals_without_tail = animals.find_by_tail(false);
    for (auto a : animals_without_tail)
        std::cout << a.name << " has no tail\n";
}