STL-Vektoren mit nicht initialisierten Speicher?

StackOverflow https://stackoverflow.com/questions/96579

  •  01-07-2019
  •  | 
  •  

Frage

Ich schreibe eine innere Schleife, die structs in zusammenhängenden Speicher platzieren muss. Ich weiß nicht, wie viele dieser structs wird es vor der Zeit sein. Mein Problem ist, dass STL vector seine Werte auf 0 initialisiert, also egal, was ich tue, ich entstehen die Kosten für die Initialisierung zuzüglich der Kosten für die Mitglieder, um ihre Werte der struct Einstellung.

Gibt es eine Möglichkeit, die Initialisierung zu verhindern, oder gibt es ein STL-ähnlichen Behälter dort mit resizeable zusammenhängenden Speicher und nicht initialisierten Elemente?

(Ich bin sicher, dass dieser Teil des Codes optimiert werden muss, und ich bin sicher, dass die Initialisierung ein signifikant Kosten.)

Auch hierzu finden Sie meine Kommentare unten für eine Klarstellung darüber, wann die Initialisierung auftritt.

Einige Code: 

void GetsCalledALot(int* data1, int* data2, int count) {
    int mvSize = memberVector.size()
    memberVector.resize(mvSize + count); // causes 0-initialization

    for (int i = 0; i < count; ++i) {
        memberVector[mvSize + i].d1 = data1[i];
        memberVector[mvSize + i].d2 = data2[i];
    }
}
War es hilfreich?

Lösung

std::vector müssen die Werte im Array initialisieren irgendwie, die einige Konstruktor (oder Copy-Konstruktor) bedeutet, genannt werden müssen. Das Verhalten von vector (oder einer Container-Klasse) ist nicht definiert, wenn Sie den nicht initialisierten Abschnitt des Arrays zuzugreifen waren, als ob sie initialisiert wurden.

Der beste Weg ist reserve() und push_back() zu verwenden, so dass das Kopie-Konstruktor verwendet wird, default-Konstruktion vermieden werden.

Arbeiten mit dem Beispielcode: 

struct YourData {
    int d1;
    int d2;
    YourData(int v1, int v2) : d1(v1), d2(v2) {}
};

std::vector<YourData> memberVector;

void GetsCalledALot(int* data1, int* data2, int count) {
    int mvSize = memberVector.size();

    // Does not initialize the extra elements
    memberVector.reserve(mvSize + count);

    // Note: consider using std::generate_n or std::copy instead of this loop.
    for (int i = 0; i < count; ++i) {
        // Copy construct using a temporary.
        memberVector.push_back(YourData(data1[i], data2[i]));
    }
}

Das einzige Problem bei Aufruf reserve() (oder resize()) wie das ist, dass Sie die Kopie-Konstruktor öfter aufrufen kann am Ende als Sie benötigen. Wenn Sie eine gute Vorhersage in Bezug auf die endgültige Größe des Arrays zu machen, ist es besser, den Raum einmal am Anfang reserve(). Wenn Sie nicht die endgültige Größe, obwohl nicht bekannt ist, zumindest die Anzahl der Kopien wird im Durchschnitt minimal sein.

In der aktuellen Version von C ++, die innere Schleife ist etwas ineffizient, da ein temporärer Wert auf dem Stapel aufgebaut ist, kopier konstruiert zu den Vektoren Speicher, und schließlich wird die temporäre zerstört wird. Doch die nächste Version von C ++ verfügt über eine Funktion namens R-Wert Referenzen (T&&), die helfen wird.

Die Schnittstelle von std::vector versorgt nicht für eine andere Option ermöglichen, die eine gewisse fabrikähnlichen Klasse zu verwenden ist auf andere Werte als die Standard zu konstruieren. Hier ist ein grobes Beispiel dafür, was dieses Muster wie implementiert in C ++ aussehen würde: 

template <typename T>
class my_vector_replacement {

    // ...

    template <typename F>
    my_vector::push_back_using_factory(F factory) {
        // ... check size of array, and resize if needed.

        // Copy construct using placement new,
        new(arrayData+end) T(factory())
        end += sizeof(T);
    }

    char* arrayData;
    size_t end; // Of initialized data in arrayData
};

// One of many possible implementations
struct MyFactory {
    MyFactory(int* p1, int* p2) : d1(p1), d2(p2) {}
    YourData operator()() const {
        return YourData(*d1,*d2);
    }
    int* d1;
    int* d2;
};

void GetsCalledALot(int* data1, int* data2, int count) {
    // ... Still will need the same call to a reserve() type function.

    // Note: consider using std::generate_n or std::copy instead of this loop.
    for (int i = 0; i < count; ++i) {
        // Copy construct using a factory
        memberVector.push_back_using_factory(MyFactory(data1+i, data2+i));
    }
}

