const_string: Ein nichtkopierender read-only-string.

1. Warum braucht man einen const_string?

Ein const_string ist besonders geeignet für Parser, die nur lesend auf strings operieren. Hierzu ein simples Beispiel:

std::string between_brackets(const std::string& s)
{
    std::size_t start = s.find('(');
    std::size_t end = s.find(')');
    return s.substr(start, end - start);
}

Das Problem dieses Codes ist, dass es den Substring ausschneidet und in einen neuen String kopiert. Der const_string verhindert diesen Overhead.

2. Die Arbeitsweise des const_strings

Der const_string kann Kopien vollständig vermeiden, indem er lediglich einen Zeiger auf den Anfang und auf das Ende des Strings speichert. Er ist nicht Eigentümer der Daten, und kann so mit anderen strings den Inhalt teilen. Wird nun beispielsweise ein Substring erzeugt, wird ein neues const_string Objekt erstellt, bei dem nur begin und end-Zeiger verschoben sind. Der Inhalt selbst wird nicht kopiert.

3. Implementation

Nachdem das Prinzip erklärt wurde, hier nun die Implementierung.

class const_string
{
public:
    const_string(const char* str):
        begin_(str),
        end_(str + std::strlen(str))
    {}
    const_string(const char* begin, const char* end):
        begin_(begin),
        end_(end)
    {}
    const char* begin() const
    {
        return begin_;
    }
    const char* end() const
    {
        return end_;
    }
    std::size_t size() const
    {
        return end() - begin();
    }
    const_string substr(std::size_t pos, std::size_t length = -1)
    {
        return const_string(begin() + pos, begin() + pos + std::min(size() - pos, n));
    }
private:
    const char* begin;
    const char* end;
};

// Verwendung:
const_string str = "(teststring)";
const_string other_string = str.substr(1, str.size() - 2);

Diese Implementierung dient nur der Verdeutlichung des Prinzips, es fehlen noch einige wichtige Methoden, die ein string haben sollte. Das Interface ist außerdem nicht STL-kompatibel. Eine vollständige(re) Implementierung gibt’s hier.

Small Object Allocator

1. Wozu ein Small Object Allocator?

Die meisten C++ Objekte sind relativ klein, meistens nur wenige Bytes. Manchmal muss man auch Integer anfordern, beispielsweise für den Referenzzähler bei Smart-pointern:

template<typename T>
class shared_ptr
{
public:
    explicit shared_ptr(T* ptr = 0):
        ptr(ptr),
        counter(new int(1))
    {}
    shared_ptr(const shared_ptr& other):
        ptr(other.ptr),
        counter(other.counter)
    {}
    ~shared_ptr()
    {
        if(--*counter == 0)
        {
            delete counter;
            delete ptr;
        }
    }
    // Und weitere typische smart-pointer methoden...
    T& operator*()
    {
        return *ptr;
    }
private:
    int* counter;
    T* ptr;
};

Das ist eine unvollständige Implementierung eines shared_ptrs, ein Zeiger der ein Objekt automatisch löscht, sobald keine Referenzen mehr darauf existieren. Sie soll nur eines zeigen: Hier wird Speicher für ein sehr kleines Objekt angefordert, einen einfachen Integer.

Gut, wo ist jetzt das Problem?
Die Speicherverwaltung für C++ ist dafür ausgelegt, mit allem zu funktionieren. Auch mit großen Objekten. Dementsprechend ist sie nicht für kleine Objekte optimiert: Je nach Implementation werden 4 bis 32 Byte zusätzlich zum eigentlichen Speicherblock allokiert, für Daten wie z.B. ob der Speicherbereich belegt ist, wie groß er ist etc. Wenn ein int z.B. 4 Byte groß ist, und unsere Speicherverwaltung benötigt 32 Byte an zusätzlichen Daten, haben wir einen Overhead von 800%. Fordert man aber z.B. 4096 Byte an, liegt der maximale Overhead nur noch bei ~0.8%.
Also fordert man optimalerweise große Speicherblöcke über den Standardallokator an und verwaltet diesen selbst. Hier kommt der Small Object Allocator zum Einsatz, der diese Arbeit für uns übernimmt.

2. Die Arbeitsweise

