[C++] Vector-Klasse mit statischer Allokation

[Schrompf]

Moin Leute,

ich brauche hier und da statisch allokierte Arrays mit einer Maximalgröße als template-Parameter, die ich aber wie einen std::vector befüllen möchte. Mir fiel dazu bisher nur boost::array ein, aber das ist wirklich nur ein statisches Array. Ich möchte aber push_back(), erase() und alles machen können, ohne selbst mitzählen zu müssen. Ich bin gerade drauf und dran, mir sowas selbst zu schreiben, aber bevor ich wieder Zeit verschwende, frage ich vorher besser mal hier nach.

Gibt es irgendwo eine fertige Klasse, die ein statisches Array wrappt und trotzdem alle Manipulationsfunktionen eines std::vector bietet?

[eXile]

Mir fiele std::array ein.

Edit: Quark mit Soße. Du willst ja so etwas wie push_back. Sorry.

[Schrompf]

Stimmt, gleiches Problem wie die gleichnamige Boost-Lösung. Ich vermute sogar, std::array ist daraus hervorgegangen :-)

[CodingCat]

In Zeile 32 ein Array statt des Heap-alloziierten Speicherbereichs einsetzen, und du hast in etwa was du willst. Leider müsstest du wohl noch mühsam einige Abhängigkeiten und überflüssige Funktionalität von Hand auflösen, eventuell tust du also doch besser daran, die Sache gleich ganz selbst in die Hand zu nehmen. ;-) Zumal mein Code immernoch größtenteils als ungetestet bezeichnet werden muss. :|

[dot]

Sicher dass du nicht vielleicht einfach sowas wie einen Ringbuffer willst (gibts in boost)?

[Schrompf]

Danke für die Tipps. Das Eigen-Schreiben hab ich inzwischen schon angefangen, und bis auf Details rund um insert() und erase() ist eigentlich alles schnell gemacht. boost::circular_buffer erfüllt leider die "statisch allokieren"-Anforderung nicht, aber der wird mir bei anderen Problemen noch nützlich werden.

Man lernt halt nie aus.

[dot]

Ah stimmt. Schonmal überlegt das Ding vielleicht nicht als eigenen Container sondern als Container Adapter anzulegen (ich denk da an sowas wie static_vector<std::array>)? Hätte den Vorteil dass es auf allem funktioniert was random access bietet und du kannst es auch einfach nur temporär über dein Array drüberstülpen wo du's brauchst ohne den Ballast ständig mitzuschleppen...

[CodingCat]

