Vettori STL con memoria non inizializzata?

Question

Sto scrivendo un ciclo interno che deve essere posizionato structs in memoria contigua.Non so quanti di questi structs ci sarà in anticipo.Il mio problema è che STL vector inizializza i suoi valori su 0, quindi qualunque cosa faccia, sostengo il costo dell'inizializzazione più il costo dell'impostazione del structai loro valori.

Esiste un modo per impedire l'inizializzazione o esiste un contenitore simile a STL con spazio di archiviazione contiguo ridimensionabile ed elementi non inizializzati?

(Sono certo che questa parte del codice debba essere ottimizzata e sono certo che l'inizializzazione abbia un costo significativo.)

Inoltre, vedere i miei commenti qui sotto per chiarimenti su quando avviene l'inizializzazione.

QUALCHE CODICE:

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];
    }
}

Answer 1

std::vector deve inizializzare in qualche modo i valori nell'array, il che significa che è necessario chiamare qualche costruttore (o costruttore di copie).Il comportamento di vector (o qualsiasi classe contenitore) non è definita se si accede alla sezione non inizializzata dell'array come se fosse inizializzata.

Il modo migliore è usare reserve() E push_back(), in modo che venga utilizzato il costruttore di copia, evitando la costruzione predefinita.

Usando il tuo codice di esempio:

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]));
    }
}

L'unico problema con la chiamata reserve() (O resize()) in questo modo potresti finire per invocare il costruttore di copia più spesso del necessario.Se riesci a fare una buona previsione sulla dimensione finale dell'array, è meglio farlo reserve() lo spazio una volta all'inizio.Se non conosci la dimensione finale, almeno il numero di copie sarà in media minimo.

Nella versione attuale di C++, il ciclo interno è un po' inefficiente poiché un valore temporaneo viene costruito nello stack, costruito per copia nella memoria dei vettori e infine il valore temporaneo viene distrutto.Tuttavia la prossima versione di C++ ha una funzionalità chiamata riferimenti R-Value (T&&) che aiuterà.

L'interfaccia fornita da std::vector non consente un'altra opzione, ovvero utilizzare una classe simile a una fabbrica per costruire valori diversi da quelli predefiniti.Ecco un esempio approssimativo di come apparirebbe questo modello implementato in C++:

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));
    }
}

Fare questo significa che devi creare la tua classe vettoriale.In questo caso si complica anche quello che avrebbe dovuto essere un semplice esempio.Ma potrebbero esserci momenti in cui usare una funzione di fabbrica come questa è meglio, ad esempio se l'inserimento è condizionato da qualche altro valore, e altrimenti dovresti costruire incondizionatamente qualche costoso temporaneo anche se non fosse effettivamente necessario.

Answer 2

C++0x aggiunge un nuovo modello di funzione membro emplace_back A vector (che si basa su modelli variadici e inoltro perfetto) che elimina completamente tutti i temporanei:

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

Answer 3

Per chiarire le risposte Reserve():è necessario utilizzare Reserve() insieme a push_back().In questo modo, per ogni elemento non viene chiamato il costruttore predefinito, ma piuttosto il costruttore di copia.Incorri comunque nella penalità di impostare la tua struttura in stack e quindi di copiarla nel vettore.D'altra parte, è possibile che se usi

vect.push_back(MyStruct(fieldValue1, fieldValue2))

il compilatore costruirà la nuova istanza direttamente nella memoria che appartiene al vettore.Dipende da quanto è intelligente l'ottimizzatore.È necessario controllare il codice generato per scoprirlo.

Answer 4

In C++11 (e boost) puoi utilizzare la versione array di unique_ptr per allocare un array non inizializzato.Questo non è proprio un contenitore STL, ma è comunque gestito dalla memoria e in stile C++, il che sarà abbastanza buono per molte applicazioni.

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

Answer 5

Quindi ecco il problema, resize chiama insert, che sta eseguendo una costruzione di copia da un elemento costruito predefinito per ciascuno degli elementi appena aggiunti.Per ottenere questo costo a 0 è necessario scrivere il proprio costruttore predefinito E il proprio costruttore di copia come funzioni vuote.Fare questo al tuo costruttore di copie è a pessima idea perché interromperà gli algoritmi di riallocazione interna di std::vettoriale.

Riepilogo:Non sarai in grado di farlo con std::vettoriale.

Answer 6

Ehm...

prova il metodo:

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

Ti consentirà di riservare memoria sufficiente per x elementi senza inizializzarne nessuno (il tuo vettore è ancora vuoto).Pertanto, non ci sarà riallocazione finché non si supererà x.

Il secondo punto è che il vettore non inizializzerà i valori su zero.Stai testando il tuo codice in debug?

Dopo la verifica su g++, il seguente codice:

#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 ;
}

dà i seguenti risultati:

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

L'inizializzazione che hai visto era probabilmente un artefatto.

[EDIT] Dopo il commento sul ridimensionamento, ho modificato il codice per aggiungere la riga di ridimensionamento.Il ridimensionamento richiama effettivamente il costruttore predefinito dell'oggetto all'interno del vettore, ma se il costruttore predefinito non fa nulla, non viene inizializzato nulla...Credo ancora che fosse un artefatto (sono riuscito la prima volta ad azzerare l'intero vettore con il seguente codice:

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

COSÌ...:-/

[EDIT 2] Come già offerto da Arkadiy, la soluzione è utilizzare un costruttore inline che prende i parametri desiderati.Qualcosa di simile a

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

Questo probabilmente verrà incorporato nel tuo codice.

Ma dovresti comunque studiare il tuo codice con un profiler per essere sicuro che questo pezzo di codice sia il collo di bottiglia della tua applicazione.

Answer 7

Utilizzare il metodo std::vettore::reserve().Non ridimensionerà il vettore, ma allocherà lo spazio.

Answer 8

Dai tuoi commenti ad altri utenti, sembra che ti siano rimasti malloc() e i suoi amici.Vector non ti consentirà di avere elementi non costruiti.

Answer 9

Dal tuo codice, sembra che tu abbia un vettore di strutture, ciascuna delle quali comprende 2 int.Potresti invece usare 2 vettori di int?Poi

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

Ora non pagherai più per copiare una struttura ogni volta.

Answer 10

Se insisti davvero a non inizializzare gli elementi e sacrifichi alcuni metodi come front(), back(), push_back(), utilizza boost vector from numeric .Ti consente anche di non preservare gli elementi esistenti quando chiami resize()...

Answer 11

Puoi utilizzare un tipo wrapper attorno al tuo tipo di elemento, con un costruttore predefinito che non fa nulla.Per esempio.:

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.
};

Usare:

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

Answer 12

Le strutture stesse devono essere in memoria contigua o puoi cavartela con un vettore di struct*?

I vettori creano una copia di tutto ciò che aggiungi loro, quindi utilizzare vettori di puntatori anziché di oggetti è un modo per migliorare le prestazioni.

Answer 13

Non penso che STL sia la tua risposta.Avrai bisogno di creare il tuo tipo di soluzione usando realloc().Dovrai memorizzare un puntatore e la dimensione o il numero di elementi e usarlo per trovare dove iniziare ad aggiungere elementi dopo un realloc().

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;
}

Answer 14

Farei qualcosa del tipo:

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]));
  }
}

È necessario definire un ctor per il tipo memorizzato in memberVector, ma si tratta di un costo ridotto poiché ti darà il meglio di entrambi i mondi;non viene eseguita alcuna inizializzazione non necessaria e durante il ciclo non si verificherà alcuna riallocazione.