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.