Std::Dynarray VS Std::Vector

std::dynarray vs std::vector

So what are the benefits and the usage of std::dynarray, when we can use std::vector which is more dynamic (Re-sizable)?

dynarray is smaller and simpler than vector, because it doesn't need to manage separate size and capacity values, and it doesn't need to store an allocator.

However the main performance benefit is intended to come from the fact that implementations are encouraged to allocate dynarray on the stack when possible, avoiding any heap allocation. e.g.

std::dynarray<int> d(5);   // can use stack memory for elements
auto p = new std::dynarray<int>(6);  // must use heap memory for elements

This optimisation requires cooperation from the compiler, it can't be implemented as a pure library type, and the necessary compiler magic has not been implemented and noone is sure how easy it is to do. Because of the lack of implementation experience, at the C++ committee meeting in Chicago last week it was decided to pull std::dynarray from C++14 and to issue a separate array extensions TS (technical specification) document defining std::experimental::dynarray and arrays of runtime bound (ARBs, similar to C99 VLAs.) This means std::dynarray will almost certainly not be in C++14.

Why can std::vector be more performant than a native array?

Any super optimized code with lower level stuff like raw arrays can beat or tie the performance of an std::vector. But the benefits of having a vector far outweigh any small performance gains you get from low level code.

1. vector manages it's own memory, array you have to remember to manage the memory
2. vector allows you to make use of stdlib more easily (with dynamic arrays you have to keep track of the end ptr yourself) which is all very well written well tested code
3. sometimes vector can even be faster, like qsort v std::sort, read this article, keep in mind the reason this can happen is because writing higher level code can often allow you to reason better about the problem at hand.
4. Since the std containers are good to use for everything else, that dynamic arrays don't cover, keeping code consistent in style makes it more readable and less prone to errors.