Aus unerfindlichen Gründen war ich gerade eh auf der Suche nach einer hirnlosen Tätigkeit. Für erase() und insert() bin ich aber auch gerade zu faul. :P Dabei fällt mir auf, dass ich diese ganzen Range-Konstruktions- und Destruktionshelfer unbedingt mal für alle Container-Klassen zusammenführen sollte. :(

[Schrompf]

Und so sieht das bei mir aus. Alles strikt STL-kompatibel, das war mir wichtig. Allerdings größtenteils noch ungetestet.

Code: Alles auswählen

template <typename Type, size_t Size>
class TArray
{
protected:
  char array[Size*sizeof( Type)];
  size_t count;
public:
  typedef Type* iterator;
  typedef const Type* const_iterator;

public:
  /// Konstruktor
  TArray() { count = 0; }
  /// Konstruktor mit vorgegebener Füllmenge
  TArray( size_t init_count, const Type& init_value = Type()) { count = 0; resize( init_count, init_value); }

  /// Feldzugriffe
  Type* data() { return reinterpret_cast<Type*> (&array[0]); }
  const Type* data() const { return reinterpret_cast<Type*> (&array[0]); }

  /// Elementzugriffe
  Type& front() { return *data(); }
  const Type& front() const { return *data(); }
  Type& back() { return *(data() + (count-1)); }
  const Type& back() const { return *(data() + (count-1)); }

  /// Elementzugriffe
  Type& operator [] (size_t n) { tassert( n < count); return data()[n]; }
  const Type& operator [] (size_t n) const { tassert( n < count); return data()[n]; }
  Type& at(size_t n) { tassert( n < count); return data()[n]; }
  const Type& at(size_t n) const { tassert( n < count); return data()[n]; }

  /// Iteratoren
  iterator begin() { return data(); }
  const_iterator begin() const { return data(); }
  const_iterator cbegin() const { return data(); }
  iterator end() { return data() + count; }
  const_iterator end() const { return data() + count; }
  const_iterator cend() const { return data() + count; }
  iterator rbegin() { return data() + count-1; }
  const_iterator rbegin() const { return data() + count-1; }
  const_iterator crbegin() const { return data() + count-1; }
  iterator rend() { return data() - 1; }
  const_iterator rend() const { return data() - 1; }
  const_iterator crend() const { return data() - 1; }

  /// Auskünfte
  size_t size() const { return count; }
  size_t max_size() const { return Size; }
  size_t capacity() const { return Size; }
  bool empty() const { return size() == 0; }

  /// Array leeren
  void clear() { while( count > 0 ) pop_back(); }

  // Auf neue Größe einstellen
  void resize( size_t n, const Type& wert) 
  {
    tassert( n <= Size );

    while( n < count )
      pop_back();

    while( n > count )
      push_back( wert);
  }

  /// neues Element anfügen
  void push_back( const Type& wert)
  {
    tassert( count < Size );
    Type* neu = data() + count;
    new (neu) Type( wert);
    count++;
  }
  /// neues Element aus temporärem Objekt
  void push_back( Type&& wert)
  {
    tassert( count < Size );
    Type* neu = data() + count;
    new (neu) Type( wert);
    count++;
  }
  /// letztes Element entfernen
  void pop_back()
  {
    tassert( count > 0 );
    Type* alt = data() + count-1;
    alt->~alt();
    count--;
  }

  /// Ersetzt den Array-Inhalt durch die gegebene Element-Reihe
  template <typename InputIterator>
  void assign( InputIterator first, InputIterator last) { clear(); while( first != last) push_back( *first++); }
  /// Ersetzt den Array-Inhalt durch eine Reihe identischer Elemente
  void assign( size_t n, const Type& wert) { clear(); for( size_t a = 0; a < n; ++a ) push_back( wert); }

  /// Fügt ein Element an der gegebenen Stelle in das Array ein, rückt alle Elemente dahinter um eins nach hinten
  iterator insert( iterator where, const Type& what)
  {
    tassert( count < Size );
    if( where != end() )
    {
      push_back( back());
      auto it = rbegin() - 1;
      while( it != where ) { *it = *(it - 1); --it; }
      *where = what;
    } else
    {
      push_back( what);
    }

    return where;
  }

  /// Fügt eine Reihe identischer Elemente an der gegebenen Stelle in das Array ein, rückt alle Elemente dahinter nach hinten
  void insert( iterator where, size_t n, const Type& what)
  {
    tassert( count + n <= Size );
    if( where != end() )
    {
      size_t nachInten = count - n;
      for( size_t a = 0; a < n; ++a )
        push_back( at( nachInten+a));
      for( size_t a = 0; a < n; ++a )
        *where++ = what;
    } else
    {
      for( size_t a = 0; a < n; ++a )
        push_back( what);
    }
  }

  /// Fügt eine Element-Seria an der gegebenen Stelle in das Array ein, rückt alle Elemente dahinter nach hinten
  template <typename InputIterator>
  void insert( iterator where, InputIterator first, InputIterator last)
  {
    if( where != end() )
    {
      // nachzählen, wieviel wir nach hinten rücken müssen
      InputIterator f = first;
      iterator nachHinten = end();
      while( f != last )
      {
        --nachHinten; ++f;
      }
      // die Elemente ab da hinten anfügen
      f = first;
      while( f != last )
      {
        push_back( *nachHinten++);
        ++f;
      }
      // jetzt den vorne gewonnenen Platz mit der eigentlichen Wunsch-Sequenz überschreiben
      while( first != last )
        *where++ = *first++;
    } else
    {
      while( first != last )
        push_back( *first++);
    }
  }

  iterator erase( iterator where)
  {
    tassert( count > 0 );
    tassert( where >= begin() && where < end() );

    while( where+1 != end() )
      *where++ = *(where + 1);
    pop_back();
  }

  iterator erase( iterator first, iterator last)
  {
    while( last != end() )
      *first++ = *last++;
    while( first != end() )
      pop_back();
  }
};

[EyDu]

Ein eigenen Allocator sollte hier doch eigentlich geeignet sein. Dann sparst du dir das Neuimplementieren der ganzen Funktionalität, abgesehen von den vielleicht gewünschten asserts.

[CodingCat]

Ich gehe einfach mal davon aus, dass du den Code hier auch zum Review reingestellt hast, und kommentiere ein wenig:

• Deine Pseudo-reverse_iterators sind leider nicht strikt STL-kompatibel, sondern in diesem Kontext eher ziemlich schädlich: Echte reverse_iterators laufen bei Inkrement rückwärts, deine laufen jedoch genau wie die normalen forward_iterators vorwärts. Damit löst du in jedem STL-Algorithmus unweigerlich eine Zugriffsverletzung aus. Entweder du wrappst deine Zeiger in einen konformen reverse_iterator-Typ, oder du benennst deine r-Methoden am besten irgendwie um.

• Deine assign()-Methode funktioniert nur für disjunkte Iteratoren. Für volle Konformität müsstest du eine Sonderbehandlung für Fälle wie a.assign(a.begin() + 3, a.end()) einbauen, welche zwar nicht allzu häufig sind, ab und zu aber durchaus in realen Szenarien auftreten. Um mir die Sonderbehandlung sparen zu können, benenne ich diese Methode deshalb gerne einfach mit assign_disjoint().

• Ich dekrementiere der Ausnahmesicherheit wegen die Anzahl der Elemente eines Containers immer vor der eigentlichen Destruktion des Elements, um auch im Falle einer Ausnahme bei der Destruktion (wenngleich eine solche hier eigentlich nicht auftreten sollte) den Container noch in einem vollständig korrekten Zustand zu halten.

• Deine Move-push_back(&&)-Methode erfüllt ihre Aufgabe noch nicht: Erst mit new (neu) Type( std::move(wert) ); verschiebt sie den übergebenen Wert auch wirklich.

• Mit Endzeiger statt Elementzähler könntest du dir einiges an Arithmetik sparen. Darüber bist du dir vermutlich im Klaren, und es spielt auch keine größere Rolle, dennoch sei das hiermit, nicht zuletzt für alle passiven Leser, kurz dokumentiert.

[Schrompf]

Ich gehe einfach mal davon aus, dass du den Code hier auch zum Review reingestellt hast, und kommentiere ein wenig:

Danke, so war's gedacht.

• Deine Pseudo-reverse_iterators sind leider nicht strikt STL-kompatibel, sondern in diesem Kontext eher ziemlich schädlich: Echte reverse_iterators laufen bei Inkrement rückwärts, deine laufen jedoch genau wie die normalen forward_iterators vorwärts. Damit löst du in jedem STL-Algorithmus unweigerlich eine Zugriffsverletzung aus. Entweder du wrappst deine Zeiger in einen konformen reverse_iterator-Typ, oder du benennst deine r-Methoden am besten irgendwie um.

Guter Hinweis. Ich benutze die quasi nie, daher wär mir das so schnell nicht aufgefallen.

• Deine assign()-Methode funktioniert nur für disjunkte Iteratoren. Für volle Konformität müsstest du eine Sonderbehandlung für Fälle wie a.assign(a.begin() + 3, a.end()) einbauen, welche zwar nicht allzu häufig sind, ab und zu aber durchaus in realen Szenarien auftreten. Um mir die Sonderbehandlung sparen zu können, benenne ich diese Methode deshalb gerne einfach mit assign_disjoint().

Stimmt, daran habe ich nicht gedacht. Man müsste das aber recht einfach sicher gestalten können.

• Ich dekrementiere der Ausnahmesicherheit wegen die Anzahl der Elemente eines Containers immer vor der eigentlichen Destruktion des Elements, um auch im Falle einer Ausnahme bei der Destruktion (wenngleich eine solche hier eigentlich nicht auftreten sollte) den Container noch in einem vollständig korrekten Zustand zu halten.

Gute Idee.

• Deine Move-push_back(&&)-Methode erfüllt ihre Aufgabe noch nicht: Erst mit new (neu) Type( std::move(wert) ); verschiebt sie den übergebenen Wert auch wirklich.

Wirklich? Ich dachte, der Typ als RValue-Referenz würde reichen, um dem Compiler klarzumachen, dass der Parameter "weg kann".

• Mit Endzeiger statt Elementzähler könntest du dir einiges an Arithmetik sparen. Darüber bist du dir vermutlich im Klaren, und es spielt auch keine größere Rolle, dennoch sei das hiermit, nicht zuletzt für alle passiven Leser, kurz dokumentiert.

Ich habe das ehrlich gesagt nicht nachgerechnet, aber ich glaub's Dir mal :-) Ich schreibe halt oft noch klassische "for( size_t a = 0; a < container.size(); ++a)"-Schleifen, wenn ich die Indizes für irgendwas brauche. Daher bin ich die "Elemente und Anzahl"-Schreibweise eher gewöhnt.

Ich bau's mal ein und poste eine neue Version. Vielleicht erspart es ja jemandem noch etwas Arbeit.

[CodingCat]

Wirklich? Ich dachte, der Typ als RValue-Referenz würde reichen, um dem Compiler klarzumachen, dass der Parameter "weg kann".

Ja, das wäre das intuitive Verhalten. Auch hier hat das C++-Komitee letztlich jedoch ganze Arbeit geleistet, Sicherheit vor Intuition zu stellen: Ein ganzer Geltungsbereich ist einfach zu viel Raum für versehentliche Falschverwendung, als dass eine automatische Verschiebung bei der ersten verschiebenden Referenzierung einer benannten Referenz sinnvoll wäre. Zumal dieses Verschieben-oder-noch-nicht-Verschieben auch noch abhängig von den Eigenschaften jeweils aufgerufener externen Funktionen wäre, deren Signatur sich jederzeit kaum nachverfolgbar ändern könnte, mit katastrophalen Folgen. Deshalb muss (temporäre!) Verschiebbarkeit jedes Mal erneut explizit bekundet werden, die R-Value-Reference-Syntax in der Parameterliste dient lediglich der Überladungsauflösung.

[Schrompf]

Hm. Ich habe doch mächtig was umschreiben müssen, damit der jetzt einen Enditerator anstatt einer Anzahl benutzt. Unter anderem kann ich mich jetzt nicht mehr auf den automatisch generierten Kopierkonstruktor und Zuweisungsoperator verlassen, weil ja der Zeiger nur für die konkrete Instanz gilt. Unschön.

Ich habe dem Ding dann auch gleich einen Move-Konstruktor und entsprechenden Zuweisungsoperator gegeben. Ich weiß nicht, ob der überhaupt was bringt oder ob das nicht sogar gefährlich ist. Ich übernehme im Move-Konstruktor auch gleich alle Objekte aus dem anderen Array als RValue-Referenzen - ist das ok so oder ein Fehler?

Reverse Iterators habe ich wieder entfernt, weil ich sie eh kaum brauche und keine Lust hatte, dafür jetzt noch Klassen für runterzuschrubben.

assign() sind jetzt eigen-sicher. insert() aber immernoch nicht. Das war mir dann einfach zuviel.

Und eine Kleinigkeit: die Klasse hatte noch keinen Destruktor. Ganz fies, wenn man für In-Place-Construction intern alles mit einem char-Array bestreitet.

[edit] Und nochmal geändert, weil in der Version noch ne Menge Flüchtigkeitsfehler drin waren. Aktuelle Version anbei:

Code: Alles auswählen

template <typename Typ, size_t Groesse>
class TArray
{
protected:
  char mFeld[Groesse*sizeof( Typ)];
  Typ* mEnde;

public:
  typedef Typ* iterator;
  typedef const Typ* const_iterator;

public:
  /// Konstruktor
  TArray() { mEnde = (Typ*) data(); }
  /// Konstruktor mit vorgegebener Füllmenge
  TArray( size_t pAnzahl, const Typ& pWert = Typ()) { mEnde = (Typ*) data(); resize( pAnzahl, pWert); }
  /// Konstruktor von Element-Reihe
  template <typename InputIterator>
  TArray( InputIterator first, InputIterator last) { mEnde = (Typ*) data(); while( first != last ) push_back( *first++); }
  /// Kopierkonstruktor
  TArray( const TArray<Typ, Groesse>& other) { mEnde = (Typ*) data(); *this = other; }
  /// RValue-Konstruktor
  TArray( TArray<Typ, Groesse>&& other) { mEnde = (Typ*) data(); *this = std::move( other); }

  /// Destruktor
  ~TArray() { while( mEnde != begin() ) pop_back(); }

  /// Zuweisung
  TArray<Typ, Groesse>& operator = (const TArray<Typ, Groesse>& other) 
  { 
    if( this == &other )
      return *this;
    clear();
    for( auto it = other.cbegin(); it != other.cend(); ++it )
      push_back( *it); 
    return *this;
  }
  /// RValue-Zuweisung
  TArray<Typ, Groesse>& operator = (TArray<Typ, Groesse>&& other) 
  { 
    if( this == &other )
      return *this;
    clear();
    for( auto it = array.cbegin(); it != array.cend(); ++it )
      push_back( std::move( *it)); 
    other.mEnde = (Typ*) other.data();
    return *this;
  }

  /// Feldzugriffe
  Typ* data() { return reinterpret_cast<Typ*> (&mFeld[0]); }
  const Typ* data() const { return reinterpret_cast<const Typ*> (&mFeld[0]); }

  /// Elementzugriffe
  Typ& front() { return *data(); }
  const Typ& front() const { return *data(); }
  Typ& back() { return *(mEnde-1); }
  const Typ& back() const { return *(mEnde-1); }

  /// Elementzugriffe
  Typ& operator [] (size_t n) { tassert( n < size()); return data()[n]; }
  const Typ& operator [] (size_t n) const { tassert( n < size()); return data()[n]; }
  Typ& at(size_t n) { tassert( n < size()); return data()[n]; }
  const Typ& at(size_t n) const { tassert( n < size()); return data()[n]; }

  /// Iteratoren
  iterator begin() { return data(); }
  const_iterator begin() const { return data(); }
  const_iterator cbegin() const { return data(); }
  iterator end() { return mEnde; }
  const_iterator end() const { return mEnde; }
  const_iterator cend() const { return mEnde; }

  /// Auskünfte
  size_t size() const { return ptrdiff_t( (char*) mEnde - mFeld) / sizeof( Typ); }
  size_t max_size() const { return Groesse; }
  size_t capacity() const { return Groesse; }
  bool empty() const { return size() == 0; }

  /// Array leeren
  void clear() { while( end() != begin() ) pop_back(); }

  // Auf neue Größe einstellen
  void resize( size_t n, const Typ& wert) 
  {
    tassert( n <= Groesse );

    while( n < mAnzahl )
      pop_back();

    while( n > mAnzahl )
      push_back( wert);
  }

  /// neues Element anfügen
  void push_back( const Typ& wert)
  {
    tassert( mEnde != begin() + capacity());
    Typ* neu = mEnde;
    new (neu) Typ( wert);
    mEnde++;
  }
  /// neues Element aus temporärem Objekt
  void push_back( Typ&& wert)
  {
    tassert( mEnde != begin() + capacity());
    Typ* neu = mEnde;
    new (neu) Typ( std::move( wert));
    mEnde++;
  }
  /// letztes Element entfernen
  void pop_back()
  {
    tassert( mEnde != begin() );
    mEnde--;
    mEnde->~Typ();
  }

  /// Ersetzt den Array-Inhalt durch die gegebene Element-Reihe
  template <typename InputIterator>
  void assign( InputIterator first, InputIterator last) 
  { 
    auto myfirst = begin();
    while( myfirst != end() && first != last )
      *myfirst++ = *first++
    // es ist noch was vom eigenen übrig
    while( myfirst != end() )
      pop_back();
    // es ist noch was vom Parameter über
    while( first != last )
      push_back( *first++);
  }

  /// Ersetzt den Array-Inhalt durch eine Reihe identischer Elemente
  void assign( size_t n, const Typ& wert) 
  { 
    auto myfirst = begin();
    ++n;
    while( myfirst != end() && n > 0 )
      *myfirst++ = wert; 
    // es ist noch was vom eigenen Vorher übrig
    while( myfirst != end() )
      pop_back();
    // es ist noch was zum Einfügen übrig
    while( n > 0 )
      push_back( wert);
  }

  /// Fügt ein Element an der gegebenen Stelle in das Array ein, rückt alle Elemente dahinter um eins nach hinten
  iterator insert( iterator where, const Typ& what)
  {
    tassert( mAnzahl < Groesse );
    if( where != end() )
    {
      push_back( back());
      auto it = rbegin() - 1;
      while( it != where ) { *it = *(it - 1); --it; }
      *where = what;
    } else
    {
      push_back( what);
    }

    return where;
  }

  /// Fügt eine Reihe identischer Elemente an der gegebenen Stelle in das Array ein, rückt alle Elemente dahinter nach hinten
  void insert( iterator where, size_t n, const Typ& what)
  {
    tassert( mAnzahl + n <= Groesse );
    if( where != end() )
    {
      auto nachInten = end() - n;
      for( size_t a = 0; a < n; ++a )
        push_back( *nachInten++);
      for( size_t a = 0; a < n; ++a )
        *where++ = what;
    } else
    {
      for( size_t a = 0; a < n; ++a )
        push_back( what);
    }
  }

  /// Fügt eine Element-Serie an der gegebenen Stelle in das Array ein, rückt alle Elemente dahinter nach hinten
  template <typename InputIterator>
  void insert( iterator where, InputIterator first, InputIterator last)
  {
    if( where != end() )
    {
      // nachzählen, wieviel wir nach hinten rücken müssen
      InputIterator f = first;
      iterator nachHinten = end();
      while( f != last )
      {
        --nachHinten; ++f;
      }
      // die Elemente ab da hinten anfügen
      f = first;
      while( f != last )
      {
        push_back( *nachHinten++);
        ++f;
      }
      // jetzt den vorne gewonnenen Platz mit der eigentlichen Wunsch-Sequenz überschreiben
      while( first != last )
        *where++ = *first++;
    } else
    {
      while( first != last )
        push_back( *first++);
    }
  }

  /// Entfernt das benannte Einzel-Element
  iterator erase( iterator where)
  {
    tassert( mAnzahl > 0 );
    tassert( where >= begin() && where < end() );

    while( where+1 != end() )
      *where++ = *(where + 1);
    pop_back();
  }

  /// Entfernt die benannte Elementreihe
  iterator erase( iterator first, iterator last)
  {
    while( last != end() )
      *first++ = *last++;
    while( first != end() )
      pop_back();
  }
};

[EyDu]

Da du einfach über meinen Vorschlag hinweg gegangen bist, habe ich ihn mal selber getestet ;-) Ist alles auf die schnelle implementiert und wahrscheinlich an der einen oder anderen Ecke nicht ganz richtig. Da sollte jemand drauf schauen, der sich mit den Details beser auskennt:

Code: Alles auswählen

template <typename T, size_t MAX_SIZE>
class fixedallocator {
public:
    typedef T value_type;
    typedef T* pointer;
    typedef T & reference;
    typedef const T* const_pointer;
    typedef const T & const_reference;
    typedef size_t size_type;
    typedef std::ptrdiff_t difference_type;
    
    template <typename U>
    struct rebind { typedef fixedallocator<U, MAX_SIZE> other; };
    
    pointer address ( reference x ) const { return mData; }
    const_pointer address ( const_reference x ) const { return mData; }
    pointer allocate (size_type n, std::allocator<void>::const_pointer hint=0) {
        return mData;
    }
    void deallocate (pointer p, size_type n) {}
    size_type max_size() const throw() { return MAX_SIZE; }
    void construct ( pointer p, const_reference val ) { *p = T(val); }
    void destroy (pointer p) { ((T*)p)->~T(); }
    
protected:
    T mData[MAX_SIZE];
};

Die ganzen asserts bekommst du so auch gleich geschenkt.

Sebastian

Edit: Code auf C++ gesetzt.
Edit 2: Vielleicht reicht auch schon das Ableiten von std::vector, so dass capacity auf die maximale Größe gesetzt wird. Dann könnte man den Standardallocator nehmen und müsste nur noch max_size überschreiben.

