Is it possible to use `std::copy` to copy values from a variable-sized array to a container?

Question

Following is a MergeSort implementation. My problem is that the compiler complains that std::begin cannot be applied on a variable-sized array temp in order to further use std:copy.

I am using C++17 and gcc 8.3.

template<typename Container, typename Iterator>
void Search::MergeSort(Container &array, Iterator begin, Iterator end)
{
    auto const len = end - begin;
    if (len > 1)
    {
        auto mid = begin + len / 2;
        MergeSort(array, begin, mid); 
        MergeSort(array, mid, end); 

        typename Container::value_type temp[len];

        int p = 0;
        for (auto i = begin, j = mid; i < mid; ++i)
        {
            auto curr = *i;
            while (j < end && *j < curr) temp[p++] = *j++;
            temp[p++] = curr;
        }

        auto temp_begin = std::begin(temp); // ! problem: unable to compile this line
        copy(temp_begin, temp_begin + p, begin);
    }

The error messages include:

template argument deduction/substitution failed:
note: mismatched types 'std::initializer_list<_Tp>' and 'std::vector<int>::value_type*' {aka 'int*'}
      variable-sized array type 'std::vector<int>::value_type [len]' {aka 'int [len]'} is not a valid template argument

Variable length arrays are not a part of c++, so how it behaves is really up to the implementation that provides the extension. — François Andrieux, Apr 26 '19 at 20:24
Beside that var-arrays are not part of C++ and therefore a compiler extension. You don't need std::begin(temp). Raw pointers behave like iterators in the STL. So temp alone is your begin. — user6556709, Apr 26 '19 at 20:26
Turn `typename Container::value_type temp[len]` into `std::vector temp(len)` and the code will be complaint and compile. No need for VLA's when you have `std::vector`. — NathanOliver, Apr 26 '19 at 20:26
VLA having entered the C-standard (where the extension originates from) was ***huge*** mistake anyway. If at all, they should rather have considered standardising `alloca`... — Aconcagua, Apr 26 '19 at 20:47
@Aconcagua You can only say this because you have not understood the power of C99 VLAs. I don't blame you, you are in good company as 99% of C++ programmers simply don't have a clue. However, if you really knew C99 VLAs, you would be asking yourself why C++ still uses crutches instead... Hint: It's much more than just being able to allocate a buffer on the stack with `int array[dynamicLength];`, C99 VLAs allow you to create multidimensional arrays with all dimensions dynamic on the heap... — cmaster - reinstate monica, Apr 26 '19 at 21:35
@Sherry The line `typename Container::value_type temp[len];` is evil: It allocates a possibly very large buffer on the stack. For your average unit test, it will look fine, but you may find that your function crashes in production due to overrunning the available stack space. — cmaster - reinstate monica, Apr 26 '19 at 21:38
@cmaster can you elaborate on *C99 VLAs allow you to create multidimensional arrays with all dimensions dynamic on the heap*? My understanding is that VLAs can only create arrays on the stack, and because of this, some folks (myself included) basically think of them as a [guaranteed stack-overflow and crash](https://stackoverflow.com/a/21519062/3854787). — Not a real meerkat, Apr 26 '19 at 23:58
@CássioRenan With C99 you can do this: `struct pixel (*image)[width] = malloc(height*sizeof(*image));` This declares a pointer `image` to an array of pixels of length `width`. This pointer is initialized by allocating space *on the heap* for `height` such arrays. **Neither `width` nor `height` need to be known at compile time**, the resulting pointer type is dynamic. Access to the red component of a pixel in this 2D array of pixels is as simple as saying `image[y][x].red`. — cmaster - reinstate monica, Apr 27 '19 at 07:19
@cmaster Actually, I already *had* functions accepting VLA (`void f(size_t n, int(*)[n])`) in mind when writing my comment... Still it didn't change my oppinion; I rather see it from the opposite point of view: One defending VLA hasn't understood the impacts on the language. Well, one could argue for a long time now, mainly because there's too much oppinion involved, one weighting stronger the pros, the other one the contras (why didn't VLA enter C++ even after 20 years?). In the end, we have to live with the situation as is, C providing VLA, C++ not (and most likely won't ever)... — Aconcagua, Apr 29 '19 at 06:45

JeJo · Answer 1 · 2019-04-26T21:49:26.203

Is it possible to use std::copy to copy values from a variable-sized array to a container?

To answer your question. Yes, Just like in @Maxim Egorushkin's answer, one could do it.

However, please don't use variable length arrays, because relying on something not part of C++ standard is a bad idea.

Secondly, C++ provides better options like std::vectors or std::arrays; therefore simply use them.

For instance, using std::vector, you could write completely error-free legal code (as @NathanOliver mentioned in the comments).

#include <vector>

using value_type = typename Container::value_type;

/* or by iterator_traits
 * using value_type = typename std::iterator_traits<Iterator>::value_type;
 */
std::vector<value_type> temp(len);

If len would have been a compile time know variable, you could have used std::array too.

Maxim Egorushkin · Accepted Answer · 2019-04-26T21:43:46.517

The problem is std::begin/end are not defined for variable-sized arrays.

Variable-size arrays are a C99 feature and a non-standard extension to C++. However, sometimes, they are the best choice performance-wise.

It is possible, however, to get iterators for a variable-sized array using plain pointer arithmetics:

std::copy(temp + 0, temp + p, begin);

If your C++ compiler doesn't support this extension some platforms, like Windows, Linux and probably most Unix-like platforms, provide alloca function instead. Be aware that this is just a memory allocation function (similar to malloc), so that it doesn't call constructors or initialize the allocated memory.

Is it possible to use `std::copy` to copy values from a variable-sized array to a container?

2 Answers2