Um den Speicher verwalten zu könnten, benötigen wir für jedes Objekt 2 Daten: Die Position im Speicher und die Objektgröße. Wenn wir allerdings jede Objektgröße erlauben, müssen wir zu jeder Speicherstelle noch eine Variable halten, die die Größe speichert. Im Fall von kleinen Objekten reicht ein Byte aus, aber der Overhead im Beispiel des shared_ptrs wäre immer noch bei 25%. Also lassen wir diese Information weg und erstellen uns einen Allokator, der immer nur Objekte einer bestimmten Größe anfordert.
Eine Information müssen wir allerdings immer noch speichern: wo der verfügbare Speicher überhaupt liegt. Ein Zeiger ist üblicherweise 4 Byte groß, das macht im bekannten shared_ptr Beispiel einen Overhead von 100% aus. Das ist eindeutig zuviel. Man könnte nun folgendes tun: Man speichert lediglich einen Zeiger auf den ersten verfügbaren Speicher. Der verfügbare Speicher selbst zeigt auf den Speicherbereich dahinter, bis irgendwann ein Speicher eine 0 beinhaltet. Wenn wir bei einer 0 ankommen, fordern wir einen neuen größeren Speicherblock an den wir entsprechend mit seinen Verweisen initialisieren. Da der angeforderte Speicher selbst die Informationen zur Verwaltung trägt, haben wir lediglich den Overhead eines einzigen Zeigers für alle Objekte einer Größe. Zur Verdeutlichung, folgende Asciigrafik:

+-------------+   +-------------+   +-------------+
|Speicherblock|-->|Speicherblock|-->|Speicherblock|-->
+-------------+   +-------------+   +-------------+
      ^
      |
+---------------------+
|Zeiger auf den ersten|
|verfügbaren Speicher |
+---------------------+

Wird jetzt Speicher angefordert, wird der erste Speicherbereich ausgelesen, der Zeiger auf den verfügbaren Speicher eins weitergesetzt und die Speicherstelle zurückgegeben, auf die der Zeiger zuerst verwies. Dadurch verlieren wir jegliche Kenntnis vom vorherigen Speicher. Was passiert, wenn wir den Speicher zur Freigabe zurückbekommen? Nehmen wir an, wir hätten 2 mal Speicher angefordert und der erste Speicher wurde vom Nutzer an uns zurückgegeben. Folgende Situation wäre dann gegeben:

+-------------+   +-------------+   +-------------+
|Speicherblock|   |Speicherblock|   |Speicherblock|-->
+-------------+   +-------------+   +-------------+
                                         ^
                                         |
+---------------------+                  |
|Zeiger auf den ersten|------------------+
|verfügbaren Speicher |
+---------------------+

Nach der Freigabe des ersten Speicherblocks lassen wir den freigegebenen Speicher auf den nächsten verfügbaren Speicher verweisen und setzen unseren Zeiger auf den eben frei gewordenen Speicherblock. Dadurch können wir wieder freigewordenen Speicher wiederverwenden und haben kein Memoryleak das unendlich wächst. Nach dem Freigeben sieht unsere Struktur so aus:

       +----------------------------------+
       |                                  v
+-------------+   +-------------+   +-------------+
|Speicherblock|   |Speicherblock|   |Speicherblock|-->
+-------------+   +-------------+   +-------------+
       ^
       |
+---------------------+
|Zeiger auf den ersten|
|verfügbaren Speicher |
+---------------------+

Diesem System ist es auch egal, ob die Blöcke am Stück im Speicher liegen, oder getrennt sind. Wir können also jederzeit neue größere Speicherblöcke anfordern und in unsere Liste einfügen. Hier wird der Speicher nur angefordert, wenn unser Zeiger auf 0 zeigt, also kein Block mehr verfügbar ist.

3. Implementation

Zunächst sollten wir ein grobes Interface für den Allokator definieren. Das Prinzip das wir hier haben, heißt auch Pool. Dementsprechend benennen wir unsere Struktur:

struct pool
{
    void init(std::size_t num_blocks, std::size_t object_size);
    void* alloc();
    void free(void* p);
    void release();
};

init initialisiert das Objekt. Der Parameter num_objects gibt an, wieviele Objekte in einem Speicherblock Platz haben sollen. object_size ist die Größe der Objekte in Bytes. Das Gegenstück zu init, release, gibt alle angeforderten Speicherblöcke wieder frei. Dazu müssen wir zusätzlich Daten speichern; das wird erst am Ende dieses Abschnitts besprochen. (Ich verwende hier bewusst init und release statt Kon- und Destruktoren. Später wollen wir mehr Kontrolle über die Pools haben und selbst bestimmen, wann erzeugt und wann freigegeben wird. Es kommt im Prinzip auf das selbe heraus, wenn wir new und delete für einen Pool nutzen würden.)
alloc gibt den Speicherplatz für ein Objekt zurück, free gibt den übergebenen Speicher wieder frei, bzw. fügt ihn in unsere Liste ein.
Nun zur Implementation: Wir benötigen zuerst eine kleine Hilfsstruktur und 2 Methoden die uns das Leben etwas vereinfachen.

    struct block
    {
        block* next;
    };

    static void set_next(void* p, void* next)
    {
        static_cast<block*>(p)->next = static_cast<block*>(next);
    }

    static void* get_next(void* p)
    {
        return static_cast<block*>(p)->next;
    }

