vetores STL com armazenamento não inicializado?

Question

Eu estou escrevendo um loop interno que precisa structs colocar em armazém contíguo. Eu não sei quantas dessas structs haverá antes do tempo. Meu problema é vector desse STL inicializa seus valores para 0, então não importa o que eu faço, eu arcar com os custos da inicialização mais o custo da criação membros do struct aos seus valores.

Existe alguma maneira para evitar a inicialização, ou há um STL-como recipiente lá fora, com o armazenamento contígua redimensionável e elementos não inicializadas?

(estou certo de que esta parte das necessidades de código a ser otimizado, e estou certo de que a inicialização é um custo significativo.)

Além disso, veja meus comentários abaixo para um esclarecimento sobre quando a inicialização ocorre.

algum código:

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 inicializar os valores na matriz de alguma forma, o que significa algum construtor (ou cópia construtor) deve ser chamado. O comportamento do vector (ou qualquer classe container) é indefinido se você fosse para aceder à secção não inicializada da matriz como se fosse inicializado.

A melhor maneira é usar reserve() e push_back(), de modo que a cópia-construtor é usado, evitando default-construção.

Usando o código de exemplo:

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

O único problema com a chamada reserve() (ou resize()) como este é que você pode acabar invocando a cópia construtor com mais freqüência do que você precisa. Se você pode fazer uma boa previsão quanto ao tamanho final do array, é melhor reserve() o espaço uma vez no início. Se você não sabe o tamanho final, porém, pelo menos, o número de cópias será mínimo, em média.

Na versão corrente de C ++, o loop interno é um pouco ineficaz como um valor temporário é construído sobre a pilha, copiar-construído para a memória vectores, e finalmente o temporária é destruída. No entanto, a próxima versão do C ++ tem um recurso chamado R-Value referências (T&&) que vai ajudar.

A interface fornecida pela std::vector não permite outra opção, que é usar alguma fábrica-como classe para construir valores diferente do padrão. Aqui está um exemplo aproximada do que esse padrão seria semelhante implementado em 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));
    }
}

Fazer isso significa que você tem que criar sua própria classe vector. Neste caso, também complica o que deveria ter sido um exemplo simples. Mas pode haver momentos em que usando uma função de fábrica como esta é melhor, por exemplo, se a inserção é condicional em algum outro valor, e você teria de outra forma incondicionalmente construir alguns temporária caro, mesmo se não fosse realmente necessário.

Answer 2

C ++ 0x adiciona um novo emplace_back modelo de função de membro para vector (que se baseia em modelos variádicos e de encaminhamento perfeito) que se livrar de quaisquer temporários inteiramente:

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

Answer 3

Para esclarecer sobre a reserva () respostas: você precisa usar de reserva () em conjunto com push_back (). Desta forma, o construtor padrão não é chamado para cada elemento, mas sim o construtor de cópia. Você ainda incorrer na pena de configurar o seu struct na pilha, e depois copiá-lo para o vetor. Por outro lado, é possível que se você usar

vect.push_back(MyStruct(fieldValue1, fieldValue2))

o compilador irá construir a nova instância diretamente nos thatbelongs memória para o vetor. Depende de quão inteligente o otimizador é. Você precisa verificar o código gerado para descobrir.

Answer 4

Em C ++ 11 (e boost) você pode usar a versão gama de unique_ptr para alocar uma matriz não inicializada. Isso não é bem um recipiente STL, mas ainda é gerenciado memória e C ++ -. Ish que vai ser bom o suficiente para muitas aplicações

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

Answer 5

Então aqui está a inserção problema, redimensionamento está chamando, que está fazendo uma construção cópia de um elemento padrão construída para cada um dos elementos adicionados recentemente. Para chegar a este 0 custo você precisa escrever seu próprio construtor padrão e sua própria construtor de cópia como funções vazias. Fazendo isso para o seu construtor de cópia é um idéia muito ruim , porque ele vai quebrar algoritmos de realocação interna de std :: Vector.

Resumo:. Você não vai ser capaz de fazer isso com std :: vector

Answer 6

Err ...

tentar o método:

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

Ele irá permitir que você reservar memória suficiente para os itens x sem inicializar qualquer (o vector ainda está vazio). Assim, não haverá redistribuição até passar por cima de x.

O segundo ponto é que vector não irá inicializar os valores a zero. Você está testando o seu código na depuração?

Após a verificação em g ++, o código a seguir:

#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á os seguintes resultados:

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

A inicialização que você viu foi provavelmente um artefato.

[EDIT] Após o comentário no redimensionamento, modifiquei o código para adicionar a linha de redimensionamento. O redimensionamento efetivamente chama o construtor padrão do objeto dentro do vetor, mas se o construtor padrão não faz nada, então nada é inicializado ... Eu ainda acredito que foi um artefato (eu consegui o primeiro tempo para ter todo o vector zerooed com o seguinte código:

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

Então ... : - /

[EDIT 2] Como já oferecido por Arkadiy, a solução é a utilização de um construtor em linha tendo os parâmetros desejados. Algo como

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

Este provavelmente será embutido em seu código.

Mas você deve de qualquer maneira estudar seu código com um profiler para ter certeza este pedaço de código é o gargalo de sua aplicação.

Answer 7

Use o std :: vector :: reserva () método. Não vai redimensionar o vetor, mas ele vai alocar o espaço.

Answer 8

De seus comentários a outros cartazes, parece que você é deixado com malloc () e amigos. Vector não vai deixar você tem elementos unconstructed.

Answer 9

A partir do seu código, parece que você tem um vetor de estruturas cada um dos quais compreende 2 ints. você poderia passar a usar 2 vetores de inteiros? Então

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

Agora você não pagar para copiar uma estrutura cada vez.

Answer 10

Se você realmente insistir em ter os elementos não inicializado e sacrificar alguns métodos como a frente (), back (), push_back (), o uso boost vector de numérico. Ele permite que você mesmo não preservar elementos existentes ao chamar de redimensionamento () ...

Answer 11

Você pode usar um tipo de invólucro em torno de seu tipo de elemento, com um construtor padrão que não faz nada. Por exemplo:.

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

Para usar:

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

Answer 12

Siga as estruturas também precisam de estar na memória contígua, ou você pode começar afastado com ter um vetor de struct *?

Vectors fazer uma cópia de tudo o que você adicionar a eles, portanto, usando vetores de ponteiros em vez de objetos é uma maneira de melhorar o desempenho.

Answer 13

Eu não acho STL é sua resposta. Você vai precisar rolar o seu próprio tipo de solução usando realloc (). Você vai ter que armazenar um ponteiro e, ou o tamanho ou número de elementos, e usar isso para encontrar onde começar a adicionar elementos após um 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

eu faria algo como:

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

Você precisa definir um ctor para o tipo que é armazenado no memberVector, mas isso é um custo pequeno, uma vez que lhe dará o melhor dos dois mundos; nenhuma inicialização desnecessária é feito e nenhuma realocação vai ocorrer durante o loop.