C++ statischer std::vector<>



  • Hallo Zusammen,

    für meine Anwendungen benötige ich eine art statischen std::vector<>. Statisch in dem Sinne, dass der Speicher nicht dynamisch allokiert werden soll sondern statisch.

    Im Endeffekt sollte der Container iteratoren (begin(), end()), wahlfreien Zugriff sowie push_back() und erase() unterstützen sowie mit der for ( : ) schleife genutzt werden können.

    Dazu habe ich zwei Ideen:

    1. Es gibt eine open source standard Lösung für das Problem? Falls ja, wäre ich für Hinweise dankbar.

    2. Man legt selbst Hand an und implementiert einen static_vector<> der praktisch komplett auf dem std::array<> basiert, aber mit ein wenig Logik noch eine push_back() und erase() funktion ermöglicht.

    Leider weiß ich nicht was nötig ist, um die for ( : ) Schleifen nutzen zu können? Was müsste man hier alles implementieren?

    Zum Hintergrund: ich möchte in embedded Anwendungen nicht gänzlich auf die Container Funktionen verzichten, gleichzeitig aber keine dynamische allokation durch die std::vector<> container. Generelle Annahme: ein ausreichend groß dimensionierter static_vector<> ist stets ausreichen.

    Vielen Dank schon mal!



  • Ich kenne nur Implementierungen, die auf dem Stack allozieren (anstatt auf dem Heap). Aber muss natuerlich nicht heissen, dass es das nicht gibt 😉

    Eine Moeglichkeit ist einen eigenen Allocator fuer std::vector zu schreiben. Die Strategie waere dann wie folgt: In deinem Programm hast du irgendwo einen grossen, statischen Buffer (char buf[MAX_SIZE]) und der Allocator holt bei Bedarf Speicher aus diesem Buffer.



  • Hallo icarus2,

    die Idee an sich gefällt mir recht gut! Aber hier gleich ne doofe Frage, wie macht man das denn 🙂 gibt es irgendwo eine Zusammenfassung was dafür zu tun ist? Die cppreference hab ich mir angesehen, ist mir ad hoc aber etwas zu abstrakt um es zu verstehen leider 😞

    Vielen Dank.



  • Es gibt da irgendwo ein Video von Alexandrecu, wo er mal was über Allocatoren erzählt... -> https://www.youtube.com/watch?v=LIb3L4vKZ7U

    Zu deiner anderen Frage, was es für die range-for-Loop braucht: ganz einfach, du musst nur eine begin und eine end-Funktion definieren. Entweder in der Klasse drin oder alternativ auch als freie Funktion.

    Eine ganz naive eigene Implementierung hätte ich mir dann so vorgestellt (nicht wirklich getestet, kompiliert aber zumindest):

    template <typename T, size_t capacity>
    class static_vector {
        char storage[sizeof(T) * capacity];
        size_t size = 0;
    public:
        void push_back(T value);
        void pop_back();
        T& operator[](size_t index);
        T* begin();
        T* end();
    };
    
    template<typename T, size_t capacity> 
    void static_vector<T, capacity>::push_back(T value)
    {
        new (&storage[sizeof(T) * size]) T;
        (*this)[size++] = value;
    }
    
    template<typename T, size_t capacity> 
    void static_vector<T, capacity>::pop_back()
    {
        (*this)[--size].~T();
    }
    
    template<typename T, size_t capacity> 
    T& static_vector<T, capacity>::operator[](size_t index)
    {
        return (reinterpret_cast<T*>(&storage))[index];
    }
    
    template<typename T, size_t capacity> 
    T* static_vector<T, capacity>::begin()
    {
        return &operator[](0);
    }
    
    template<typename T, size_t capacity> 
    T* static_vector<T, capacity>::end()
    {
        return &operator[](size);
    }
    

    Da man hier auch noch die const-Varianten, emplace, dies und das machen würde, ist die Idee mit dem Allokator vermutlich besser.



  • Hallo Zusammen,

    das mit dem Allocator habe ich mir mal angesehen. Ein paar offene Fragen habe ich da leider noch.

    Zum einen muss ich wenn ich den Vector mit meinem allocator erstellen will, den typ des allocators mit angeben:

    MyAllocator<int> intAlloc;
    std::vector<int, MyAllocator<int>> v { intAlloc };
    

    Wenn ich jetzt aber eine Methode schreiben möchte:

    int sum(vector<int> &v) {
     ...
    }
    

    Dann meckert mir der Compiler, weil der vector Typ nicht passt. Das finde ich nicht so schön, weil ich dann allen Funktionen die einen vector bekommen sollen noch den allocator typ mitgeben müsste also im Endeffekt:

    int sum(vector<int, MyAllocator<int>> &v) {
     ...
    }
    

    Wenn ich das richtig interpretiere, benötige ich für jeden typ der erzeugt werden soll einen eigenen allocator? Oder sehe ich das hier falsch?

    Ich hätte gerne den einen allocator geschrieben, der den Speicher aus einem statischen array holt und dann von einem vector einfach verwendet wird. Ich hätte gehofft, man kann dem vector beim erzeugen einfach den allocator übergeben und der Rest läuft dann wie gehabt. Also im Endeffekt:

    std::vector<int> v { MyAllocatorInstance };
    

    Ist es überhaupt möglich, dies zu erreichen?

    Vielen Dank!



  • template< typename T, typename Allocator >
    auto sum( std::vector< T, Allocator > &v ) // ...
    

    ftw.

    ... besser aber einfach ein Iteratorenpaar übergeben.



  • Hi Swordfish,

    daran dachte ich auch, die Idee mit den Iteratoren-Paar gefällt mir aber noch besser..

    Jetzt bleibt nur noch die Sache mit den vielen Allokatoren...

    Beispiel:

    SimpleAllocator<int> intAllocator;
    // ...
    int main() {
      std::vector<int, SimpleAllocator<int>> iVec {intAllocator};
      std::vector<double, SimpleAllocator<double>> iVec {intAllocator}; // ERROR, ich benötige einen <double> allocator
    }
    

    Ich verstehe wo das Problem liegt, aber kann man das noch lösen? Ich möchte ja nur einen allocator haben, welcher sich aus einem großen statischen Speicherbereich bedient.

    Eine spontane Idee wäre eine MyAllocator Klasse zu schreiben, welche selbst keinen Speicher hält sondern einen globalen Allokator benutzt, welcher letztendlich den großen statischen Speicherbereich verwaltet.

    Also pseudo code mäßig:

    template <typename T>
    MyAllocator() {
    ...
       alloc() { staticMemManager::allocate(...); }
    ...
    }
    
    int main() {
      std::vector<int, MyAllocator<int>> v { MyAllocator<int>() };
    }
    

    Könnte das funktionieren? Gibt es bessere Möglichkeiten?

    Vielen Dank und Grüße!



  • Warum nicht einfach std::array nehmen und wegen der fehlenden benötigten Funktionen evtl eine Klasse darum bauen ? Das wird statisch angelegt.



  • wenns nur für embedded reichen muss, wieso dann nicht einfach ::new[] und ::new überladen?

    Ich möchte ja nur einen allocator haben, welcher sich aus einem großen statischen Speicherbereich bedient.

    finde ich an und für sich ziemlich hässlich.
    schon alleine, weil du dann entweder reserve am anfang aufrufen musst oder bis zu doppelt so viel speicher brauchst, wie du nutzt...
    abgesehen davon musst du natürlich noch ans alignment denken.



  • Hallo Zusammen,

    ich denke es wird tatsächlich auf eine Eigen-Implementierung von einem static_vector<> hinauslaufen. Ich habe mir noch mal den std::vector<> angesehen und selbst mit einem eigenen allocator kommt mir hier das ::new deutlich zu oft vor, das ist für embedded nichts.

    Der Container muss zunächst ja auch nur mal die Basisfunktionalität beinhalten. Viele Sachen sollten verhältnismäßig schnell zu realisieren sein.

    Eine Frage habe ich aber noch, in der Implementierung von wob wird ein char array genutzt um den Speicher vorzuhalten und anschließend mit

    reinterpret_cast<>
    

    gearbeitet. Wo liegt hier der Vorteil? Was spricht denn gegen ein

    T memory[SIZE]
    

    ? (So hätte ich das nämlich spontan gemacht).

    Vielen Dank und Grüße!



  • Probiere es doch mal mit dieser Klasse aus:

    struct X {
        X() { std::cout << "Erstelle Objekt\n"; }
        ~X() { std::cout << "Zerstöre Objekt\n"; }
    };
    


  • Hallo Wob,

    habe ich gemacht, ich denke die Schwäche liegt darin, dass beim Erzeugen des Containers bereits alle Instanzen erzeugt werden.

    Das muss ich tatsächlich ändern... 🙂

    Danke 🙂



  • Hallo Zusammen,

    eine Frage habe ich noch zum push_back().

    template<typename T, std::size_t SIZE>
    inline void static_vector<T, SIZE>::push_back(const T &value)
    {
      new (&m_dataStorage[sizeof(T) * m_size]) T;
      (*this)[m_size++] = value;
    }
    

    Ist die Zeile

    new (&m_dataStorage[sizeof(T) * m_size]) T;
    

    notwendig? Weil die Zeile macht es mir nicht möglich folgendes Beispiel zu kompilieren, weil es keinen Default Constructor gibt. Ich hätte erwartet, dass auch ohne diese Zeile die Daten einfach an den Speicher kopiert werden.

    #include "static_vector.hpp"
    #include <iostream>
    
    struct SomeType {
      int m_param;
    
      void sayHello(){ std::cout << "Hello from " << m_param << " at " << this << std::endl; }
    
      SomeType(int param) : m_param(param) { std::cout << "Constructed: " << param << " at " << this << std::endl; }
      ~SomeType() { std::cout << "Destructed: " << m_param << " at " << this << std::endl; }
    
    };
    
    void someFunction() {
      std::cout << "\n\nEnter some function" << std::endl;
    
      static_vector<SomeType, 3> sv;
    
      std::cout << "\n\nPush them" << std::endl;
    
      sv.push_back(SomeType(1));
      sv.push_back(SomeType(2));
    
      std::cout << "\n\nLets say hello" << std::endl;
    
      for (auto &a : sv)
        a.sayHello();
    
      std::cout << "\n\nLets pop them" << std::endl;
    
      sv.pop_back();
      sv.pop_back();
    
      std::cout << "\n\nLeave some function" << std::endl;
    }
    
    int main() {
      someFunction();
    
      std::cin.get();
    }
    

    Die Ausgabe - wenn man oben genannte Zeile weg lässt - lautet:

    Enter some function
    
    Push them
    Constructed: 1 at 003AF908
    Destructed: 1 at 003AF908
    Constructed: 2 at 003AF8FC
    Destructed: 2 at 003AF8FC
    
    Lets say hello
    Hello from 1 at 003AFA04
    Hello from 2 at 003AFA08
    
    Lets pop them
    Destructed: 2 at 003AFA08
    Destructed: 1 at 003AFA04
    
    Leave some function
    

    Viele Grüße!



  • Was ist daran falsch? Da hast Du die statische allokation und bereits eine Menge anderer Funktionalität out-of-the-box



  • starseed84 schrieb:

    Ist die Zeile

    new (&m_dataStorage[sizeof(T) * m_size]) T;
    

    notwendig?

    Was hat denn die Zeile für einen Effekt? Wenn Du das beantwortest, hast Du auch die Antwort auf Deine Frage.

    ~Wahrscheinlich suchst du placement-new?~



  • Hallo Swordfish,

    im Endeffekt ist es ein placement new, sprich, das new holt sich vor-allokierten Speicher von einer Adresse (in unserem Fall das char array) und konstruiert hier ein neues Objekt.

    Ich verstehe nur nicht ganz wieso ich es benötige 🙂 schließlich wird ja der Zuweisungsoperator genutzt. Eigentlich sollte dieser ja alles was in Objekt A (an 0xABCD) steht, eben an die Adresse von Objekt B (0xCDEF) in unserem Array kopieren. Ob an der Adresse dann in wirklichkeit ein char array mit wilden Daten liegt dürfte doch egal sein?

    Das emplacement new würde das Objekt an 0xCDEF eben zuerst konstruieren, aber am Ende würde es ja trotzdem durch den Zuweisungsoperator überbügelt werden?

    Der Nachteil an der Sache mit dem emplacement new ist, dass es nur dann geht, wenn T einen Default Konstruktor besitzt 😞

    Viele Grüße



  • starseed84 schrieb:

    ich denke es wird tatsächlich auf eine Eigen-Implementierung von einem static_vector<> hinauslaufen. Ich habe mir noch mal den std::vector<> angesehen und selbst mit einem eigenen allocator kommt mir hier das ::new deutlich zu oft vor, das ist für embedded nichts.

    Ich hab den Thread zwar nur überflogen, aber ich denke wenn du an diesem Punkt angelangt bist, kann vielleicht auch die SmallVector-Implementierung des LLVM-Projekts eine Inspirationsquelle sein.
    Ich bin darauf durch diesen Vortrag aufmerksam geworden. SmallVector ist jedoch kein reiner "statischer Vektor", sondern eine hybride Datenstruktur: SmallVector<T, N> speichert bis zu N Elemente
    auf dem Stack, kann jedoch auch größer werden und mutiert dann transparent zu einem dynamischen Array auf dem Heap - ein wenig wie die Small String Optimization die man in diversen std::string -
    Implementierungen findet. SmallVector verwendet allerdings eine etwas fragwürdige Methode um ohne Polymorphie, sondern lediglich mit gewolltem Object Slicing nur über die Basisklasse (ohne den
    Template-Parameter N ) auf den Vektor zugreifen zu können (nützlich um sich bei Funktionsparametern keinen Kopf darüber machen zu müssen, ob es sich um einen Stack- oder einen Heap-Vektor
    handelt). Wenn man ein Auge zudrückt, kann man das (in diesem Fall Chris Lattner, von dem der fragliche Commit stammt) aber noch gerade so durchgehen lassen.

    T memory[SIZE];
    

    Was den automatischen Speicher angeht, würde ich allerdings eher folgenden Member empfehlen:

    std::aligned_storage_t<sizeof(T), alignof(T)> elements[N];
    

    So ist sichergestellt, dass die Datenstruktur auch mit ungewöhnlicheren Alignments klar kommt. Das Placement- new muss natürlich an den entsprechenden Stellen in einer Schleife für jedes Vektor-Element
    aufgerufen werden. Wenn du sogar zulassen willst, dass die Konstruktoren von T Exceptions werfen können, wird es sogar noch etwas umfangreicher: In diesem Fall must du auch sicherstellen, dass wenn
    z.B. das 10. Element eine Exception wirft, die ersten 9 Elemente zerstört werden, indem du manuell ihren Destruktor aufrufst. Ein selbstgestrickter Vektor von Bibliotheks-Qualität ist auf jeden Fall etwas
    mehr Aufwand, als es auf den ersten Blick den Anschein macht.

    starseed84 schrieb:

    Hallo Swordfish,

    im Endeffekt ist es ein placement new, sprich, das new holt sich vor-allokierten Speicher von einer Adresse (in unserem Fall das char array) und konstruiert hier ein neues Objekt.

    Ich verstehe nur nicht ganz wieso ich es benötige 🙂 schließlich wird ja der Zuweisungsoperator genutzt. Eigentlich sollte dieser ja alles was in Objekt A (an 0xABCD) steht, eben an die Adresse von Objekt B (0xCDEF) in unserem Array kopieren. Ob an der Adresse dann in wirklichkeit ein char array mit wilden Daten liegt dürfte doch egal sein?

    Nein, das würde nicht mit beliebigen Objekten funktionieren. Es ist nicht garantiert, dass der Zuweisungsoperator tatsächlich alles kopiert was das Objekt in einen konsistenten Zustand bringt. T könnte
    z.B. auch Member haben die spezifisch für die Instanz sind und bei einer Zuweisungsoperation nicht mitkopiert werden - z.B. einen Mutex. Man kann allerdings spezielle Optimierungen implementieren, z.B.
    für Objekte, für die std::is_trivially_copyable<T>::value wahr ist. In diesem Fall lassen sich die Objekte mit einem simplen std::memcpy kopieren. Der allgemeingültige Weg ist allerdings über einen
    Kopier/Move-Konstruktor, oder einen Default-Konstruktor mit anschliessender Zuweisung.


Log in to reply