Diese sind direkt innerhalb der Poolstruktur definiert, wir benötigen sie auch sonst nirgends. Wenn ein neuer Speicherblock angelegt wird, wird er zuerst mit den Blöcken überschrieben und die Zeiger der Blöcke entsprechend gesetzt. Da wir normalerweise nur void-Zeiger auf den Speicher haben, gibt es die Funktionen set_next und get_next die uns das casten abnehmen. get_next liefert die Adresse des Speicherbereichs, auf die der Block zeigt, set_next setzt die Adresse neu.
Außerdem benötigen wir in der Struktur noch den Zeiger auf den Anfang unserer Liste. Wir nennen ihn head_of_free_list. Die Größe der Objekte und des Blocks werden auch in der Struktur gespeichert. Die init-Methode unseres Pools sieht so aus:

void pool::init(std::size_t num_objects, std::size_t object_size)
{
    this->num_objects = num_objects;
    this->object_size = std::max(object_size, sizeof(block));
    head_of_free_list = 0;
}

Nichts besonders kompliziertes. Man mag sich fragen, wozu std::max hier gebraucht wird, aber das ist schnell erklärt. Die einzelnen Speicherstellen müssen mindestens so groß sein wie ein Objekt unserer Blockstruktur, damit wir unsere verkettete Liste aufbauen können. Man hat aber selten Objekte, die noch kleiner sind als die Blockstruktur, die schließlich nur einen Zeiger hält.
Jetzt wird es etwas schwieriger: die Implementation von alloc.

void* pool::alloc()
{
    void* p = head_of_free_list;
    if(p)
    {
        head_of_free_list = get_next(p);
    }
    else
    {
        char* new_block = new char[num_objects * object_size];
        for(std::size_t i = object_size; i < (num_objects - 1) * object_size; i += object_size)
        {
            set_next(&new_block[i], &new_block[i + object_size]);
        }

        set_next(&new_block[(num_objects - 1) * object_size], 0);
        p = new_block;
        head_of_free_list = &new_block[object_size];
    }

    return p;
}

Ist noch Platz in der Liste, ist das ganze trivial: p ist nicht 0, also wird head_of_free_list eins weiter gesetzt und p zurückgegeben, das vorher den Wert von head_of_free_list angenommen hatte.
Etwas unverständlicher sieht dagegen der else-Teil aus. Zunächst werden für den neuen Block num_objects * object_size Bytes Speicher angefordert. Die seltsam anmutende Schleife beschreibt das zweite bis zum vorletzten Objekt mit jeweils einem Zeiger auf das nächste. Das erste Objekt wird nicht beschrieben, da es ja sowieso danach an den Anwender zurückgegeben wird. Das letzte benötigt auch eine Spezialbehandlung, da es ins Nirvana zeigen soll, um das Ende der Liste anzugeben. Danach wird noch head_of_free_list auf das 2. Element des Blockes gesetzt und das 1. Element zurückgegeben. Das wars schon.

free gestaltet sich relativ einfach:

void pool::free(void* p)
{
    if(p == 0)
        return;

    block* dead_object = static_cast<block*>(p);

    dead_object->next = static_cast<block*>(head_of_free_list);
    head_of_free_list = dead_object;
}

Der freigegebene Speicher verweist nun auf das vorher erste Objekt in der Liste und der Zeiger auf den Listenanfang wurde neu gesetzt.
Übergebene 0-Zeiger ignorieren wir übrigens einfach aus Konsistenzgründen. In C++ ist schließlich auch ein delete 0; ohne weiteres möglich.
Zu release:
Das endgültige Freigeben des Speichers an das Betriebssystem beim Zerstören des Pools kann auch weggelassen werden. Dadurch haben wir nicht unbedingt ein Memoryleak. Memoryleaks entstehen, wenn man keinen Zugriff mehr auf Speicher hat, der noch nicht freigegeben wurde. Dadurch, dass wir aber die Objekte in unserer Liste verwalten, wächst der Speicherbedarf nicht ins unendliche, sondern erreicht einen Maximalwert. Es sei denn, jemand kommt auf die Idee, den pool immer wieder in einer Schleife anzulegen, dann entsteht natürlich ein Leak. Später in der Kapselung werden wir allerdings dafür sorgen, dass ein pool das komplette Programm überdauert. Sollte man dennoch den Speicher freigeben wollen, fügt man leider ein wenig Overhead hinzu: man muss beim Anfordern eines größeren Blockes einen Zeiger in einen std::vector einfügen, beim release durchlaufen und jedes Element mit delete [] löschen. Auf diese Weise kann man auch lokale Pools verwenden, falls man das unbedingt benötigt.

