How can I avoid std::vector<> to initialize all its elements?

Question

EDIT: I edited both the question and its title to be more precise.

Considering the following source code:

#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() :-(
}

...how can I avoid the memory allocated by the vector<> to be initialized with copies of its first element, which is a O(n) operation I'd rather skip for the sake of speed, since my default constructor does nothing ?

A g++ specific solution will do, if no generic one exists (but I couldn't find any attribute to do that).

EDIT: generated code follows (command line: arm-elf-g++-4.5 -O3 -S -fno-verbose-asm -o - test.cpp | arm-elf-c++filt | grep -vE '^[[:space:]]+[.@].*$' )

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}

EDIT: For the sake of completeness, here is the assembly for 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: I think the conclusion is to not use std::vector<> when you want to avoid unneeded initialization. I ended up unrolling my own templated container, which performs better (and has specialized versions for neon and armv7).

Answer 1

The initialization of the elements allocated is controlled by the Allocator template argument, if you need it customized, customize it. But remember that this can get easily wind-up in the realm of dirty hacking, so use with caution. For instance, here is a pretty dirty solution. It will avoid the initialization, but it most probably will be worse in performance, but for demonstration's sake (as people have said this is impossible!... impossible is not in a C++ programmer's vocabulary!):

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

Of course, the above is awkward and not recommended, and certainly won't be any better than actually letting the memory get filled with copies of the first element (especially since the use of this flag-checking will impede on each element-construction). But it is an avenue to explore when looking to optimize the allocation and initialization of elements in an STL container, so I wanted to show it. The point is that the only place you can inject code that will stop the std::vector container from calling the copy-constructor to initialize your elements is in the construct function of the vector's allocator object.

Also, you could do away with the "switch" and simply do a "no-init-allocator", but then, you also turn off copy-construction which is needed to copy the data during resizing (which would make this vector class much less useful).

Answer 2

This is a strange corner of the vector. The problem is not that your element is being value initialised... it's that the random content in the first prototypal element is copied to all the other elements in the vector. (This behaviour changed with C++11, which value initialises each element).

This is(/was) done for a good reason: consider some reference counted object... if you construct a vector asking for 1000 elements initialised to such an object, you obviously want one object with a reference count of 1000, rather than having 1000 independent "clones". I say "obviously" because having made the object reference counted in the first place implies that's highly desirable.

Anyway, you're almost out of luck. Effectively, the vector is ensuring that all the elements are the same, even if the content it's syncing to happens to be uninitialised garbage.

---

In the land of non-Standard g++-specific happy-hacking, we can exploit any public templated member function in the vector interface as a backdoor to change private member data simply by specialising the template for some new type.

WARNING: not just for this "solution" but for this whole effort to avoid default construction... don't do this for types with important invariants - you break encapsulation and can easily have vector itself or some operation you attempt invoke operator=(), copy-constructors and/or destructors where *this/left- and/or right-hand-side arguments don't honour those invariants. For example, avoid value-types with pointers that you expect to be NULL or to valid objects, reference counters, resource handles 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;
        }
}

My output:

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

This suggests the new vector was reallocated the heap that the first vector released when it went out of scope, and shows the values aren't clobbered by the assign. Of course, there's no way to know if some other important class invariants have been invalidated without inspecting the vector sources very carefully, and the exact names/import of private members can vary at any time....

Answer 3

You cannot avoid std::vector's elements initialization.

I use a std::vector derived class for that reason. resize() is implemented in this example. You must implement constructors too.

Although this is not standard C++ but compiler implementation :-(

#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 4

You wrap all your primitives in a struct:

struct IntStruct
{
    IntStruct();

    int myInt;
}

with IntStruct() defined as an empty constructor. Thus you declare v as IntStruct v; so when a vector of xyzs all value-initialize, all they do is value-initialize v which is a no-op.

EDIT: I misread the question. This is what you should do if you have a vector of primitive types, because vector is defined to value-initialize upon creating elements through the resize() method. Structs are not required to value-initialize their members upon construction, though these "uninitialized" values can still be set to 0 by something else -- hey, they could be anything.

Answer 5

For reference, the following code leads to optimal assembly in g++: I am not saying I will ever use it and I don't encourage you to. It is not proper C++! It's a very, very dirty hack! I guess it might even depend on g++ version, so, really, do not use it. I would puke if I saw it used somewhere.

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

EDIT: realized _Vector_impl was public, which simplify things.

EDIT: here is the generated ARM assembly for xyz_create(), compiled with -fno-exceptions (demangled using c++filt) and without any memory-initializing loop:

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}

..and here for 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 6

I am also curious. Do you just want the memory random initialized?

Vector elements are stored in consecutive memory locations so random initialization is a possibility.

Answer 7

I'm not seeing the memory initialized. The default int() constructor does nothing, just like in C.

Program:

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

Output:

$ 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

EDIT:

If you're just trying to initialize the vector to some nontrivial thing, and don't want to waste time default-constructing its contents, you might want to try creating a custom iterator and passing it to the vector's constructor.

Modified example:

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

Output:

$ 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 8

If you want a vector with only memory reserved, but no initialized elements, use reserve instead of the constructor:

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

Answer 9

With the way your struct is declared at the moment, there is no mechanism to default initialize the int member of your struct, therefore you get the default C behavior which is an indeterminate initialization. In order to initialize the int member variable with a default initialization value, you would have to add it to the initialization list of the structure's constructor. For example,

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

Where-as

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