Wir brauchen Platz

Ein etwas abgefahreneres Thema: wie kommen eigentlich die ganzen STL-Container an ihren Speicher? Man könnte ja annehmen, dass die einfach mittels new/delete arbeiten, aber weit gefehlt: um die Teile so flexibel, wie möglich zu halten, verwenden die einen Allocator, den man auch selbst implementieren und verwenden kann.

Video

Quelltext

#include <iostream>
#include <list>
#include <typeinfo>
#include <limits>

template <typename T> class LoggingAllocator
{
public:
  typedef T  value_type;
  typedef T* pointer;
  typedef const T* const_pointer;
  typedef T& reference;
  typedef const T& const_reference ;
  typedef std::size_t size_type;
  typedef std::ptrdiff_t difference_type;
  
  template <typename Other> struct rebind
  {
    typedef LoggingAllocator<Other> other;
  };
  
  LoggingAllocator()
  {
    std::cerr << "Neue LoggingAllocator-Instanz angelegt.\n";
  }
  
  ~LoggingAllocator()
  {
    std::cerr << "LoggingAllocator-Instanz zerstört\n";
  }
  
  pointer address(reference value) const
  {
    std::cerr << "Adresse von Objekt erfragt " << &value << std::endl;
    return &value;
  }
  
  pointer allocate(size_type number, std::allocator<void>::const_pointer hint = 0)
  {
    pointer p = reinterpret_cast<pointer>(::operator new(number*sizeof(T)));
    std::cerr << "Reserviere Platz für " << number << " Objekte der Größe " << sizeof(T) << " an Position " << static_cast<void*>(p) << std::endl;
    return p;
  }
  
  void deallocate(pointer p, size_type)
  {
    std::cerr << "Gebe Speicher frei an Position " << static_cast<void*>(p) << std::endl;
    ::operator delete(p);
  }
  
  size_type max_size() const noexcept
  {
    std::cerr << "Maximale Anzahl reservierbarer Elemente abgefragt: " << std::numeric_limits<size_type>::max()/sizeof(T) << std::endl;
    return std::numeric_limits<size_type>::max()/sizeof(T);
  }
  
  template <typename U, typename... Args> void construct(U* ptr, Args&&... args)
  {
    std::cerr << "Konstruiere neues Objekt des Typs " << typeid(U).name() << " an Position " << static_cast<void*>(ptr) << std::endl;
    ::new(static_cast<void*>(ptr)) U(std::forward<Args>(args)...);
  }
  
  template <typename U> void destroy(U* ptr)
  {
    std::cerr << "Zerstöre Objekt des Typs " << typeid(U).name() << " an Position " << static_cast<void*>(ptr) << std::endl;
    ptr->~U();
  }
};

int main()
{
  std::list<int, LoggingAllocator<int>> l;
  l.push_back(10);
  l.push_back(20);
}

Erklärung

Allocator sind im C++-Standard fast etwas unterdokumentiert. Die einzige etwas umfassendere Quelle ist § 20.6.9.1 "allocator members", in der die Memberfunktionen des Standardallokators std::allocator beschrieben werden. Wenn man sich tunlichst an die hält und sie für einen eigenen Allokator implementiert, dann wird der funktionieren.

Aufgabe des Allokators ist es, die Details des zugrundeliegenden Speichermodells zu abstrahieren. Dafür muss er natürlich zuerstmal Speicher reservieren und freigeben können (die Methoden allocate und deallocate). Zusätzlich muss er natürlich Objekte in diesem Speicher konstruieren und zerstören können (dafür sind construct und destroy zuständig).Weitere Kleinigkeiten, die man nicht übersehen darf: die Adresse eines Objektes holen (normalerweise ist das ja operator&, aber es könnte ja durchaus sein, dass sich das in einem speziellen Speichermodell anders verhält) und zumindest mal ausrechnen, was maximal geht (max_size. Vor allem für embedded-Plattformen interessant).

Der LoggingAllocator oben verhält sich grundsätzlich wie std::allocator: er reserviert den Speicher mit new und gibt ihn mit delete frei. Außerdem konstruiert er Objekte durch ein einfaches placement new (Zeile 60), bei dem kein neuer Speicher reserviert wird, sondern in einem existierenden Speicherbereich (der Parameter von new in den runden Klammern) ein Objekt instanziiert wird. Analog kann mittels eines direkten Konstruktoraufrufs (Zeile 66) ein Objekt zerstört werden, ohne den betreffenden Speicherbereich freizugeben. Der einzige Unterschied des LoggingAllocator: all das tut er recht geschwätzig und informiert über die einzelnen Aktionen. Sehr praktisch, wenn man einem STL-Container mal bei der Arbeit zuschauen will.

Als Besonderheit beim Entwurf des Allokators sind die Templates construct und destroy, sowie struct rebind zu beachten. Auch wenn ein Allokator eigentlich für einen spezifischen Typ parametrisiert werden kann (nicht zwingend notwendig, aber im Falle von unserem Beispiel oben praktisch, weil der dann für alle möglichen Typen wiederverwendet werden kann. Grundsätzlich wäre auch ein Allokator denkbar – wenn auch unpraktisch –, der nur einen bestimmten Objekttyp reservieren kann.), muss er in der Lage sein, Objekte eines anderen Typs zu konstruieren und zu zerstören. Mir ist ehrlich gesagt nicht 100% klar, wieso das so ist, denn eigentlich sollten diese ihren eigenen Allokatortyp kriegen. Dafür ist nämlich rebind da: aus dem gegebenen Allokator einen anderen erzeugen, der für einen anderen Typ da ist. In unserem Fall ist das einfach: das gleiche Template, aber ein anderer Parameter. Hat man da was komplexeres (bspw. unterschiedliche Typen in unterschiedlichen Speicherbereichen oder ähnliches), dann kann man das natürlich auch so erledigen. Evtl. weiß ja jemand, wieso es da diese beiden Mechanismen gibt, die sich aus meiner Sicht ein klein wenig widersprechen. Der Standard ist da leider etwas knapp.