4. Kapselung des Pools

Zunächst sollten wir uns überlegen, wie die Anwendung aussehen soll. Es würde z.B. sehr einfach werden, wenn man Objekte einfach nur von einer Klasse small_object ableiten müsste, und schon wird bei jedem new automatisch dieser Allokator genutzt. Damit small_object die Größe des Typen kennt, werden wir daraus ein Template machen und als Parameter den Typen nehmen, der ableitet. In small_object reichen dann ein paar einfache Überladungen von operator new und delete und wir sind fast fertig. Zuerst benötigen wir einen Wrapper um den Pool, der automatisch init und release aufruft, und als dummy-Parameter für alloc und free die Größe des Speichers übernimmt. Wozu das gut ist, sehen wir später. Hier zuerst die einfache Implementation des fixed_size_allocators:

class fixed_size_allocator
{
public:
    fixed_size_allocator(std::size_t num_objects, std::size_t object_size)
    {
        allocator.init(num_objects, object_size);
    }
    
    ~fixed_size_allocator()
    {
        allocator.release();
    }
    
    void* alloc(std::size_t)
    {
        return allocator.alloc();
    }
    
    void free(void* p, std::size_t)
    {
        allocator.free(p);
    }
private:
    fixed_size_allocator(const fixed_size_allocator&);
    fixed_size_allocator& operator=(const fixed_size_allocator&);
    pool allocator;
};

Die Implementation von small_object kann dann so aussehen:

template<typename T>
class small_object
{
    static void* operator new(std::size_t size)
    {
        return allocator.alloc(size);
    }
    static void* operator new(std::size_t size, void* p)
    {
        return p;
    }
    static void operator delete(void* p, std::size_t size)
    {
        allocator.free(p, size);
    }
private:
    static fixed_size_allocator allocator;
};
template<typename T>
fixed_size_allocator small_object<T>::allocator(64, sizeof(T));

Der 2. operator new sorgt übrigens nur dafür, dass placement-new immer noch möglich ist.
Die Anwendung sieht folgendermaßen aus:

struct foo : small_object<foo>
{
    int i;
};

Mehr braucht man nicht. Nur ableiten. Ein Problem hat diese Implementierung allerdings: Für jeden Typen wird ein neuer pool angelegt. Auch wenn 2 Typen die selbe Größe haben. Um das zu umgehen, schreiben wir nun eine Klasse small_obj_allocator, die Objekte beliebiger Größe anfordern kann. Sie sammelt dazu lediglich alle pools in einem vector und sucht nach dem mit der passenden Größe.

class small_obj_allocator
{
    static bool compare_pool_size(const pool& p, std::size_t size)
    {
        return p.object_size < size;
    }
public:
    small_obj_allocator(std::size_t num_objects, std::size_t max_object_size):
        num_objects(num_objects),
        max_object_size(max_object_size),
        allocators(),
        last_alloc(0),
        last_free(0)
    {
    }
    ~small_obj_allocator()
    {
        std::for_each(allocators.begin(), allocators.end(),
                      std::mem_fun_ref(&pool::release));
    }
    
    void* alloc(std::size_t size)
    {
        if(size > max_object_size)
        {
            return ::operator new(size);
        }
        size = std::max(size, sizeof(pool::block));
        
        if(last_alloc && last_alloc->object_size == size)
        {
            return last_alloc->alloc();
        }

        std::vector<pool>::iterator iter =
            std::lower_bound(allocators.begin(),
                             allocators.end(),
                             size,
                             compare_pool_size);

        if(iter == allocators.end() || iter->object_size != size)
        {
            iter = allocators.insert(iter, pool());
            iter->init(num_objects, size);
            last_free = &allocators.front();
        }
        last_alloc = &*iter;
        return last_alloc->alloc();
    }
    