[Schrompf]

Wenn ich das so sehe, dann scheint ein Allocator auch ein Weg zu sein. Hält sich der Container auch an das max-size()? Meine Furcht war bisher immer, dass der Allocator einfach nach mehr gefragt wird, als er geben kann. Oder zwischendurch eine Reallocation kommt, wo man dann den alten und den neuen Buffer parallel halten muss. All das würde die statische Allokation ja sprengen.

[EyDu]

Ich habe es mir nicht im Code oder in der Spezifikation angesehen, ob das Verhalten definiert ist, aber zu mindest beim g++ wurde vor jedem alloc-Aufruf einmal max_size aufgerufen. Das dies beachtet wird, sieht man dort auch recht gut an der Menge des reservierten Speichers. Hier mal als Beispiel:

Code: Alles auswählen

#include <cstddef>
#include <iostream>
#include <vector>


template <typename T, size_t MAX_SIZE>
class fixedallocator {
public:
    typedef T value_type;
    typedef T* pointer;
    typedef T & reference;
    typedef const T* const_pointer;
    typedef const T & const_reference;
    typedef size_t size_type;
    typedef std::ptrdiff_t difference_type;
    
    template <typename U>
    struct rebind { typedef fixedallocator<U, MAX_SIZE> other; };
    
    pointer address ( reference x ) const { return mData; }
    const_pointer address ( const_reference x ) const { return mData; }
    pointer allocate (size_type n, std::allocator<void>::const_pointer hint=0) {
        std::cout << "allocate = " << n << std::endl;
        return mData;
    }
    void deallocate (pointer p, size_type n) {}
    size_type max_size() const throw() { std::cout << "max_size" << std::endl; return MAX_SIZE; }
    void construct ( pointer p, const_reference val ) { *p = T(val); }
    void destroy (pointer p) { ((T*)p)->~T(); }
    
protected:
    T mData[MAX_SIZE];
};