Das Tun bedeutet Sie Ihre eigenen Vektor-Klasse erstellen haben. In diesem Fall erschwert es auch, was ein einfaches Beispiel hätte sein sollen. Aber es kann vorkommen, wo eine Fabrik-Funktion wie dies besser ist, zum Beispiel, wenn der Einsatz auf einem anderen Wert abhängig ist, und Sie müßten sonst bedingungslos einig teure temporären zu konstruieren, selbst wenn es nicht tatsächlich benötigt wird.

Andere Tipps

C ++ 0x fügt eine neue Member-Funktion Vorlage emplace_back vector (die auf variadische Vorlagen und perfekte Weiterleitung beruht), die vollständig aus irgendwelchen Provisorien loswird: 

memberVector.emplace_back(data1[i], data2[i]);

auf Reserve Um klären () Antworten: Sie müssen Reserve () in Verbindung mit push_back () verwenden. Auf diese Weise wird der Standardkonstruktor nicht für jedes Element genannt, sondern die Kopie Konstruktor. Sie entstehen nach wie vor die Strafe Ihrer Struktur auf Stapel einrichten, und kopieren sie dann in den Vektor. Auf der anderen Seite ist es möglich, dass, wenn Sie 

vect.push_back(MyStruct(fieldValue1, fieldValue2))

wird der Compiler die neue Instanz direkt in den Speicher thatbelongs zum Vektor konstruieren. Es hängt davon ab, wie intelligent der Optimierer ist. Sie müssen den generierten Code überprüfen, um herauszufinden.

In C ++ 11 (und Boost) können Sie die Array-Version von unique_ptr verwenden eine nicht initialisierte Array zuzuordnen. Dies ist nicht ein ganz stl Behälter, ist aber noch Speicher verwaltet und C ++ -. Ish, die für viele Anwendungen gut genug sein wird, 

auto my_uninit_array = std::unique_ptr<mystruct[]>(new mystruct[count]);

Hier ist also das Problem, die Größe Einsatz ruft, das für jede der neu hinzugefügten Elemente eine Kopie Konstruktion aus einem Standard aufgebaut Elemente tut. Um dies zu 0 Kosten, die Sie benötigen, um Ihren eigenen Standardkonstruktor und eigenen Copykonstruktor als leere Funktionen zu schreiben. Tut dies Ihrer Kopie Konstruktor ist eine sehr schlechte Idee , weil es std :: vector interne Umschichtung Algorithmen brechen.

Zusammenfassung:. Sie werden in der Lage sein, dies zu tun nicht mit std :: vector

Err ...

versuchen, die Methode: 

std::vector<T>::reserve(x)

Es ermöglicht Ihnen, genügend Speicher für x Artikel zu reservieren, ohne die Initialisierung jeder (Ihr Vektor ist noch leer). Somit wird es keine Umverteilung sein, bis über x zu gehen.

Der zweite Punkt ist, dass Vektor die Werte auf Null nicht initialisiert werden. Sind Sie Testen Sie den Code im Debug?

Nach der Überprüfung auf g ++, den folgenden Code: 

#include <iostream>
#include <vector>

struct MyStruct
{
   int m_iValue00 ;
   int m_iValue01 ;
} ;

int main()
{
   MyStruct aaa, bbb, ccc ;

   std::vector<MyStruct> aMyStruct ;

   aMyStruct.push_back(aaa) ;
   aMyStruct.push_back(bbb) ;
   aMyStruct.push_back(ccc) ;

   aMyStruct.resize(6) ; // [EDIT] double the size

   for(std::vector<MyStruct>::size_type i = 0, iMax = aMyStruct.size(); i < iMax; ++i)
   {
      std::cout << "[" << i << "] : " << aMyStruct[i].m_iValue00 << ", " << aMyStruct[0].m_iValue01 << "\n" ;
   }

   return 0 ;
}

gibt die folgenden Ergebnisse: 

[0] : 134515780, -16121856
[1] : 134554052, -16121856
[2] : 134544501, -16121856
[3] : 0, -16121856
[4] : 0, -16121856
[5] : 0, -16121856

Die Initialisierung Sie sah, war wahrscheinlich ein Artefakt.

