C++: Höherwertige Container

von Hubert Schmid vom 2014-03-30

Die Standardbibliothek von C++ enthält zahlreiche Container für Listen, Mengen und assoziative Felder. Höherwertige Datenstrukturen – wie beispielsweise die LinkedHashMap in Java – sucht man dort allerdings vergebens. Für C++ greift man stattdessen gerne auf die Boost Multi-Index Container zurück, die praktisch unzählig viele Möglichkeiten bieten, Constainer mit mehreren Zugriffswegen zu konstruieren. Doch auch ohne Boost lassen sich Container in C++ einfach miteinander kombinieren.

Als Beispiel verwende ich eine Datenstruktur, um die zuletzt verwendeten Dateien zu verwalten – eine mittlerweile weit verbreitete Funktion in Anwendungen. Häufig wird dafür auch die Abkürzung LRU verwendet. Die Schnittstelle sollte ungefähr wie folgt aussehen, wobei die Iteratoren die Einträge in der Reihenfolge der letzten Verwendung liefern, und die Funktion put entweder einen neuen Eintrag anlegt oder den gegebenenfalls bereits existierenden an den Anfang der Liste stellt.

template <typename Value>
class recent_list
{
    using Iterator = ...;
public:
    explicit recent_list(std::size_t limit);
    auto begin() const -> Iterator;
    auto end() const -> Iterator;
    void put(Value value);
};

Implementieren lässt sich diese Datenstruktur vergleichsweise einfach mit Hilfe einer std::list. Der entsprechende Code ist im folgenden Listing zu sehen. Allerdings hat diese Implementierung ein Problem: Die Laufzeit der put-Funktion ist linear in der Anzahl der Einträge. Bei zehn Einträgen spielt das keine Rolle. Dennoch wäre wünschenswert, dass die Datenstruktur auch für andere Größenordnungen effizient ist.

template <typename Value>
class recent_list
{
    using Iterator = typename std::list<Value>::const_iterator;
    std::size_t _limit;
    std::list<Value> _list;
public:
    explicit recent_list(std::size_t limit) : _limit{limit} { }
    auto begin() const { return _list.cbegin(); }
    auto end() const { return _list.cend(); }
    void put(Value value)
    {
        auto p = std::find(_list.cbegin(), _list.cend(), value);
        if (p != _list.cend()) {
            _list.splice(_list.cbegin(), _list, p);
        } else {
            _list.push_front(std::move(value));
            if (_list.size() > _limit) {
                _list.pop_back();
            }
        }
    }
};

Das Problem lässt sich durch Hinzufügen einer assoziativen Datenstruktur lösen. Im ersten Augenblick könnte man an std::unordered_map<Value, Iterator> denken, doch dann würde Value zweimal gespeichert werden. Tatsächlich reicht std::unordered_set<Iterator> bereits aus, wobei der Iterator als Stellvertreter für das eigentliche Objekt agiert. Damit das funktioniert, muss std::unordered_set geeignet für die Hash-Berechnung und den Vergleich parametrisiert werden. Dazu gleich mehr, doch zunächst geht es um die put-Funktion. Im folgenden Listing wird immer zunächst ein neuer Eintrag angelegt. Falls anschließend festgestellt wird, dass bereits ein passender Eintrag existiert, wird der neu eingefügte wieder entfernt und der Alte an den Anfang verschoben.

    void put(Value value)
    {
        _list.push_front(std::move(value));
        auto r = _set.insert(_list.cbegin());
        if (!r.second) {
            _list.pop_front();
            _list.splice(_list.cbegin(), _list, *r.first);
        } else if (_set.size() > _limit) {
            _set.erase(std::prev(_list.cend()));
            _list.pop_back();
        }
    }

Alternativ könnte man zuerst die Existenz prüfen, und nur im Negativfall einen neuen Eintrag anlegen. Einfacher wird der Code dadurch jedoch nicht.

Es fehlt noch die korrekte Deklaration und Definition der std::unordered_set, so dass sie mit den Stellvertreter-Objekten korrekt arbeitet. Dafür hilft zunächst ein Template für ein Funktionsobjekt, das den Aufruf an das eigentliche Objekt weiterleitet, dabei jedoch alle Parameter dereferenziert.

template <typename Delegate>
struct proxy
{
    Delegate _delegate;
    template <typename ...Args>
    auto operator()(Args&&... args) const
    {
        return _delegate(*std::forward<Args>(args)...);
    }
};

Damit ist der Rest sehr einfach. Das Klassen-Template wird um Typparameter für die Hashfunktion und das Vergleichsprädikat erweitert. Die std::unordered_set wird mit proxy<Hash> und proxy<Equals> parametrisiert, da sie auf Iterator statt Value arbeitet. Und schließlich wird noch der Konstruktor um zwei zusätzliche Parameter erweitert, damit der Nutzer den Vergleich beliebig parametrisieren kann. Das folgende Listing zeigt die konkrete Implementierung.

template <typename Value, typename Hash = std::hash<Value>, typename Equals = std::equal_to<Value>>
class recent_list
{
    // ...
    std::unordered_set<Iterator, proxy<Hash>, proxy<Equals>> _set;
public:
    explicit recent_list(std::size_t limit, Hash hash = {}, Equals equals = {})
        : _limit{limit}
        , _set{0, proxy<Hash>{std::move(hash)}, proxy<Equals>{std::move(equals)}}
    { }
};

Es gibt noch ein wichtiges Detail, das es zu beachten gilt. Der Code sieht zwar so aus, als würde er korrekt mit Ressourcen umgehen. Doch dieser Eindruck täuscht. Kopiert man die Datenstruktur, werden auch die Member-Variablen _list und _set kopiert. Allerdings werden dabei die Iteratoren, die in _set gespeichert werden, nicht automatisch auf die neue _list umgebogen. Das müsste man manuell aufmachen. Alternativ kann man auch einfach die entsprechenden Konstruktoren und Zuweisungsoperatoren mit = delete deklarieren.

Fazit: Der Eigenbau ist sicherlich aufwendiger als die Verwendung von Datenstrukturen aus den Bibliotheken von Drittanbietern. Doch andererseits ist die eigene Implementierung einfacher als viele annehmen. Insbesondere erfordert sie keine besonderen Kenntnisse über die Implementierung solcher Datenstrukturen. Ob sich ein Eigenbau lohnt, hängt natürlich vom konkreten Umfeld ab. Die Reduzierung von Abhängigkeiten auf Drittanbieter kann jedoch sehr wertvoll sein.