    void free(void* p, std::size_t size)
    {
        if(size > max_object_size)
        {
            ::operator delete(p);
            return;
        }
        
        if(last_free && last_free->object_size == size)
        {
            last_free->free(p);
            return;
        }
        std::vector<pool>::iterator iter =
            std::lower_bound(allocators.begin(),
                             allocators.end(),
                             size,
                             compare_pool_size);
        last_free = &*iter;
        last_free->free(p);
    }
private:
    std::size_t num_objects;
    std::size_t max_object_size;
    std::vector<pool> allocators;
    pool* last_alloc;
    pool* last_free;
};

Falls der Code jemandem bekannt vorkommt: Das ist die selbe Strategie, mit der Andrei Alexandrescus SmallObjAllocator die Anfragen an seine Pools in der Loki-lib weiterleitet. Ich werde hier nicht näher darauf eingehen, nur erklären wie er ungefähr arbeitet: Da man häufig mehrere Objekte hintereinander mit gleicher Größe anfordert oder freigibt, speichert small_obj_allocator den zuletzt verwendeten pool. Ist dieser für die Freigabe oder Allokation nicht zuständig, wird mit einer Binären Suche der passende pool festgestellt. Das ist möglich, da der vector ständig sortiert wird.
Nun müssen wir das noch in unser small_object einbauen – wir sollten dem Benutzer aber die Wahl lassen. Die Suche nach dem passenden pool geht auf Kosten der Laufzeit, auf der anderen Seite benötigt der fixed_size_allocator wegen möglichen Doppelungen von pools mehr Speicher.
Wir testen einfach den an small_object übergebenen typen. Wenn er ein von uns vordefinierter dummy-typ ist, wird der small_obj_allocator verwendet, ansonsten der fixed_size_allocator.
Hier zeigt sich auch der Vorteil der Übergabe des size-Parameters an fixed_size_allocator: small_obj_allocator benötigt die Größe, fixed_size_allocator eigentlich nicht. Dadurch, dass aber beide nun die selbe Schnittstelle besitzen, müssen wir lediglich über ein typedef den Allokatortypen festlegen und der Rest geht von allein. Zusätzlich legen wir noch eine Konstante object_size fest. Bei dem vordefinierten dummy-typen wird sie auf 64 gesetzt, ansonsten auf sizeof(T). Das bedeutet, sobald vom small_obj_allocator ein Speicherbereich abgefragt wird, der größer als 64 Byte ist, wird die Anfrage an den globalen operator new weitergeleitet. Ebenso beim Freigeben an operator delete.
Unser neues small_object-Template:

struct empty_type {};

template<typename T = empty_type>
class small_object
{
    typedef is_same<T, empty_type> is_empty_type;
public:
    typedef typename if_
    <
        is_empty_type,
        small_obj_allocator,
        fixed_size_allocator
    >::type allocator_type;
    
    static const std::size_t object_size = is_empty_type::value ? 64 : sizeof(T);
        
    static void* operator new(std::size_t size)
    {
        return allocator.alloc(size);
    }
    
    static void* operator new(std::size_t size, void* p)
    {
        return p;
    }

    static void operator delete(void* p, std::size_t size)
    {
        allocator.free(p, size);
    }
private:
    static allocator_type allocator;
};

template<typename T>
typename small_object<T>::allocator_type
small_object<T>::allocator(64, small_object<T>::object_size);

is_same ist ein einfaches Template mit einer statischen integralen Konstante, die true ist, wenn beide übergebenen Typen gleich sind, ansonsten false. if_ wertet den ersten Parameter als Bedingung aus, wenn dessen value true ist, wird ein typedef auf den 2. übergebenen Typen gemacht, ansonsten auf den 3. Ein Compile-time-if also.
Hier kurz ihre Definitionen:

template<bool If, typename Then, typename Else>
struct if_c
{
    typedef Then type;
};

template<typename Then, typename Else>
struct if_c<false, Then, Else>
{
    typedef Else type;
};

template<typename If, typename Then, typename Else>
struct if_ : if_c<If::value, Then, Else> {};

template<typename T, typename U>
struct is_same
{
    static const bool value = false;
};

template<typename T>
struct is_same<T, T>
{
    static const bool value = true;
};

Ende. Ein einsatzbereiter Small Object Allocator.

C++ Idiom: RAII

Beim Anfordern von Ressourcen muss man als Programmierer immer aufpassen, diese auch wieder richtig freizugeben. Beispiele sind Dateien schließen, Speicher freigeben oder Locks aufheben. Gleich zu Beginn ein Beispiel-Code:

lock l;

