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
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::vector
s or std::array
s; 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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With