STL vectors with uninitialized storage?

by

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.

More Related Contents:

  1. std::vector reserve() and push_back() is faster than resize() and array index, why?
  2. Erasing elements from a vector
  3. Why can’t I make a vector of references?
  4. What is the easiest way to initialize a std::vector with hardcoded elements?
  5. How to overload std::swap()
  6. Alternative to vector
  7. Why isn’t vector a STL container?
  8. Best way to extract a subvector from a vector?
  9. When vectors are allocated, do they use memory on the heap or the stack?
  10. reduce the capacity of an stl vector
  11. How to sum up elements of a C++ vector?
  12. How to avoid memory leaks when using a vector of pointers to dynamically allocated objects in C++?
  13. Does vector::erase() on a vector of object pointers destroy the object itself?
  14. how do you insert the value in a sorted vector?
  15. How to use std::sort with a vector of structures and compare function?
  16. Reorder vector using a vector of indices [duplicate]
  17. std::vector, default construction, C++11 and breaking changes
  18. array vs vector vs list
  19. How to make elements of vector unique? (remove non adjacent duplicates)
  20. How to downsize std::vector?
  21. C++ convert vector to vector
  22. What happens if you increment an iterator that is equal to the end iterator of an STL container
  23. Is std::vector memory freed upon a clear?
  24. Getting a vector into a function that expects a vector
  25. std::vector capacity after copying
  26. Why is a C++ Vector called a Vector? [closed]
  27. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  28. C++ STL: Array vs Vector: Raw element accessing performance
  29. How to get the address of the std::vector buffer start most elegantly?
  30. How to cheaply assign C-style array to std::vector?

Leave a Comment