Any alternative to std::dynarray presently available?

Question

C++11 gave us great std::array, which requires size to be known at compile time:

std::array<int, 3> myarray = {1, 2, 3};

Now, I happen to have some old short* buffers to wrap, whose size will be known (and it will be, of course) at runtime only.

C++14 will define std::dynarray to cover this case, but dynarray is not available yet in GCC 4.7 nor in Clang 3.2.

So, does anyone know a container which is comparable to std::array (in terms of efficiency) but does not require to specify size at compile time? I suspect Boost has something ready for me, although I couldn't find anything.

Ellissa

Why not std::vector? – Polka

Dynamic capabilities are heavyweight and not needed here. I need a fixed size container, much like a plain old C array, but with some metadata attached and the ability to iterate over. – Ellissa

You could still use std::vector and reserve() the size you need ahead of time. This way you don't hit the resizing penalties when inserting. – Polka

I removed your C++14 tag. This meta question came to a concensus to wait until the Final Draft Standard is released before using it instead of C++1y. – Helsinki

@StefanoSanfilippo, No problem. I found out the same way with my question, except the edit just had the link in the summary. – Helsinki

Please note that there's a high chance dynarray won't make it into C++14, since there doesn't seem to be implementation experience regarding the stack-allocation part of it and there are other problems aswell. – Biconcave

The problem with saying "C++14 will" before C++14 exists is that, well, C++14 doesn't exist yet :-S – Learn

Answer 1

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

Kienan

Great! std::valarray is as close to a pure array as possible (not counting std::dynarray) and I'm fine with the limitations you listed (nice!). – Ellissa

In respect to a std::vector created with the right overload and just accessing elements with operator[] you are just cutting on one data member (the capacity). This smells a lot like premature optimization to me... – Arterio

I would say the case for dynarray is more about defensive programming than about optimization -- it should not be possible to resize an array that has no business being resized. – Beamer

Why malloc()? Why not raw_array = new short(12);? – Snuggery

For stack allocated use, the raw_array could be a VLA if one could accept the use of non standard compiler features. Your code could be used to implement dynarray then, until it gets available. – Indication

@MatteoItalia Adding an extra member makes the object 1,5 times larger. Also a std::vector may over-allocate memory to increase performance. – Metalworking

Also, on an x86_64, copying 16 bytes can be done in one cycle assuming correct alignment, improving efficiency for std::swap. – Metalworking

Answer 2

I think std::vector is what you're looking for before dynarray becomes available. Just use the allocating constructor or reserve and you'll avoid reallocation overhead.

Pincushion

What is the main difference between dynarray and vector? – Bunchy

@user814628 vector can be resized after creation, to-be-dynarray can't. – Syllepsis

Why such specialization? More efficient push_back code I assume? – Bunchy

@user814628 and this assumption allows for better optimization of the container. – Ellissa

I guess C++ strives to be efficient as possible, but it seems like it's specializing on every little thing to allow optimization. More option couldn't hurt but can be overwhelming with all these choices – Bunchy

@user814628: The assumption is that the library implementation would be able to allocate the elements in the stack in the case of std::dynarray, which would make it closer to VLAs in C. If that is the case, then dynarray would not incur the cost of the allocation, but it is not trivial to implement dynarray (at least as a library) – Cheapen

@DavidRodríguez-dribeas Given a \constant number n, how can we allocate n-elements on stack in runtime? – Bunchy

@user814628 using stack-allocated dynamic arrays, which are also coming in C++14. – Handbill

@user814628 with alloca – Blinnie

Answer 3

I’ll put in a vote for std::unique_ptr<short[]>(new short[n]) if you don’t need the range-checked access provided by std::dynarray<T>::at(). You can even use an initializer list:

#include <iostream>
#include <memory>

int main(int argc, char** argv) {
  const size_t n = 3;
  std::unique_ptr<short[]> myarray(new short[n]{ 1, 2, 3 });
  for (size_t i = 0; i < n; ++i)
    std::cout << myarray[i] << '\n';
}

Swat

But but... you cannot use the pretty for loop syntax with that! – Skeleton

@Yakk True true... ;) but you can use std::for_each( myarray.get(), myarray.get() + 3, [](short val) { std::cout << val << "\n"; } ); – Skill

@andre It isn't the same. sniff. Plus you have to remember that 3 somewhere, which a dynarray remembers for you. – Skeleton

You should write a make_unique function and use that instead of writing new. – Handbill

Answer 4

A buffer and a size, plus some basic methods, give you most of what you want.

Lots of boilerplate, but something like this:

template<typename T>
struct fixed_buffer {
  typedef       T                               value_type;
  typedef       T&                              reference;
  typedef const T&                              const_reference;
  typedef       T*                              iterator;
  typedef const T*                              const_iterator;
  typedef std::reverse_iterator<iterator>       reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  typedef size_t                                size_type;
  typedef ptrdiff_t                             difference_type;

  std::size_t length;
  std::unique_ptr<T[]> buffer;

  std::size_t size() const { return length; }

  iterator begin() { return data(); }
  const_iterator begin() const { return data(); }
  const_iterator cbegin() const { return data(); }
  iterator end() { return data()+size(); }
  const_iterator end() const { return data()+size(); }
  const_iterator cend() const { return data()+size(); }

  reverse_iterator rbegin() { return {end()}; }
  const_reverse_iterator rbegin() const { return {end()}; }
  const_reverse_iterator crbegin() const { return {end()}; }
  reverse_iterator rend() { return {begin()}; }
  const_reverse_iterator rend() const { return {begin()}; }
  const_reverse_iterator crend() const { return {begin()}; }

  T& front() { return *begin(); }
  T const& front() const { return *begin(); }
  T& back() { return *(begin()+size()-1); }
  T const& back() const { return *(begin()+size()-1); }
  T* data() { return buffer.get(); }
  T const* data() const { return buffer.get(); }
  T& operator[]( std::size_t i ) { return data()[i]; }
  T const& operator[]( std::size_t i ) const { return data()[i]; }
  fixed_buffer& operator=(fixed_buffer &&) = default;
  fixed_buffer(fixed_buffer &&) = default;

  explicit fixed_buffer(std::size_t N):length(N), buffer( new T[length] ) {}
  fixed_buffer():length(0), buffer() {}

  fixed_buffer(fixed_buffer const& o):length(o.N), buffer( new T[length] )
  {
    std::copy( o.begin(), o.end(), begin() );
  }
  fixed_buffer& operator=(fixed_buffer const& o)
  {
    std::unique_ptr<T[]> tmp( new T[o.length] );
    std::copy( o.begin(), o.end(), tmp.get() );
    length = o.length;
    buffer = std::move(tmp);
    return *this;
  }
};

at() is missing, as are allocators.

operator= is different than dyn_array proposal -- the proposal blocks operator=, I give it value semantics. A few methods are less efficient (like copy construction). I allow empty fixed_buffer.

This would probably block being able to use the stack to store a dyn_array, which is probably why it doesn't allow it. Simply delete my operator= and trivial constructor if you want closer-to-dyn_array behavior.

Skeleton

As far as I know std::dynarray allocates the memory on the stack, so one could extend or modify the template above in a way that it does not allocate the memory on the heap but uses external memory which was allocated with alloc(sizeof(T) * NUMBER_OF_ELEMENTS). One only must then call in in place constructor on all elements inside the templates' c'tor and call the d'tor on destruction. I have not checked it, but it should not be too difficult to realize – Kerman

@FelixPetriconi alloca (stack based allocation) would be difficult to support, because alloca's memory cannot be returned from a function! You'd have to take a "scoping" lambda that would be the "body" within which the array was valid, or have the containing scope pass in alloca'd memory methinks. – Skeleton

Answer 5

C++14 also adds variable length arrays, similar to those in C99, and that's supported by some compilers already:

void foo(int n) {
  int data[n];
  // ...
}

It's not a container, as it doesn't support begin() and end() etc. but might be a workable solution.

Ghost

They aren't called variable length arrays, and not really similar to C99 VLAs other than the declaration syntax. – Rickets

@BenVoigt: What are they called? – Melee

"Arrays of runtime bound" but they got yanked from C++14 – Ghost

Answer 6

dynarray is very easy to implement oneself without the stack-allocation component -which apparently isn't possible to do until perhaps C++14 anyway- so I just rolled a dynarray inverse-backport (forwardport?) as part of my library and started using it ever since. Works in C++03 without any "void in Nebraska" clauses so far, as it doesn't absolutely depend on any C++11-specific capability, and it's neat to have
That way when C++1y/2z dynarray comes along my code is still for the most part compatible.

(It's also one of those many obvious "why didn't C++ have this sooner?" things so it's good to have it around).

This was before I learned that apparently C++1y-dynarray and C++1y-runtime-size-arrays are the exact same proposal (one is just syntactic sugar for the other) and not two different-but-complementary proposals as I first thought. So if I had to solve the same question nowadays I'd probably switch to something based off @Yakk's solution for correctness.

Chitarrone

Is this supposed to be an answer to the question or what? – Ellissa

Answer 7

This header-only library from year 2021 seems a decent option if you are ok with C++17: https://github.com/cnbatch/dynarray

Fireback