[EDIT] Nach dem Kommentar über Resize, modifizierte ich den Code der Resize-Zeile hinzufügen. Die Resize effektiv ruft den Standardkonstruktor des Objekts innerhalb des Vektors, aber wenn der Standardkonstruktor nichts tut, dann wird nichts initialisiert ... Ich glaube immer noch, es war ein Artefakt (konnte ich das erste Mal den ganzen Vektor mit der zerooed haben folgenden Code: 

aMyStruct.push_back(MyStruct()) ;
aMyStruct.push_back(MyStruct()) ;
aMyStruct.push_back(MyStruct()) ;

So ... : - /

[EDIT 2] Wie bereits von Arkadiy angeboten wird, ist die Lösung, die einen Inline-Konstruktor verwenden, um die gewünschten Parameter nehmen. So etwas wie 

struct MyStruct
{
   MyStruct(int p_d1, int p_d2) : d1(p_d1), d2(p_d2) {}
   int d1, d2 ;
} ;

Dies wird wahrscheinlich inlined in Ihrem Code erhalten.

Sie sollten aber auf jeden Fall Ihren Code mit einem Profiler studieren dieses Stück Code, um sicherzustellen, der Engpass Ihrer Anwendung ist.

Mit der std :: vector :: Reserve () -Methode. Es wird nicht die Vektor Größe ändern, aber es wird den Platz zuzuweisen.

Von Ihre Kommentare zu anderen Poster, sieht es aus wie Sie mit malloc sind links () und Freunde. Vector lassen Sie nicht unkonstruierten Elemente haben.

Von Ihrem Code, es sieht aus wie ein Vektor von Strukturen haben jeweils 2 Ints umfasst. Könnten Sie stattdessen zwei Vektoren von Ints verwenden? Dann 

copy(data1, data1 + count, back_inserter(v1));
copy(data2, data2 + count, back_inserter(v2));

Jetzt zahlen Sie keine Struktur jedes Mal zum Kopieren.

Wenn Sie wirklich darauf bestehen, die Elemente nicht initialisierten mit und opfern einige Methoden wie vorne (), Rücken (), push_back (), verwenden boost Vektor von numerischen. Es erlaubt Ihnen auch nicht zu erhalten Elemente vorhanden ist, wenn () aufgerufen wird die Größe ...

Sie können einen Wrapper um den Elementtyp, mit einem Standard-Konstruktor verwenden, die nichts tut. Z. 

template <typename T>
struct no_init
{
    T value;

    no_init() { static_assert(std::is_standard_layout<no_init<T>>::value && sizeof(T) == sizeof(no_init<T>), "T does not have standard layout"); }

    no_init(T& v) { value = v; }
    T& operator=(T& v) { value = v; return value; }

    no_init(no_init<T>& n) { value = n.value; }
    no_init(no_init<T>&& n) { value = std::move(n.value); }
    T& operator=(no_init<T>& n) { value = n.value; return this; }
    T& operator=(no_init<T>&& n) { value = std::move(n.value); return this; }

    T* operator&() { return &value; } // So you can use &(vec[0]) etc.
};

So verwenden: 

std::vector<no_init<char>> vec;
vec.resize(2ul * 1024ul * 1024ul * 1024ul);

Sind die Strukturen selbst in zusammenhängenden Speicher sein müssen, oder können Sie mit mit einem Vektor von struct * wegkommen?

Vectors machen eine Kopie von was auch immer Sie sie hinzufügen, so Vektoren von Zeigern, anstatt Objekte ist eine Möglichkeit, die Leistung zu verbessern.

Ich glaube nicht, STL ist Ihre Antwort. Sie gehen müssen Ihre eigene Art von Lösung rollen realloc () verwenden. Sie werden einen Zeiger speichern und entweder die Größe oder die Anzahl der Elemente, und dass dort, wo Elemente nach einer realloc beginnen zu finden, benutzen Sie das Hinzufügen (). 

int *memberArray;
int arrayCount;
void GetsCalledALot(int* data1, int* data2, int count) {
    memberArray = realloc(memberArray, sizeof(int) * (arrayCount + count);
    for (int i = 0; i < count; ++i) {
        memberArray[arrayCount + i].d1 = data1[i];
        memberArray[arrayCount + i].d2 = data2[i];
    }
    arrayCount += count;
}

Ich würde so etwas wie: 

void GetsCalledALot(int* data1, int* data2, int count)
{
  const size_t mvSize = memberVector.size();
  memberVector.reserve(mvSize + count);

  for (int i = 0; i < count; ++i) {
    memberVector.push_back(MyType(data1[i], data2[i]));
  }
}

Sie benötigen einen Ctor für den Typen zu definieren, die in der memberVector gespeichert ist, aber das sind ein klein Kosten, wie es Ihnen das Beste aus beiden Welten geben; keine unnötige Initialisierung erfolgt und keine Umverteilung während der Schleife auftreten.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top