void do_something()
{
    l.acquire();
    if(some_resource == 0)
    {
        throw std::runtime_error("resource not found");
    }
    else
    {
        some_resource->weird_stuff();
    }
    l.release();
}

Das Problem ist klar: Wird eine Exception geworfen oder aus sonst einem Grund die Funktion früher erlassen, haben wir einen Deadlock. l wurde niemals freigegeben. Vor das throw auch noch ein l.release() zu schreiben, kann nicht die Lösung sein. weird_stuff könnte auch eine Exception werfen, und so die Funktion beenden, was ist also zu tun? Man könnte umständlich mit try-catch alles fangen, den Lock freigeben und rethrowen. Aber C++ hat ein besseres Mittel: Destruktoren

class scoped_lock
{
public:
    scoped_lock(lock& l):
        l(l)
    {
        l.acquire();
    }
    ~scoped_lock()
    {
        l.release();
    }
private:
    lock& l;
};

Anwendung in unserem Fall:

lock l;

void do_something()
{
    scoped_lock sl(l);
    if(some_resource == 0)
    {
        throw std::runtime_error("resource not found");
    }
    else
    {
        some_resource->weird_stuff();
    }
}

Egal auf welchem Weg die Funktion verlassen wird, der Destruktor von sl wird immer aufgerufen und der Lock freigegeben.

Wie sieht RAII in anderen Sprachen aus? Die meisten Sprachen kennen diese Technik nicht. So sieht z.B. der Code um eine Datei zu öffnen und aus ihr zu lesen in Java so aus:

FileInputStream fis = null;
try
{
    fis = new FileInputStream("datei.txt");
    // mach was mit fis
    // ...
}
finally
{
    if(fis != null)
        fis.close();
}

Python hat hierfür seit Version 2.6 ein with-statement:

with open("datei.txt") as f:
    # mach was mit f
    pass

Hier noch ein Beispiel in C++ zur Vertiefung: Eine Implementierung einer file-Klasse die auf C-Dateioperationen basiert und immer alles korrekt aufräumt (der Einfachheit halber nur zum Schreiben):

class file
{
public:
    file(const std::string& filename):
        fp(std::fopen(filename.c_str(), "w"))
    {
        if(fp == 0)
        {
            throw std::runtime_error("Could not open file");
        }
    }
    ~file()
    {
        std::fclose(fp);
    }

    void write(const std::string& text)
    {
        if(std::fputs(text.c_str(), fp) == EOF)
        {
            throw std::runtime_error("Could not write to file");
        }
    }
private:
    std::FILE* fp;

    file(const file&);
    file& operator=(const file&);
};

C++ Idiom: Copy & Swap

Nehmen wir einmal an, wir möchten eine Arrayklasse für Objekte dieses Typen bauen:

struct object
{
    object& operator=(const object& other)
    {
        if(std::rand() == 12389)
        {
            throw std::exception();
        }
    }
};

Eine erste Implementation könnte so aussehen:

class object_array
{
public:
    object_array():
        array(0),
        size(0)
    {}

    explicit object_array(std::size_t size):
        array(new object[size]),
        size(size)
    {}

    object_array(const object_array& other):
        array(0),
        size(other.size)
    {
        if(other.array && size)
        {
            try
            {
                array = new object[size];
                std::copy(other.array, other.array + size, array);
            }
            catch(...)
            {
                delete [] array; // Im Fehlerfall speicher freigeben, um kein Speicherleck zu hinterlassen.
                throw;
            }
        }
    }

    ~object_array()
    {
        delete [] array;
    }

    object_array& operator=(const object_array& other)
    {
        delete [] array;
        array = 0;
        size = other.size;
        if(other.array && size)
        {
            array = new object[size];
            std::copy(other.array, other.array + size, array);
        }
        return *this;
    }

    object& operator[](std::size_t index)
    {
        assert(index < size);
        return array[index];
    }

    object operator[](std::size_t index) const
    {
        assert(index < size);
        return array[index];
    }

private:
    object* array;
    std::size_t size;
};

Diese Implementation weist einige Probleme auf. operator= beinhaltet praktisch den selben Code wie der Kopierkonstruktor. Nun könnte man eine Funktion copy schreiben, die von operator= und vom Kopierkonstruktor aufgerufen wird.

Doch was passiert bei einer Selbstzuweisung?

object_array array(5);
array = array;

Verursacht undefiniertes Verhalten. Das eigene Array wird im Zuweisungsoperator gelöscht und vom anderen Objekt in das eigene Array hineinkopiert. Wenn das andere Array das selbe ist wie das eigene wird beim Kopieren auf Speicher zugegriffen, der gerade erst freigegeben wurde. Das lässt sich aber auch regeln. Über eine Simple abfrage ob this == &other.

