C++ statischer std::vector<>



  • 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.


Anmelden zum Antworten