Die Boost C++ Bibliotheken
Bei Boost.Instrusive handelt es sich um eine Bibliothek, die sich besonders für den Einsatz in Programmen eignet, die eine hohe Performance erzielen müssen. Die Bibliothek stellt Werkzeuge zur Verfügung, um intrusive Container zu erstellen. Diese Container ersetzen die bekannten Container der Standardbibliothek. Sie haben den Nachteil, dass sie nicht ganz so einfach einzusetzen sind wie beispielsweise std::list oder std::set. Dafür bieten sie diese Vorteile:
Intrusive Container reservieren keinen dynamischen Speicher. Ein Aufruf von push_back() führt nicht zu einer dynamischen Speicherallokation mit new. Das ist ein Grund, warum der Einsatz intrusiver Container zu einer höheren Performance führen kann.
Intrusive Container speichern keine Kopien von Objekten, sondern Originalobjekte. Dies ergibt sich bereits daraus, dass keine Speicherallokation stattfindet. Daraus resultiert aber ein weiterer Vorteil: Methoden wie push_back() werfen keine Ausnahmen. So kann es weder zu einer fehlgeschlagenen Speicherallokation kommen noch zu Problemen beim Kopieren von Objekten – weder das eine noch das andere geschieht bei intrusiven Containern.
Die Vorteile werden durch einen etwas komplizierteren Code erkauft, der die notwendigen Vorbedingungen schafft, damit Objekte bestimmter Typen in intrusiven Containern gespeichert werden können. So ist es nicht möglich, Objekte beliebiger Typen in intrusiven Containern zu speichern. Sie können zum Beispiel keine Strings vom Typ std::string in einem intrusiven Container ablegen. Hier müssen Sie auf die bekannten Container aus der Standardbibliothek zugreifen.
Sehen Sie sich Beispiel 18.1 an, in dem eine Klasse animal so präpariert wird, dass Objekte dieses Typs in einer intrusiven Liste gespeichert werden können.
boost::intrusive::list in Aktion#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal : public list_base_hook<>
{
std::string name;
int legs;
animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
animal a1{"cat", 4};
animal a2{"shark", 0};
animal a3{"spider", 8};
typedef list<animal> animal_list;
animal_list animals;
animals.push_back(a1);
animals.push_back(a2);
animals.push_back(a3);
a1.name = "dog";
for (const animal &a : animals)
std::cout << a.name << '\n';
}Eine Liste ist so definiert, dass man von einem Element der Liste auf das nächste zugreifen kann. Dies wird üblicherweise mit einem Zeiger implementiert. Wenn eine intrusive Liste Objekte vom Typ animal speichern können soll, ohne dynamisch Speicher zu reservieren, muss es irgendwo einen Zeiger geben, um sich später in der Liste von einem Element zum nächsten zu hangeln.
Um Objekte vom Typ animal in einer intrusiven Liste speichern zu können, muss die Klasse selbst Variablen bereitstellen, die es der intrusiven Liste ermöglichen, Elemente zu verketten. Boost.Intrusive stellt hierzu Hooks zur Verfügung – Klassen, von denen abgeleitet werden kann, um die notwendigen Variablen zu erben und sie so bereitzustellen. So muss animal von der Klasse boost::intrusive::list_base_hook abgeleitet werden, damit Objekte vom Typ animal in einer intrusiven Liste verwaltet werden können. Dank dieser Vorgehensweise ist es nicht notwendig zu wissen, welche Details die intrusive Liste im Einzelnen benötigt. Es kann aber davon ausgegangen werden, dass boost::intrusive::list_base_hook mindestens zwei Zeiger zur Verfügung stellt, da boost::intrusive::list eine doppelt verkettete Liste ist. Dank der Elternklasse boost::intrusive::list_base_hook stellt animal diese beiden Zeiger zur Verfügung, die notwendig sind, um Elemente dieses Typs zu verketten.
Beachten Sie, dass es sich bei boost::intrusive::list_base_hook um ein Template handelt. Da das Template Standardwerte besitzt, müssen Sie keine Werte bei der Instanziierung angeben.
Boost.Intrusive stellt die Klasse boost::intrusive::list zur Verfügung, um eine intrusive Liste zu erstellen. Die Klasse ist in der Headerdatei boost/intrusive/list.hpp definiert und wird grundsätzlich genauso verwendet wie std::list. So können Elemente nicht nur mit push_back() der Liste hinzugefügt werden. Es kann auch über Elemente in der Liste iteriert werden.
Es ist wichtig zu verstehen, dass intrusive Container keine Kopien, sondern Originalobjekte speichern. So gibt Beispiel 18.1 die Namen dog, shark und spider aus – nicht cat. Es ist das Objekt a1 selbst, das in die Liste eingebunden ist. Deswegen ist die Namensänderung sichtbar, wenn über die Elemente in der Liste iteriert wird und die Namen ausgegeben werden.
Da intrusive Container keine Kopien speichern, müssen Sie darauf achten, dass Sie Objekte explizit aus einem intrusiven Container entfernen, wenn Sie sie zerstören.
#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal : public list_base_hook<>
{
std::string name;
int legs;
animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
animal a1{"cat", 4};
animal a2{"shark", 0};
animal *a3 = new animal{"spider", 8};
typedef list<animal> animal_list;
animal_list animals;
animals.push_back(a1);
animals.push_back(a2);
animals.push_back(*a3);
animals.pop_back();
delete a3;
for (const animal &a : animals)
std::cout << a.name << '\n';
}Im Beispiel 18.2 wird ein Objekt vom Typ animal mit new erstellt und der Liste animals hinzugefügt. Wenn Sie dieses Objekt mit delete zerstören wollen, weil es nicht mehr benötigt wird, müssen Sie es aus der Liste entfernen. Achten Sie darauf, dass Sie das Objekt zuerst aus der Liste entfernen, bevor Sie es zerstören – die Reihenfolge ist wichtig. Andernfalls laufen Sie Gefahr, dass im intrusiven Container über Zeiger auf ungültige Speicherbereiche zugegriffen wird, in denen sich kein Objekt vom Typ animal mehr befindet.
Da intrusive Container Speicher weder reservieren noch freigeben, gilt natürlich auch, dass Objekte, die in einem intrusiven Container verwaltet werden, weiter existieren, wenn der intrusive Container zerstört wird.
Weil bei intrusiven Containern das Entfernen von Elementen nicht automatisch mit dem Zerstören dieser verbunden ist, werden neben den von Containern aus der Standardbibliothek bekannten Methoden weitere angeboten. Zu diesen gehört zum Beispiel pop_back_and_dispose().
pop_back_and_dispose()#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal : public list_base_hook<>
{
std::string name;
int legs;
animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
animal a1{"cat", 4};
animal a2{"shark", 0};
animal *a3 = new animal{"spider", 8};
typedef list<animal> animal_list;
animal_list animals;
animals.push_back(a1);
animals.push_back(a2);
animals.push_back(*a3);
animals.pop_back_and_dispose([](animal *a){ delete a; });
for (const animal &a : animals)
std::cout << a.name << '\n';
}pop_back_and_dispose() entfernt ein Element aus der Liste und zerstört es. Da intrusive Container nicht wissen können, wie ein Element der Liste zerstört werden muss, muss eine Funktion oder ein Funktionsobjekt als Parameter an pop_back_and_dispose() übergeben werden. Die Methode ruft die Funktion oder das Funktionsobjekt auf und übergibt einen Zeiger auf das Objekt, das nun nicht mehr Teil der Liste ist und zerstört werden kann. Im Beispiel 18.3 wird eine Lambda-Funktion übergeben, die lediglich delete ausführt.
Beachten Sie, dass im Beispiel 18.3 ausschließlich das dritte Element in animals wie gezeigt mit pop_back_and_dispose() entfernt werden darf. Die anderen beiden Elemente in der Liste sind nicht mit new erstellt worden und dürfen demnach nicht mit delete zerstört werden.
Boost.Intrusive bietet eine weitere Möglichkeit an, das Entfernen und Zerstören von Elementen zu verbinden.
#include <boost/intrusive/list.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
typedef link_mode<auto_unlink> mode;
struct animal : public list_base_hook<mode>
{
std::string name;
int legs;
animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
};
int main()
{
animal a1{"cat", 4};
animal a2{"shark", 0};
animal *a3 = new animal{"spider", 8};
typedef constant_time_size<false> constant_time_size;
typedef list<animal, constant_time_size> animal_list;
animal_list animals;
animals.push_back(a1);
animals.push_back(a2);
animals.push_back(*a3);
delete a3;
for (const animal &a : animals)
std::cout << a.name << '\n';
}Hook-Klassen kann ein Parameter für einen Link-Modus übergeben werden. Dazu wird auf die Klasse boost::intrusive::link_mode zugegriffen, die ihrerseits ein Template ist und einen Parameter erwartet. Indem Sie boost::intrusive::auto_unlink übergeben, wird der Auto-Unlink-Modus aktiviert.
Im Auto-Unlink-Modus wird ein Element aus einem intrusiven Container automatisch entfernt, wenn es zerstört wird. So gibt Beispiel 18.4 nur die Namen cat und shark aus.
Der Auto-Unlink-Modus kann nur verwendet werden, wenn die Methode size(), die von allen intrusiven Containern angeboten wird, keine konstante Komplexität besitzt. Standardmäßig besitzt diese Methode eine konstante Komplexität, was bedeutet: Egal, wie viele Elemente sich in einem Container befinden – die Anzahl der Elemente wird von size() immer gleich schnell berechnet. Hierbei handelt es sich um eine weitere Einstellungsmöglichkeit, um die Performance zu optimieren.
Um die Komplexität der Methode size() zu ändern, muss auf die Klasse boost::intrusive::constant_time_size zugegriffen werden. Es handelt sich bei dieser Klasse um ein Template, das lediglich true oder false als Parameter erwartet. Die Klasse boost::intrusive::constant_time_size kann als zweiter Template-Parameter an intrusive Container wie boost::intrusive::list übergeben werden, um die Komplexität der Methode size() einzustellen.
Sie haben soeben zwei neue Konzepte kennengelernt: Intrusive Container besitzen Link-Modi und eine Einstellungsmöglichkeit zur Komplexität von size(). Auch wenn dies den Anschein erweckt, als würde Boost.Intrusive von Konfigurationseinstellungen nur so wimmeln, gibt es nicht viel mehr zu entdecken. Zum Beispiel gibt es insgesamt nur drei Link-Modi, von denen Sie lediglich den Auto-Unlink-Modus explizit kennen müssen – der Standard-Modus, der immer dann verwendet wird, wenn Sie keinen Link-Modus vorgeben, ist in allen anderen Fällen eine gute Wahl.
Des Weiteren gibt es keine Einstellungsmöglichkeiten bezüglich anderer Methoden, die von intrusiven Containern angeboten werden. Es gibt also keine weiteren Klassen neben boost::intrusive::constant_time_size, die Sie kennenlernen müssen.
Im Beispiel 18.5 soll nicht nur ein anderer Hook-Mechanismus vorgestellt werden. Mit boost::intrusive::set wird außerdem ein anderer intrusiver Container verwendet.
boost::intrusive::set als Eigenschaft definiert#include <boost/intrusive/set.hpp>
#include <string>
#include <utility>
#include <iostream>
using namespace boost::intrusive;
struct animal
{
std::string name;
int legs;
set_member_hook<> set_hook;
animal(std::string n, int l) : name{std::move(n)}, legs{l} {}
bool operator<(const animal &a) const { return legs < a.legs; }
};
int main()
{
animal a1{"cat", 4};
animal a2{"shark", 0};
animal a3{"spider", 8};
typedef member_hook<animal, set_member_hook<>, &animal::set_hook> hook;
typedef set<animal, hook> animal_set;
animal_set animals;
animals.insert(a1);
animals.insert(a2);
animals.insert(a3);
for (const animal &a : animals)
std::cout << a.name << '\n';
}Boost.Intrusive bietet grundsätzlich zwei Möglichkeiten an, eine Klasse mit einem Hook zu versehen: Entweder leiten Sie von einer Hook-Klasse ab oder Sie verwenden eine Hook-Klasse, um eine Eigenschaft zu definieren. Während in den vorherigen Beispielen von boost::intrusive::list_base_hook abgeleitet wurde, verwendet Beispiel 18.5 die Klasse boost::intrusive::set_member_hook, um eine Eigenschaft zu definieren.
Beachten Sie, dass der Name der Eigenschaft keine Rolle spielt. Sie müssen jedoch je nach intrusivem Container eine andere Hook-Klasse verwenden. So heißt zum Beispiel die Hook-Klasse, um eine Eigenschaft für eine intrusive Liste zu definieren, nicht boost::intrusive::set_member_hook, sondern boost::intrusive::list_member_hook.
Intrusive Container haben unterschiedliche Hook-Klassen, weil Container unterschiedliche Anforderungen an Elemente stellen, die sie speichern sollen. Sie können jedoch problemlos mehrere Hook-Klassen verwenden, um Objekte in unterschiedlichen intrusiven Containern speichern zu können. Mit boost::intrusive::any_base_hook und boost::intrusive::any_member_hook stehen sogar Klassen zur Verfügung, um Objekte in jedem beliebigen intrusiven Container speichern zu können, ohne dass von mehreren Hook-Klassen abgeleitet werden muss oder mehrere Eigenschaften als Hooks definiert werden müssen.
Intrusive Container erwarten standardmäßig, dass Hooks in Elternklassen definiert sind. Verwenden Sie wie im Beispiel 18.5 eine Eigenschaft, um einen Hook zu definieren, müssen Sie dem intrusiven Container mitteilen, welche Eigenschaft als Hook verwendet werden soll. Deswegen wird dem Template boost::intrusive::set nicht nur die Klasse animal als Parameter übergeben, sondern auch der Typ hook. Dieser ist mit Hilfe der Klasse boost::intrusive::member_hook definiert, die zum Einsatz kommt, wenn ein intrusiver Container eine Eigenschaft als Hook verwenden soll. Das Template boost::intrusive::member_hook erwartet dabei den Klassennamen der im Container zu speichernden Elemente, den Typ des Hooks und einen Zeiger auf die entsprechende Eigenschaft als Parameter.
Wenn Sie Beispiel 18.5 ausführen, wird shark, cat und spider in dieser Reihenfolge ausgegeben.
Neben den in diesem Kapitel vorgestellten Klassen boost::intrusive::list und boost::intrusive::set stellt Boost.Intrusive weitere zum Teil sehr spezielle Container zur Verfügung. Die wichtigsten dieser Container sind neben oben vorgestellten boost::intrusive::slist für einfach verkettete Listen und boost::intrusive::unordered_set für Hash-Container.