One thing I would keep in mind is that you shouldn't compare a dynamic array to a std::vector they are two different things. It should be compared to something like std::dynarray which unfortunately probably won't make it into c++14 (boost prolly has one, and I'm sure there are reference implementations lying around). A std::dynarray implementation is unlikely to have any performance difference from a native array.

Any alternative to std::dynarray presently available?

You could (ab)use a std::valarray<short>.

int main() {
    short* raw_array = (short*) malloc(12 * sizeof(short));
    size_t length = 12;
    for (size_t i = 0; i < length; ++ i) {
        raw_array[i] = (short) i;
    }

    // ...

    std::valarray<short> dyn_array (raw_array, length);
    for (short elem : dyn_array) {
        std::cout << elem << std::endl;
    }

    // ...

    free(raw_array);
}

valarray supports most features of a dynarray, except:

• allocator
• reverse iterator
• .at()
• .data()

Note that the standard (as of n3690) does not require valarray storage be continuous, although there's no reason not to do so :).

(For some implementation detail, in libstdc++ it is implemented as a (length, data) pair, and in libc++ it is implemented as (begin, end).)

Using arrays or std::vectors in C++, what's the performance gap?

Using C++ arrays with new (that is, using dynamic arrays) should be avoided. There is the problem that you have to keep track of the size, and you need to delete them manually and do all sorts of housekeeping.

Using arrays on the stack is also discouraged because you don't have range checking, and passing the array around will lose any information about its size (array to pointer conversion). You should use std::array in that case, which wraps a C++ array in a small class and provides a size function and iterators to iterate over it.

Now, std::vector vs. native C++ arrays (taken from the internet):

// Comparison of assembly code generated for basic indexing, dereferencing, 
// and increment operations on vectors and arrays/pointers.

// Assembly code was generated by gcc 4.1.0 invoked with  g++ -O3 -S  on a 
// x86_64-suse-linux machine.

#include <vector>

struct S
{
  int padding;

  std::vector<int> v;
  int * p;
  std::vector<int>::iterator i;
};

int pointer_index (S & s) { return s.p[3]; }
  // movq    32(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

int vector_index (S & s) { return s.v[3]; }
  // movq    8(%rdi), %rax
  // movl    12(%rax), %eax
  // ret

// Conclusion: Indexing a vector is the same damn thing as indexing a pointer.

int pointer_deref (S & s) { return *s.p; }
  // movq    32(%rdi), %rax
  // movl    (%rax), %eax
  // ret

int iterator_deref (S & s) { return *s.i; }
  // movq    40(%rdi), %rax
  // movl    (%rax), %eax
  // ret

// Conclusion: Dereferencing a vector iterator is the same damn thing 
// as dereferencing a pointer.

void pointer_increment (S & s) { ++s.p; }
  // addq    $4, 32(%rdi)
  // ret

void iterator_increment (S & s) { ++s.i; }
  // addq    $4, 40(%rdi)
  // ret

// Conclusion: Incrementing a vector iterator is the same damn thing as 
// incrementing a pointer.

Note: If you allocate arrays with new and allocate non-class objects (like plain int) or classes without a user defined constructor and you don't want to have your elements initialized initially, using new-allocated arrays can have performance advantages because std::vector initializes all elements to default values (0 for int, for example) on construction (credits to @bernie for reminding me).

How operations are performed for dynamic array?

In C++ there are (well, pretty soon will be!) 4 kinds of arrays: C-style static arrays, C++11 static arrays, C++ dynamic vectors and C++14 dynamic arrays.

The C-style and C++11 static arrays take a compile-time constant size parameter and cannot be enlarged / shrunk after their initialization. C++ dynamic vectors can take any runtime number of elements at initialization, and can be enlarged / shrunk afterwards. With the upcoming C++14 Standard, there will also be std::dynarray that fills a smal gap between the existing containers: it will take a runtime number of elements during initialization, but cannot be enlarged / shrunk afterwards.

Here are some basic use cases:

static const int N = 4;                // compile-time constant int
int M = 4;                             // run-time int

int c[N] = { 0, 1, 2, 3 };             // C-style static array: compile-time constant size
std::array<int, N> a = { 0, 1, 2, 3 }; // C++11 static array: compile-time constant size

int rc[M] = { 0, 1, 2, 3 };             // ERROR: M is not a compile-time constant expression
std::array<int, M> ra = { 0, 1, 2, 3 }; // ERROR: M is not a compile-time constant expression

std::vector<int> v { std::begin(a), std::end(a) };   // C++ dynamic vector: runtime size, but can be enlarged afterwards
v.push_back(4);                                      // v enlarged to { 0, 1, 2, 3, 4 } now
v.pop_back();                                        // v shrunk back to { 0, 1, 2, 3 }

std::dynarray<int> d { std::begin(v), std::end(v) }; // C++14 dynamic array: runtime size, but cannot be enlarged afterwards

Static arrays (C-style arrays, std::array) do static memory allocation on the stack. Dynamic arrays (std::vector<T> and std::dynarray<T>) can take an Allocator template parameter. For std::vector this Allocator defaults to std::allocator<T>, which does dynamic low-level memory management behind the scenes using new. For std::dynarray the memory is allocated from an unspecified source, which may, or may not, invoke the global operator new.

By supplying a user-defined allocator, both std::vector and std::dynarray can be made to work with stack-based memory allocation, e.g. using @HowardHinnant 's stack allocator.

Can std::array (or boost::array) be used in this case, or am I stuck with std::vector and native arrays?

You simply cannot use any form of std::array if you don't know the length at compile time.

If you don't know the size of your array at compile time, seriously consider using std::vector. Using variable length arrays (like int foo[n]), is not standard C++ and will cause stack overflows if given length is big enough. Also you cannot write any array-like-wrapper with (measurably) less overhead than std::vector.

I would just use

virtual void foo(const unsigned char* my_array, size_t my_array_len);

And call it like

obj.foo(&vec[0], vec.size());

There is no overhead attached and it does what you want. In addition to normal arrays (int foo[42]) this can also be called with vectors and std::arrays with zero overhead.

Is there a standard C++ class for arrays with fixed run-time-determined size?

Allocate the memory using an std::unique_ptr<T[]> like you suggested, but to use it - construct an std::span (in C++20; gsl::span before C++20) from the raw pointer and the number of elements, and pass the span around (by value; spans are reference-types, sort of). The span will give you all the bells and whistles of a container: size, iterators, ranged-for, the works.

#include <span>
// or:
// #include <gsl/span>

int main() {

    // ... etc. ...

    {
        size_t size = 10e5;
        auto uptr { std::make_unique<double[]>(size) };
        std::span<int> my_span { uptr.get(), size };
        do_stuff_with_the_doubles(my_span);
    }

    // ... etc. ...
}

For more information about spans, see:

What is a "span" and when should I use one?

---

Related Topics