CODEWITHSUNDEEP
c++templatesc++17variable-length-arraystdcopy
Sherry
Sherry

Reputation: 263

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

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

enter image description here

Upvotes: 4

Views: 1252

Answers (2)

JeJo
JeJo

Reputation: 32852

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.

Upvotes: 7

Maxim Egorushkin
Maxim Egorushkin

Reputation: 136266

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.

Upvotes: 4

Related Questions