Stl Vectors with Uninitialized Storage

STL vectors with uninitialized storage?

std::vector must initialize the values in the array somehow, which means some constructor (or copy-constructor) must be called. The behavior of vector (or any container class) is undefined if you were to access the uninitialized section of the array as if it were initialized.

The best way is to use reserve() and push_back(), so that the copy-constructor is used, avoiding default-construction.

Using your example code:

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

The only problem with calling reserve() (or resize()) like this is that you may end up invoking the copy-constructor more often than you need to. If you can make a good prediction as to the final size of the array, it's better to reserve() the space once at the beginning. If you don't know the final size though, at least the number of copies will be minimal on average.

In the current version of C++, the inner loop is a bit inefficient as a temporary value is constructed on the stack, copy-constructed to the vectors memory, and finally the temporary is destroyed. However the next version of C++ has a feature called R-Value references (T&&) which will help.

The interface supplied by std::vector does not allow for another option, which is to use some factory-like class to construct values other than the default. Here is a rough example of what this pattern would look like implemented 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));
    }
}

Doing this does mean you have to create your own vector class. In this case it also complicates what should have been a simple example. But there may be times where using a factory function like this is better, for instance if the insert is conditional on some other value, and you would have to otherwise unconditionally construct some expensive temporary even if it wasn't actually needed.

building a vector to allow uninitialized storage

To answer the questions:

1. no restriction on T : if it works for standard containers it works for yours.
2. destruction is conditional, you can statically disable it if std::is_trivially_destructible<T>, else you must track constructed elements and only delete those which were actually constructed.
3. I don't see a major flaw in your idea, but make sure it is worth it: profile your use-case and check that you really spend a lot of time initializing elements.

I'm making the assumption that you implement your container as a block of contiguous memory of size size() * sizeof(T). Also, if the element's destructor must be called, i.e. !std::is_trivially_destructible<T>, you must enable an additional storage, like a std::vector<bool> of size() elements use to flag elements for destruction.

Basically, if T is trivially destructible, you just init when the user asks and don't bother with destroying anything. Else, things are a little more tricky and you need to track which element was constructed and which is uninitialized, so that you only destroy what's needed.

• up-sizing or container creation:
  
  1. if !std::is_trivially_destructible<T> resize flags storage accordingly
  2. Memory allocation
  3. Optional initialization depending on what the user asked:
     
     • no_init => if !std::is_trivially_destructible<T>, flag elements as non-initialized. Else do nothing.
     • (Args...) => if std::is_constructible<T, class... Args> call that constructor for each element. If !std::is_trivially_destructible<T>, flag elements as constructed.
• down-sizing or container destruction:
  
  1. Optional destruction:
     
     • If std::is_trivially_destructible<T> do nothing
     • else for each element, if it is flagged as constructed, call its destructor
  2. Memory deallocation
  3. If !std::is_trivially_destructible<T> resize flags storage accordingly

From a performance point of view, if T is trivially destructible, things are great. If it has a destructor, things are more constrasted: you gain some constructors/destructors calls, but you need to maintain additional flags storage - in the end it depends if your constructors/destructors are complex enough.

Also like some suggested in the comments, you could just use an associative array based on std::unordered_map, add a size_t vector_size field, implement resize and override size. That way, uninitialized elements would not even be stored. On the other hand, indexing would be slower.

C++ vector that *doesn't* initialize its members?

For default and value initialization of structs with user-provided default constructors which don't explicitly initialize anything, no initialization is performed on unsigned char members:

struct uninitialized_char {
    unsigned char m;
    uninitialized_char() {}
};

// just to be safe
static_assert(1 == sizeof(uninitialized_char), "");

std::vector<uninitialized_char> v(4 * (1<<20));

GetMyDataFromC(reinterpret_cast<unsigned char*>(&v[0]), v.size());

I think this is even legal under the strict aliasing rules.

When I compared the construction time for v vs. a vector<unsigned char> I got ~8 µs vs ~12 ms. More than 1000x faster. Compiler was clang 3.2 with libc++ and flags: -std=c++11 -Os -fcatch-undefined-behavior -ftrapv -pedantic -Weverything -Wno-c++98-compat -Wno-c++98-compat-pedantic -Wno-missing-prototypes