template <typename T, size_t MAX_SIZE>
class fixedvector : public std::vector<T, fixedallocator<T, MAX_SIZE> > {
public:
    void push_back ( const T& x ) {
        std::cout << x << std::endl;
        std::vector<T, fixedallocator<T, MAX_SIZE> >::push_back(x);
        std::cout << std::endl;
    }
};


int main(int argc, char **argv) {
    fixedvector<int, 10> v;
    for(int i=0; i<20; ++i)
        v.push_back(i);
    
    return 0;
}

liefert

Code: Alles auswählen

0                                                                                                                          
max_size                                                                                                                   
max_size                                                                                                                   
allocate = 1                                                                                                               
                                                                                                                           
1                                                                                                                          
max_size                                                                                                                   
max_size                                                                                                                   
allocate = 2                                                                                                               
                                                                                                                           
2                                                                                                                          
max_size                                                                                                                   
max_size                                                                                                                   
allocate = 4                                                                                                               
                                                                                                                           
3                                                                                                                          
                                                                                                                           
4                                                                                                                          
max_size                                                                                                                   
max_size                                                                                                                   
allocate = 8                                                                                                               
                                                                                                                           
5                                                                                                                          

6

7

8
max_size
max_size
max_size
allocate = 10

9

10
max_size
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_insert_aux
Aborted

