c++ - ¿Cómo puedo evitar std:: vector<> para inicializar todos sus elementos?

optimization gcc

Question

EDITAR: edité tanto la pregunta como su título para ser más precisos.

Teniendo en cuenta el siguiente código fuente:

#include <vector>
struct xyz {
    xyz() { } // empty constructor, but the compiler doesn''t care
    xyz(const xyz& o): v(o.v) { } 
    xyz& operator=(const xyz& o) { v=o.v; return *this; }
    int v; // <will be initialized to int(), which means 0
};

std::vector<xyz> test() {
    return std::vector<xyz>(1024); // will do a memset() :-(
}

... ¿cómo puedo evitar que la memoria asignada por el vector <> se inicialice con copias de su primer elemento, que es una operación O (n) que prefiero omitir por motivos de velocidad, ya que mi constructor predeterminado no hace nada? ?

Una solución específica de g ++ funcionará, si no existe una genérica (pero no pude encontrar ningún atributo para hacerlo).

EDITAR : el código generado sigue (línea de comando: arm-elf-g ++ - 4.5 -O3 -S -fno-verbose-asm -o - test.cpp | arm-elf-c ++ filt | grep -vE ''^ [[: espacio:]] + [. @]. * $ '')

test():
    mov r3, #0
    stmfd   sp!, {r4, lr}
    mov r4, r0
    str r3, [r0, #0]
    str r3, [r0, #4]
    str r3, [r0, #8]
    mov r0, #4096
    bl  operator new(unsigned long)
    add r1, r0, #4096
    add r2, r0, #4080
    str r0, [r4, #0]
    stmib   r4, {r0, r1}
    add r2, r2, #12
    b       .L4          @
.L8:                     @
    add     r0, r0, #4   @
.L4:                     @
    cmp     r0, #0       @  fill the memory
    movne   r3, #0       @
    strne   r3, [r0, #0] @
    cmp     r0, r2       @
    bne     .L8          @
    str r1, [r4, #4]
    mov r0, r4
    ldmfd   sp!, {r4, pc}

EDITAR: En aras de la integridad, aquí está el conjunto para x86_64:

.globl test()
test():
LFB450:
    pushq   %rbp
LCFI0:
    movq    %rsp, %rbp
LCFI1:
    pushq   %rbx
LCFI2:
    movq    %rdi, %rbx
    subq    $8, %rsp
LCFI3:
    movq    $0, (%rdi)
    movq    $0, 8(%rdi)
    movq    $0, 16(%rdi)
    movl    $4096, %edi
    call    operator new(unsigned long)
    leaq    4096(%rax), %rcx
    movq    %rax, (%rbx)
    movq    %rax, 8(%rbx)
    leaq    4092(%rax), %rdx
    movq    %rcx, 16(%rbx)
    jmp     L4          @
L8:                     @
    addq    $4, %rax    @
L4:                     @
    testq   %rax, %rax  @ memory-filling loop
    je      L2          @
    movl    $0, (%rax)  @
L2:                     @
    cmpq    %rdx, %rax  @
    jne     L8          @
    movq    %rcx, 8(%rbx)
    movq    %rbx, %rax
    addq    $8, %rsp
    popq    %rbx
    leave
LCFI4:
    ret
LFE450:
EH_frame1:
LSCIE1:
LECIE1:
LSFDE1:
LASFDE1:
LEFDE1:

EDIT: Creo que la conclusión es no usar std::vector<> cuando se quiere evitar una inicialización innecesaria. Terminé de desenrollar mi propio contenedor con plantilla, que funciona mejor (y tiene versiones especializadas para neon y armv7).

Answer 1

Con la forma en que se declara su struct en este momento, no hay ningún mecanismo para inicializar por defecto el miembro int de su estructura, por lo tanto, obtiene el comportamiento predeterminado de C, que es una inicialización indeterminada. Para inicializar la variable miembro int con un valor de inicialización predeterminado, tendría que agregarla a la lista de inicialización del constructor de la estructura. Por ejemplo,

struct xyz {
    xyz(): v() { } //initialization list sets the value of int v to 0
    int v;
};

Mientras

struct xyz {
    xyz(): { } //no initialization list, therefore ''v'' remains uninitialized
    int v;
};

Answer 2

Envuelves todas tus primitivas en una estructura:

struct IntStruct
{
    IntStruct();

    int myInt;
}

con IntStruct () definido como un constructor vacío. Así declaras v como IntStruct v; por lo tanto, cuando un vector de xyzs todo el valor de inicialización, todo lo que hacen es el valor de inicialización v que es un no-op.

EDITAR: He leído mal la pregunta. Esto es lo que debe hacer si tiene un vector de tipos primitivos, porque vector se define para inicializar con valor al crear elementos a través del método resize() . Las estructuras no están obligadas a inicializar con valor sus miembros en la construcción, aunque estos valores "no inicializados" todavía pueden establecerse en 0 por otra cosa: bueno, podrían ser cualquier cosa.

Answer 3

Este es un rincón extraño del vector . El problema no es que su elemento se esté inicializando con valor ... es que el contenido aleatorio en el primer elemento prototípico se copia a todos los demás elementos del vector. (Este comportamiento cambió con C ++ 11, cuyo valor inicializa cada elemento).

Esto se hace (/ se hizo) por una buena razón: considere algún objeto de referencia contado ... si construye un vector solicitando 1000 elementos inicializados para tal objeto, obviamente desea un objeto con un recuento de referencia de 1000, en lugar de tener 1000 "clones" independientes. Digo "obviamente" porque haber hecho la referencia del objeto contada en primer lugar implica que eso es altamente deseable.

De todos modos, ya casi no tienes suerte. Efectivamente, el vector se asegura de que todos los elementos sean iguales, incluso si el contenido que se está sincronizando es basura no inicializada.

En la tierra de los hackers felices específicos de g ++ no estándar, podemos explotar cualquier función miembro pública con plantilla en la interfaz vector como una puerta trasera para cambiar los datos de miembros privados simplemente especializando la plantilla para un nuevo tipo.

ADVERTENCIA : no solo para esta "solución", sino para todo este esfuerzo para evitar la construcción predeterminada ... no haga esto para los tipos con invariantes importantes : rompe la encapsulación y puede tener un vector propio o alguna operación que intente invocar operator=() , constructores de copia y / o destructores donde *this / lado izquierdo y / o derecho no respetan esos invariantes. Por ejemplo, evite los tipos de valor con punteros que espera que sean NULL o para objetos válidos, contadores de referencia, manejadores de recursos, etc.

#include <iostream>
#include <vector>

struct Uninitialised_Resize
{
    explicit Uninitialised_Resize(int n) : n_(n) { }
    explicit Uninitialised_Resize() { }
    int n_;
};

namespace std
{
    template <>
    template <>
    void vector<int>::assign(Uninitialised_Resize ur, Uninitialised_Resize)
    {
        this->_M_impl._M_finish = this->_M_impl._M_start + ur.n_;

        // note: a simpler alternative (doesn''t need "n_") is to set...
        //   this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
        // ...which means size() will become capacity(), which may be more
        // you reserved() (due to rounding; good) or have data for
        // (bad if you have to track in-use elements elsewhere,
        //  which makes the situation equivalent to just reserve()),
        // but if you can somehow use the extra elements then all''s good.
    }
}

int main()
{
    {
        // try to get some non-0 values on heap ready for recycling...
        std::vector<int> x(10000);
        for (int i = 0; i < x.size(); ++i)
            x[i] = i;
    }

    std::vector<int> x;
    x.reserve(10000);
    for (int i = 1; i < x.capacity(); ++i)
        if (x[0] != x[i])
        {
            std::cout << "lucky/n";
            break;
        }
    x.assign(Uninitialised_Resize(1000), Uninitialised_Resize());

    for (int i = 1; i < x.size(); ++i)
        if (x[0] != x[i])
        {
            std::cout << "success [0] " << x[0] << " != [" << i << "] "
                << x[i] << ''/n'';
            break;
        }
}

Mi salida:

lucky
success [0] 0 != [1] 1

Esto sugiere que el nuevo vector se reasignó al montón que el primer vector lanzó cuando se salió del alcance, y muestra que los valores no están obstruidos por la asignación. Por supuesto, no hay forma de saber si otras invariantes de clase importantes se han invalidado sin inspeccionar las fuentes vector mucho cuidado, y los nombres / importes exactos de los miembros privados pueden variar en cualquier momento ...

Answer 4

La inicialización de los elementos asignados se controla mediante el argumento de la plantilla Asignador. Si necesita personalizarlo, personalícelo. Pero recuerde que esto puede ser fácilmente enrollado en el ámbito de la piratería sucia, así que use con precaución. Por ejemplo, aquí hay una solución bastante sucia. Evitará la inicialización, pero lo más probable es que sea peor en el rendimiento, pero en aras de la demostración (¡como la gente ha dicho que esto es imposible! ... ¡imposible no está en el vocabulario de un programador de C ++!):

template <typename T>
class switch_init_allocator : public std::allocator< T > {
  private:
    bool* should_init;
  public:
    template <typename U>
    struct rebind {
      typedef switch_init_allocator<U> other;
    };

    //provide the required no-throw constructors / destructors:
    switch_init_allocator(bool* aShouldInit = NULL) throw() : std::allocator<T>(), should_init(aShouldInit) { };
    switch_init_allocator(const switch_init_allocator<T>& rhs) throw() : std::allocator<T>(rhs), should_init(rhs.should_init) { };
    template <typename U>
    switch_init_allocator(const switch_init_allocator<U>& rhs, bool* aShouldInit = NULL) throw() : std::allocator<T>(rhs), should_init(aShouldInit) { };
    ~switch_init_allocator() throw() { };

    //import the required typedefs:
    typedef typename std::allocator<T>::value_type value_type;
    typedef typename std::allocator<T>::pointer pointer;
    typedef typename std::allocator<T>::reference reference;
    typedef typename std::allocator<T>::const_pointer const_pointer;
    typedef typename std::allocator<T>::const_reference const_reference;
    typedef typename std::allocator<T>::size_type size_type;
    typedef typename std::allocator<T>::difference_type difference_type;

    //redefine the construct function (hiding the base-class version):
    void construct( pointer p, const_reference cr) {
      if((should_init) && (*should_init))
        new ((void*)p) T ( cr );
      //else, do nothing.
    };
};

template <typename T>
class my_vector : public std::vector<T, switch_init_allocator<T> > {
  public:
    typedef std::vector<T, switch_init_allocator<T> > base_type;
    typedef switch_init_allocator<T> allocator_type;
    typedef std::vector<T, allocator_type > vector_type;
    typedef typename base_type::size_type size_type;
  private:
    bool switch_flag; //the order here is very important!!
    vector_type vec;
  public:  
    my_vector(size_type aCount) : switch_flag(false), vec(aCount, allocator_type(&switch_flag)) { };
    //... and the rest of this wrapper class...
    vector_type& get_vector() { return vec; };
    const vector_type& get_vector() const { return vec; };
    void set_switch(bool value) { switch_flag = value; };
};

class xyz{};

int main(){
  my_vector<xyz> v(1024); //this won''t initialize the memory at all.
  v.set_switch(true); //set back to true to turn initialization back on (needed for resizing and such)
}

Por supuesto, lo anterior es incómodo y no se recomienda, y ciertamente no será mejor que dejar que la memoria se llene con copias del primer elemento (especialmente porque el uso de este control de bandera impedirá cada construcción de elemento) . Pero es una avenida para explorar cuando se busca optimizar la asignación e inicialización de elementos en un contenedor de STL, así que quería mostrarlo. El punto es que el único lugar donde puede inyectar código que impida que el contenedor std :: vector llame al constructor de copia para inicializar sus elementos es en la función de construcción del objeto asignador del vector.

Además, puede eliminar el "interruptor" y simplemente hacer un "no-init-allocator", pero luego, también desactiva la construcción de copia, que es necesaria para copiar los datos durante el cambio de tamaño (lo que haría que esta clase de vector fuera mucho más Menos útil).

Answer 5

No estoy viendo la memoria inicializada. El constructor predeterminado int() no hace nada, al igual que en C.

Programa:

#include <iostream>
#include <vector>

struct xyz {
    xyz() {}
    xyz(const xyz& o): v(o.v) {} 
    xyz& operator=(const xyz& o) { v=o.v; return *this; }
    int v;
};

std::vector<xyz> test() {
    return std::vector<xyz>(1024);
}

int main()
{
    std::vector<xyz> foo = test();
    for(int i = 0; i < 10; ++i)
    {
        std::cout << i << ": " << foo[i].v << std::endl;
    }
    return 0;
}

Salida:

$ g++ -o foo foo.cc
$ ./foo 
0: 1606418432
1: 1606418432
2: 1606418432
3: 1606418432
4: 1606418432
5: 1606418432
6: 1606418432
7: 1606418432
8: 1606418432
9: 1606418432

EDITAR:

Si solo está tratando de inicializar el vector a algo no trivial, y no quiere perder tiempo en la creación de sus contenidos, puede intentar crear un iterador personalizado y pasarlo al constructor del vector.

Ejemplo modificado:

#include <iostream>
#include <vector>
#include <iterator>

struct xyz {
    xyz() {}
    xyz(int init): v(init) {}
    xyz(const xyz& o): v(o.v) {} 
    xyz& operator=(const xyz& o) { v=o.v; return *this; }
    int v;
};

class XYZInitIterator: public std::iterator<std::input_iterator_tag, xyz>
{
public:
                        XYZInitIterator(int init): count(init) {}
                        XYZInitIterator(const XYZInitIterator& iter)
                        : count(iter.count) {}
    XYZInitIterator&    operator=(const XYZInitIterator& iter)
                        { count = iter.count; return *this; }
    value_type          operator*() const { return xyz(count); }
    bool                operator==(const XYZInitIterator& other) const 
                        { return count == other.count; }
    bool                operator!=(const XYZInitIterator& other) const 
                        { return count != other.count; }
    value_type          operator++() { return xyz(++count); }
    value_type          operator++(int) { return xyz(count++); }
private:
    int count;
};

std::vector<xyz> test() {
    XYZInitIterator start(0), end(1024);
    return std::vector<xyz>(start, end);
}

int main()
{
    std::vector<xyz> foo = test();
    for(int i = 0; i < 10; ++i)
    {
        std::cout << std::dec << i << ": " << std::hex << foo[i].v << std::endl;
    }
    return 0;
}

Salida:

$ g++ -o foo foo.cc
$ ./foo 
0: 0
1: 1
2: 2
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9

Answer 6

No se puede evitar la inicialización de los elementos de std :: vector.

Yo uso una clase derivada std :: vector por esa razón. resize() se implementa en este ejemplo. Usted debe implementar constructores también.

Aunque esto no es C ++ estándar, pero la implementación del compilador :-(

#include <vector>

template<typename _Tp, typename _Alloc = std::allocator<_Tp>>
class uvector : public std::vector<_Tp, _Alloc>
{
    typedef std::vector<_Tp, _Alloc> parent;
    using parent::_M_impl;

public:
    using parent::capacity;
    using parent::reserve;
    using parent::size;
    using typename parent::size_type;

    void resize(size_type sz)
    {
        if (sz <= size())
            parent::resize(sz);
        else
        {
            if (sz > capacity()) reserve(sz);
            _M_impl._M_finish = _M_impl._M_start + sz;
        }
    }
};

Answer 7

Para referencia, el siguiente código lleva a un ensamblaje óptimo en g ++: No estoy diciendo que lo vaya a usar nunca y no lo aliento a que lo haga. No es correcto C ++! Es un truco muy, muy sucio! Supongo que incluso podría depender de la versión g ++, así que, realmente, no la use. Yo vomitaría si lo viera usado en alguna parte.

#include <vector>

template<typename T>
static T create_uninitialized(size_t size, size_t capacity) {
    T v;
#if defined(__GNUC__)
    // Don''t say it. I know -_-;
    // Oddly, _M_impl is public in _Vector_base !?
    typedef typename T::value_type     value_type;
    typedef typename T::allocator_type allocator_type;
    typedef std::_Vector_base<value_type, allocator_type> base_type;
    base_type& xb(reinterpret_cast<base_type&>(v));
    value_type* p(new value_type[capacity]);
#if !defined(__EXCEPTIONS)
    size=p?size:0;         // size=0 if p is null
    capacity=p?capacity:0; // capacity=0 if p is null
#endif
    capacity=std::max(size, capacity); // ensure size<=capacity
    xb._M_impl._M_start = p;
    xb._M_impl._M_finish = p+size;
    xb._M_impl._M_end_of_storage = p+capacity;
#else
    // Fallback, for the other compilers
    capacity=std::max(size, capacity);
    v.reserve(capacity);
    v.resize(size);
#endif
    return v;
}

struct xyz {
    // empty default constructor
    xyz() { }
    xyz(const xyz& o): v(o.v) { }
    xyz& operator=(const xyz& o) { v=o.v; return *this; }
    int v;
    typedef std::vector<xyz> vector;
};

// test functions for assembly dump
extern xyz::vector xyz_create() {
    // Create an uninitialized vector of 12 elements, with
    // a capacity to hold 256 elements.
    return create_uninitialized<xyz::vector>(12,256);
}

extern void xyz_fill(xyz::vector& x) {
    // Assign some values for testing
    for (int i(0); i<x.size(); ++i) x[i].v = i;
}

// test
#include <iostream>
int main() {
    xyz::vector x(xyz_create());
    xyz_fill(x);
    // Dump the vector
    for (int i(0); i<x.size(); ++i) std::cerr << x[i].v << "/n";
    return 0;
}

EDITAR: se realizó _Vector_impl público, lo que simplifica las cosas.

EDITAR: aquí se encuentra el ensamblado ARM generado para xyz_create (), compilado con -fno-exceptions (desmangle usando c ++ filt) y sin ningún bucle de inicialización de memoria:

xyz_create():
    mov r3, #0
    stmfd   sp!, {r4, lr}
    mov r4, r0
    str r3, [r0, #0]
    str r3, [r0, #4]
    str r3, [r0, #8]
    mov r0, #1024
    bl  operator new[](unsigned long)(PLT)
    cmp r0, #0
    moveq   r3, r0
    movne   r3, #1024
    moveq   r2, r0
    movne   r2, #48
    add r2, r0, r2
    add r3, r0, r3
    stmia   r4, {r0, r2, r3}    @ phole stm
    mov r0, r4
    ldmfd   sp!, {r4, pc}

..y aquí para x86_64:

xyz_create():
    pushq   %rbp
    movq    %rsp, %rbp
    pushq   %rbx
    movq    %rdi, %rbx
    subq    $8, %rsp
    movq    $0, (%rdi)
    movq    $0, 8(%rdi)
    movq    $0, 16(%rdi)
    movl    $1024, %edi
    call    operator new[](unsigned long)
    cmpq    $1, %rax
    movq    %rax, (%rbx)
    sbbq    %rdx, %rdx
    notq    %rdx
    andl    $1024, %edx
    cmpq    $1, %rax
    sbbq    %rcx, %rcx
    leaq    (%rax,%rdx), %rdx
    notq    %rcx
    andl    $48, %ecx
    movq    %rdx, 16(%rbx)
    leaq    (%rax,%rcx), %rcx
    movq    %rbx, %rax
    movq    %rcx, 8(%rbx)
    addq    $8, %rsp
    popq    %rbx
    leave
    ret

Answer 8

Si desea un vector con solo memoria reservada, pero sin elementos inicializados, use reserve lugar del constructor:

std::vector<xyz> v;
v.reserve(1024);
assert(v.capacity() >= 1024);
assert(v.size() == 0);

Answer 9

También soy curioso. ¿Solo quieres que la memoria se inicialice al azar?

Los elementos vectoriales se almacenan en ubicaciones de memoria consecutivas, por lo que la inicialización aleatoria es una posibilidad.