Ein Problem besteht aber immer noch: Eine Kopieroperation von object kann eine Exception werfen. Was passiert nun, wenn bei operator= das Kopieren eines Elements mittendrin fehlschlägt? operator= bricht ab und lässt das Array in einem ungültigen Zustand. Alle Elemente nach dem objekt, das die Exception warf, bleiben unkopiert.

Die Lösung: Das Copy & Swap Idiom. Alle eben genannten Probleme lassen sich darüber lösen, ohne irgendwelchen copy-Funktionen oder Abfragen ob this == &other. Wir ergänzen eine swap-Funktion, die 2 object_arrays miteinander tauscht:

    void swap(object_array& other)
    {
        std::swap(array, other.array);
        std::swap(size, other.size);
    }

Unseren operator= implementieren wir nun so:

    object_array& operator=(object_array other)
    {
        swap(other);
        return *this;
    }

Er arbeitet folgendermaßen: Das auf der rechten Seite stehende Objekt der Zuweisung wird über den Kopierkonstruktor kopiert. Dieses Objekt wird über swap getauscht. Wenn beim Kopieren etwas fehlschlägt, bleibt das Objekt, dem zugewiesen wurde, in seinem ursprünglichen, gültigen Zustand. Beim swap kann nichts fehlschlagen, da lediglich Zeiger und Integer getauscht werden müssen. Das other-objekt übernimmt den Speicher des alten Objekts und zerstört diesen beim Verlassen der Funktion. Hier noch einmal die vollständige Klasse:

class object_array
{
public:
    object_array():
        array(0),
        size(0)
    {}

    explicit object_array(std::size_t size):
        array(new object[size]),
        size(size)
    {}

    object_array(const object_array& other):
        array(0),
        size(other.size)
    {
        if(other.array && size)
        {
            try
            {
                array = new object[size];
                std::copy(other.array, other.array + size, array);
            }
            catch(...)
            {
                delete [] array; // Im Fehlerfall speicher freigeben, um kein Speicherleck zu hinterlassen.
                throw;
            }
        }
    }

    ~object_array()
    {
        delete [] array;
    }

    object_array& operator=(object_array other)
    {
        swap(other);
        return *this;
    }

    void swap(object_array& other)
    {
        std::swap(array, other.array);
        std::swap(size, other.size);
    }

    object& operator[](std::size_t index)
    {
        assert(index < size);
        return array[index];
    }

    object operator[](std::size_t index) const
    {
        assert(index < size);
        return array[index];
    }

private:
    object* array;
    std::size_t size;
};

LISP-Konzepte in C++ Templates

In diesem Eintrag will ich zeigen, wie man einige Konzepte aus LISP direkt in C++ Templates übertragen kann.
Zu Beginn folgender Scheme-Code:

(define (cons a b)
  (lambda (f) (f a b)))
(define (car l)
  (l (lambda (a b) a)))
(define (cdr l)
  (l (lambda (a b) b)))

Das ist eine Möglichkeit, ein Listensystem in Scheme zu implementieren. Das sieht folgendermaßen aus: Eine Liste ist ein Paar bestehend aus einem Element und dem Rest, wobei der Rest wiederum eine Liste ist, bis irgendwann ein Element am Ende steht, das nichts repräsentiert.

(cons 1 (cons 2 (cons 3 (cons 4 nil))))

erstellt eine Liste mit den Zahlen von 1 bis 4. Mit car besteht die Möglichkeit, auf das Element zuzugreifen, mit cdr auf den Rest. (Die eben konstruierte Liste ist hier l):
(cdr l) sind die Zahlen 2 bis 4.
(car l) ist die 1.
Unsere Implementation in Scheme funktioniert so:
cons gibt eine Funktion zurück, die eine Funktion als Parameter übernimmt, ihr das Element und Rest der Liste als Parameter übergibt, und ihren Rückgabewert zurückgibt. car übergibt der mit cons erzeugten Funktion eine Funktion, die ihren ersten Parameter zurückgibt, also das Element. cdr tut das gleiche, allerdings gibt es den Rest zurück. Das will ich nun in C++ umsetzen.
Um alles mögliche in einer Liste zu speichern, benötigen wir eine allgemeine Schnittstelle, wie Listenelemente aussehen sollen. In der Metaprogrammierung in C++ verwendet man dafür normalerweise Typen. Wir brauchen also eine Möglichkeit, um aus Zahlen Typen zu machen. Das ist relativ simpel:

template<typename T, T Value>
struct integral_constant
{
    typedef integral_constant<T, Value> type;
    typedef T value_type;
    static const T value = Value;
};
template<int Value>
struct int_ : integral_constant<int, Value>{};

integral_constant speichert den übergebenen Wert im statischen Member value. Dadurch können wir aus dem Typen auch jederzeit die Zahl wieder herausholen. int_ ist hier nur dazu da, damit wir über eine kürzere Schreibweise aus einem Integer einen Typen machen können.
Nun zum komplizierten Teil: Wie setzt man Lambdas in C++ um? Dazu benötigen wir zunächst das Konzept der Metafunktion. Eine Metafunktion ist grundsätzlich so aufgebaut:

struct mul
{
    template<typename Param1, typename Param2>
    struct apply
    {
        typedef int_<Param1::value * Param2::value> type;
    };
};

Die Metafunktion muss ein Strukturentemplate mit dem Namen apply besitzen. apply ist die eigentliche Funktion. Ihr Rückgabewert stellt sich über einen Typen mit dem Namen type dar. Die hier gezeigte Funktion nimmt an, dass die Parameter das integral_constant Konzept unterstützen und hat als Rückgabewert einen Integer, in dem das Produkt der beiden Parameter steht. Ein Aufruf inklusive Ausgabe könnte z.B. so aussehen:

std::cout << mul::apply<int_<3>, int_<2> >::type::value;

Die Ausgabe ist 6.
Eine Lambda können wir in C++ als einfache lokale Metafunktion umsetzen. Damit wird unser cons – übrigens auch eine Metafunktion – zu:

struct cons
{
    template<typename A, typename B>
    struct apply
    {
        struct type
        {
            template<typename F>
            struct apply
            {
                typedef typename F::template apply<A, B>::type type;
            };
        };
    };
};

Das Ganze sieht erstmal etwas kompliziert aus, ist es aber eigentlich gar nicht. apply kennen wir ja schon, es beinhaltet praktisch die eigentliche Funktion. Es bekommt hier das Element (A) und den Rest der Liste (B) als Parameter. Der Rückgabewert type ist hier erneut eine Metafunktion, die eine Metafunktion (F) erwartet. Dessen Rückgabewert ist auch der Rückgabewert der Metafunktion type.
Nun benötigen wir erst einmal die Funktion car, um auf das erste Element der Liste zugreifen zu können.

struct car
{
    template<typename L>
    struct apply
    {
        struct lambda
        {
            template<typename A, typename B>
            struct apply
            {
                typedef A type;
            };
        };
        typedef typename L::template apply<lambda>::type type;
    };
};

Auch hier ist wieder in apply die eigentliche Funktion. Sie erwartet die Liste L, eigentlich eine Metafunktion und übergibt ihr eine Lambdafunktion, die ihr erstes Argument zurückgibt. Also genau das Prinzip wie in der Schemeimplementation. cdr, die Funktion die den Rest der Liste zurückgibt, sieht ähnlich aus und unterscheidet sich nur in der Lambdafunktion:

struct cdr
{
    template<typename L>
    struct apply
    {
        struct lambda
        {
            template<typename A, typename B>
            struct apply
            {
                typedef B type;
            };
        };
        typedef typename L::template apply<lambda>::type type;
    };
};

Als Markierung für das Ende einer Liste nehmen wir einfach einen Typen, der nil darstellt.

struct nil {};

Das Ganze nun in einem Programm angewandt:

#include <iostream>
typedef cons::apply<int_<1>,
        cons::apply<int_<2>,
        cons::apply<int_<3>,
        cons::apply<int_<4>,
        nil>::type>::type>::type>::type list;
template<typename L>
struct print_list
{
    static void run()
    {
        std::cout << car::apply<L>::type::value << std::endl;
        print_list<typename cdr::apply<L>::type>::run();
    }
};
template<>
struct print_list<nil>
{
    static void run()
    {
    }
};
int main()
{
    print_list<list>::run();
}

print_list<>::run gibt das erste Element der Liste aus, und ruft sich rekursiv mit dem Rest der Liste auf. Die Rekursion stoppt, wenn der Parameter nur noch nil ist.

Eine Liste zur Compilezeit geht in C++ natürlich auch einfacher, aber hier wollte ich nur die direkte Umsetzung eines LISP Konzepts in C++ zeigen, auch wie Lambdas möglich sind und wie man eine Allgemeine Schnittstelle für Zahlen, Typen oder Funktionen findet.