[dot]

Interessant wär auch, ob der vector die Elemente nach einer Allokation immer umkopiert (was unnötig ist) und ob definiert ist wie er das macht oder ob es da evtl. zu Problemen kommen kann...

[Schrompf]

Das war auch meine Sorge: allokiert der vector beim Wachsen ein neues Stück Speicher und wirft das alte weg? In dem Fall muss der Allocator beide Speicher parallel halten können, was der statischen Allokation widerspricht.

Ich fühle mich übrigens gerade wie ein Verräter, aber mein statischer Vector ist irgendwie unnötig geworden. Ich habe gegenüber der gestrigen Version noch einige Dummheiten beseitigt und stoße jetzt bereits an die vordefinierten Wachstumsgrenzen. Der Algorithmus dahinter muss prinzipiell damit klar kommen, dass er eben nicht soviele Elemente ablegen kann, wie er will. Und nebenbei habe ich festgestellt, dass ich durch eine Änderung des Vor-Codes nur noch etwa 2000 der Objekte überhaupt habe. 2000 kleine std::vector tun keinem mehr weh... da kann ich mir die komplette Arbeit rund um statische Allokation ersparen. Vorher wären es etwa 500.000 gewesen, da wäre mir das wichtiger gewesen. Aber jetzt... tja.