C++11 has a helper for uninitialized storage, std::aligned_storage. Though it requires a compile time size.

---

Here's an added example, to compare total usage (times in nanoseconds):

VERSION=1 (vector<unsigned char>):

clang++ -std=c++14 -stdlib=libc++ main.cpp -DVERSION=1 -ftrapv -Weverything -Wno-c++98-compat -Wno-sign-conversion -Wno-sign-compare -Os && ./a.out

initialization+first use: 16,425,554
array initialization: 12,228,039
first use: 4,197,515
second use: 4,404,043

VERSION=2 (vector<uninitialized_char>):

clang++ -std=c++14 -stdlib=libc++ main.cpp -DVERSION=2 -ftrapv -Weverything -Wno-c++98-compat -Wno-sign-conversion -Wno-sign-compare -Os && ./a.out

initialization+first use: 7,523,216
array initialization: 12,782
first use: 7,510,434
second use: 4,155,241

#include <iostream>
#include <chrono>
#include <vector>

struct uninitialized_char {
  unsigned char c;
  uninitialized_char() {}
};

void foo(unsigned char *c, int size) {
  for (int i = 0; i < size; ++i) {
    c[i] = '\0';
  }
}

int main() {
  auto start = std::chrono::steady_clock::now();

#if VERSION==1
  using element_type = unsigned char;
#elif VERSION==2
  using element_type = uninitialized_char;
#endif

  std::vector<element_type> v(4 * (1<<20));

  auto end = std::chrono::steady_clock::now();

  foo(reinterpret_cast<unsigned char*>(v.data()), v.size());

  auto end2 = std::chrono::steady_clock::now();

  foo(reinterpret_cast<unsigned char*>(v.data()), v.size());

  auto end3 = std::chrono::steady_clock::now();

  std::cout.imbue(std::locale(""));
  std::cout << "initialization+first use: " << std::chrono::nanoseconds(end2-start).count() << '\n';
  std::cout << "array initialization: " << std::chrono::nanoseconds(end-start).count() << '\n';
  std::cout << "first use: " << std::chrono::nanoseconds(end2-end).count() << '\n';
  std::cout << "second use: " << std::chrono::nanoseconds(end3-end2).count() << '\n';
}

I'm using clang svn-3.6.0 r218006

uninitialized move in std::vector

If you're completely sure that objects you move don't have pointers to each other (subobjects of those included) - then just moving contents is okay. However you can't know that unless you know how the type is designed inside. One exception is that if the type is not larger than a pointer (sizeof(Type) <= sizeof( void* )), then it is very unlikely to have pointers to objects in the same container, so usually it can be just moved.

C++ - value of uninitialized vectorint

The zero initialization is specified in the standard as default zero initialization/value initialization for builtin types, primarily to support just this type of case in template use.

Note that this behavior is different from a local variable such as int x; which leaves the value uninitialized (as in the C language that behavior is inherited from).

How to copy into an uninitialized vector?

The first solution is incorrect because reserve doesn't add elements to your vector (it only reserves memory which you can't use). copy_if requires that the output iterator is valid and it points to the begining of a sequence that's able to hold all the elements you want to copy while your vector after calling reserve isn't able to hold the values because it only has raw, uninitialized memory so begin effectively returns an iterator to the end. If you copied elements this way the vector wouldn't know those elements are initialized which leads to a lot of problems.
On the other hand, the second solution is fine. back_inserter inserts elements to vector (which is more than just allocating memory) so that the vector is aware of what's going on. Note that calling reserve doesn't change anything in the aspect of correctness of this code. I mean it could be omited and the code would work just fine. However, it might be a good idea to leave it there especially if you know how many elements (even if it's just an approximation) you are going to insert. It's going to reduce the number of dynamic allocations which is good for performance.

Uninitialized class fields and STL containers

A container will default-initialize the objects it creates if you don't give them a specific value. In your case the default constructor for the object does not initialize the POD integer, so it will contain whatever was left over in memory.

Sometimes new heap blocks will be zero initialized by the OS, but you can't even count on that. A block can get reused and again it will contain leftover garbage from the last time it was used.

Code that is ultra sensitive to exploits will take care to zero out memory to critical variables such as passwords before destroying them.

---

Related Topics