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