[dot]

Der Algorithmus dahinter muss prinzipiell damit klar kommen, dass er eben nicht soviele Elemente ablegen kann, wie er will.

Eben darum mein Hinweis in Richtung Ringbuffer: Einfach von hinten wieder drüberschreiben ;)

[Schrompf]

Nein, ich glaube, da meinen wir verschiedene Sachen. Auch beim RingBuffer gehen dann Einträge verloren. Der darüberliegende Algorithmus, der die Daten ablegen will, muss damit klarkommen, dass er nicht alle Daten ablegen kann. Das ist eine meist nicht triviale Einschränkung.

[edit]2ms, um das Wegenetz für ein ganzes Level zu erstellen. Ich glaube, ich habe mir völlig umsonst Gedanken gemacht.

[EyDu]

So wie es aussieht, wird bei jeder Vergrößerung des Containers der gesamte Inhalt kopiert. Da sowohl der copy constructor und release aufgerufen werden, kann hier wahrscheinlich auch nicht getrickst werden. Wenn man die maximale Größer aber so oder so vorher kennt, dann ist das aber eh nicht relevant, da man vorher genug Speicher anfordern kann und dann erst die Elemente einfügt.

Bei meinem Ansatz würde der doppelte Speicher allerdings entfallen, da Quelle und Ziel, wegen der allocate-Methode, gleich sind. Wenn möglich, würde ich einen std::vector verwenden und ein reserve darauf aufrufen. Wie oben bereits vorgeschlagen, sollte das vielleicht noch gekapselt werden. So ist dann auch sichergestellt, dass man ein solches Objekt auch auf dem Stack erstellen kann und diese nicht gleich sprengt.

Zum Problem der Wegsuche: Da du wohl APSP suchst, würde ich diese Lösung verwenden.

[CodingCat]

Hm. Ich habe doch mächtig was umschreiben müssen, damit der jetzt einen Enditerator anstatt einer Anzahl benutzt. Unter anderem kann ich mich jetzt nicht mehr auf den automatisch generierten Kopierkonstruktor und Zuweisungsoperator verlassen, weil ja der Zeiger nur für die konkrete Instanz gilt. Unschön.

Das hatte ich gestern schlichtweg übersehen, aber die automatisch generierten Varianten sind ohnehin immer falsch, weil sie des rohen Speichersegments wegen einfach bitweise Kopien aller Elemente anfertigen, ohne sich um Konstruktion oder Destruktion zu scheren.

Ein eigenen Allocator sollte hier doch eigentlich geeignet sein. Dann sparst du dir das Neuimplementieren der ganzen Funktionalität, abgesehen von den vielleicht gewünschten asserts.

Von der Idee her, ja. In C++ sind Allokatoren für derlei Zwecke jedoch keine gute Wahl. Zum einen sind die STL-Container-Klassen, wie im Verlauf dieses Threads bereits festgestellt, alle ausschließlich auf dynamische Allokation ausgelegt. Reallokationen mit perfiden Hacks von Allocator-Seite aus abzufangen, ist gar keine gute Idee, dafür ist der Allokationsvorgang zu unspezifiziert. Die Vermeidung von nachträglichen Reallokationen durch unmittelbares Aufrufen von reserve() mit der Maximalgröße sollte zwar funktionieren, hinterlässt aber dennoch einen höchst unsicheren Container. So würde swap() zum Beispiel auf Lebenszeit Abhängigkeiten zwischen den zwei vertauschten Container-Objekten schaffen, die Kapazitäten der beiden Containers würden vertauscht, und die Container-Objekte müssten später auf jeden Fall gleichzeitig zerstört werden. Dasselbe gilt für Move Construction und Move Assignment derartiger statischer Container-Instanziierungen.

[CodingCat]

Hier noch einige Anmerkungen, die mir während der Verfassung des vorangegangenen Posts schon wieder entfallen waren, und erst nachträglich zurück in mein Bewusstsein fanden.

Hier mal als Beispiel [...]

Dein Allocator ist in Bezug auf seine Hauptaufgabe, die Speicherverwaltung, noch ziemlich fehlerhaft. Alle Elemente deines Arrays, egal ob bereits reserviert, werden bereits bei der Konstruktion des Allocators voll mit Konstruktoraufruf initialisiert. Dies hast du insofern selbst erkannt, als dass du Elemente in construct() nicht mehr erneut konstruierst, sondern einfach den Zuweisungsoperator aufrufst. Die destruct()-Methode ist jedoch fundamental falsch, deine dortige manuelle Destruktion des Elements führt dazu, dass es bei Destruktion des Allocators am Ende für jedes Element zu einer Doppeldestruktion kommt, welche mit großer Wahrscheinlichkeit zu vielfältigen Access Violations und Corruptions führt, und deinem Programm so ein schmerzhaftes Ende bereitet. Um konsistent mit der construct()-Methode zu bleiben, dürfte die destruct()-Methode überhaupt nichts tun.

Eine bessere Alternative wäre, wie es bereits in diesem Thread in den vorangegangenen Beispielcodes zu sehen war, ein rohes Speichersegment vom Typ char[sizeof(T) * Capacity] anzulegen. Darin würde deine construct()-Methode dann ganz normal, wie in der Spezifikation vorgesehen, mit Placement new ((void*)p) T(v) Elemente auf Anfrage konstruieren, und deine destruct()-Methode diese Elemente, wie schon in deinem fehlerhaften Beispiel, auf Anfrage durch manuellen Destruktoraufruf zerstören.

Ich übernehme im Move-Konstruktor auch gleich alle Objekte aus dem anderen Array als RValue-Referenzen - ist das ok so oder ein Fehler?

Da dein Array in Bezug auf seine Elemente Besitzsemantik hat, ist das vollkommen in Ordnung.

[EyDu]

Hallo CodingCat, vielen Dank für die Anmerkungne und die Kritik. Über die doppelten Destrukturaufrufe hätte ich selber stoplern müssen, den Rest werde ich mir merken, wenn ich mal wieder über ein ähnliches Szenario stolpere. Hast du, oder natürlich auch jemand anderes, vielleicht noch einen Link für mich, in dem der Allokationsvorgang genauer beschrieben wird? Ich habe mal einen Blick in die Spezifikation geworfen, so richtig fündig werde ich dort, abgesehen von den Abschnitten 20.0.15 und20.4.1, allerdings nicht. Was natürlich mit dem bereits angesprochenen relativ unspezifischen Allokationsvorgang zusammen hängen kann.

Sebastian

[Schrompf]

Ich empfand das bisher auch als sehr wertvolle Diskussion, obwohl sie technisch betrachtet eigentlich ergebnislos war. Allokatoren waren mir bisher ein Geheimnis, aber ich sollte mal damit umzugehen lernen.

[CodingCat]

C++11 Update: Aus oben genannten Gründen (move, swap) war die Definition von STL Allocators mit Zustand bis dato praktisch unmöglich. Ein Blick in den neuen Standard zeigt jedoch, dass auch dieses Problem mit C++11 angegangen wurde, und ein Allocator in der Art wie EyDu in vorgeschlagen hat in C++11 tatsächlich wohldefiniert umsetzbar wäre. Der Standard führt hierzu einige (const bool) Flags ein, konkret propagate_on_container_copy_assignment::value, propagate_on_container_move_assignment::value und propagate_on_container_swap::value. Ein Wert von true führt jeweils dazu, dass die entsprechenden Container-Operationen auch an die beteiligten Allocators weitergeleitet werden.

Interessant für Entwickler eigener Bibliotheksklassen ist zudem das allocator_traits-Template. Allocators haben inzwischen dermaßen viele optionale Features, dass die direkte Nutzung übergebener Allocator-Typen ein einziges Spießrutenlaufen wäre. allocator_traits nimmt einen Allocator-Typ und baut daraus automatisch einen vollständigen Allocator, der alle Features implementiert. Im übergebenen Allocator-Typ nicht definierte Features werden mit einiger Template-Magie erkannt und mit Standard-Werten und -Verhaltensweisen aufgefüllt.

[jumphigh]

Anstatt mir STL-konforme Iteratoren selber zusammenzuklöppeln, würde ich zuerst Boost-Iterator versuchen.

MfG
Andreas

[antisteo]

Die Diskussion geht zwar schon eine Weile, aber wie wäre es mit einer fertigen, ordentlichen Lösung?
http://llvm.org/docs/doxygen/html/class ... ector.html

ein

Code: Alles auswählen

llvm::SmallVector<int, 100>

allokiert die ersten 100 Elemente statisch. Sollte wider Erwarten doch mehr benötigt sein, wird auf dynamisch umgeschalten.
Vor allem sind hier die Iteratoren schon korrekt implementiert.
SCNR

[Schrompf]

Nuja, genau nach sowas fragte ich ja im Startbeitrag. Der Code sieht hier und da etwas gewagt aus, dürfte aber getestet sein. Inzwischen sind sie halt von der Zeit überholt worden - die VC++-vector-Implementation macht genau das gleiche, nur halt nicht einstellbar viel. Und wahrscheinlich kann man die auch irgendwo konfigurieren.