0

Simple question. I have a pointer to an array.

vector<int> myVector = { 22, 18, 12, -4, 58, 7, 31, 42 };
int* myPtr = myVector.data();

I also have a function that takes a reference to an array as a parameter.

template<typename T> void sort_quick(T (&arr)[]);

How can I pass my vector's array to this function without having to copy the potentially huge array in data().

sort_quick(*arr); // No matching function call for 'sort_quick'

Also, I need to pass it as an array, it's a pre-requisite, so don't come talking about just passing the vector because I wish I could.

Edit:

template<typename T, int N> void sort_quick(T (&arr)[N]);

This should now be legal syntax?

Edit2:

template<typename T> void sort_quick(T* arr, size_t length);

I believe this would be the best version then, when needing to deal with arrays and not vectors.

Francisco Aguilera
  • 3,099
  • 6
  • 31
  • 57
  • 1
    That declaration of `sort_quick` shouldn't compile. Reference to array of unknown bound is not allowed as a parameter in C++. – Brian Bi Feb 27 '15 at 00:09
  • `myPtr` is not a pointer to an array, it's a pointer to an `int` that happens to be an element of an array. There is no way to "go back" to the array that it is an element of. – molbdnilo Feb 27 '15 at 00:11
  • Seems to me like this problem is 2-sided. @Brian says that C++ does ot allow arrays of unknown bounds as parameters. See edit. Second problem still stands, is there no way to pass the array of a vector as a reference? – Francisco Aguilera Feb 27 '15 at 00:24
  • This is still impossible since the size of a vector is not known until runtime, but template arguments have to be known at compile time. (Or, more technically speaking, template arguments have to be constant expressions.) – Brian Bi Feb 27 '15 at 00:28
  • So there is no way to pass an array as a reference in C++ given a pointer to the array? You should post this as an answer so I may mark it. – Francisco Aguilera Feb 27 '15 at 00:32

3 Answers3

2

C-style array bounds must be known at compile-time. Your original definition of sort_quick was illegal. This is legal:

template<typename T, int N> void sort_quick(T (&arr)[N]);

however it can only be called with an actual array.

In order to support sorting containers whose sizes are not known until compile-time, you will need to make a version that takes two parameters. These could be two pointers, or a start pointer and a length. The version taking array could be made to delegate to the new version.

The idiomatic way would be to use iterators:

template<typename Iterator> void sort_quick(Iterator begin, Iterator end);

and then you can call the function like:

sort_quick(myVector.begin(), myVector.end());
M.M
  • 138,810
  • 21
  • 208
  • 365
  • While I do think your solution using iterators is elegant, and in my opinion, the way to go about doing this, I was asked to write a quick sort using array parameters. Therefore my best course of action would always be to use pointers when dealing with arrays in the case that the array is not available at compile time? – Francisco Aguilera Feb 27 '15 at 00:39
  • @FranciscoAguilera Why can't your function take `T[]` (or its equivalent `T*`) and a length parameter? That's how people always passed arrays to functions in C. (Of course, better alternatives exist in C++, which is why this requirement is silly in the first place.) – Brian Bi Feb 27 '15 at 00:47
  • It could take T[ ] and a length parameter, however, this way a copy could be made over a potentially large array. I did mention that T* is the way I will address this problem in the future. See my second edit. – Francisco Aguilera Feb 27 '15 at 00:50
  • @FranciscoAguilera taking `T*` and a length does not cause a copy. The pointer points at the data where it already is. – M.M Feb 27 '15 at 00:56
  • Yeah, a copy would be made, but only of the pointer :) I meant a copy of the full object if the function took T[ ] not T*. – Francisco Aguilera Feb 27 '15 at 00:57
  • @FranciscoAguilera the `T (&arr)[N]` does not make a copy because it passes by reference. C-style arrays cannot be passed by value in C++. I'm not sure if you are talking about using `T begin[]` as a function parameter, but that has the same meaning as `T *begin` – M.M Feb 27 '15 at 00:58
  • So C style arrays cannot be passed by value (even if you pass the size?) `template void sort_quick(T arr[N]);` Edit: oh...`T begin[]` is euqivalent to `T *begin`? So they're both pass-by-pointer? – Francisco Aguilera Feb 27 '15 at 01:00
  • Yes, in a function parameter list, specifying an array type actually gets you a pointer type. This is a hangover from C, [see here](http://stackoverflow.com/questions/22677415/why-do-c-and-c-compilers-allow-array-lengths-in-function-signatures-when-they/). In the `(T arr[N])` version, `N` actually is ignored and not deduced. – M.M Feb 27 '15 at 01:07
  • Interesting, thank you for that @Matt. I will stick with `template void sort_quick(T* arr, size_t length);`, seems the easiest to read and the right way to go about it. – Francisco Aguilera Feb 27 '15 at 01:15
-1

The signature for your sorting function takes an array reference; Something you may not know is that no rvalue expression in C or C++ may yield an array, that is to say, an rvalue may not be of an array type. You may also not know about how arrays can decay in to pointers when passed as parameters to functions, but that is perhaps a little off topic;

Regardless, you may not do something like:

sort_quick(my_vec.data());

If you absolutely must use that function with that signature (i.e. it is an interface over which you have no control), you will need to construct an array using the information that the set of values is [my_vec.data(); my_vec.size()] is valid. As to why you can't just use std::vector::data(), if you look carefully, you will see it's return type is T*, and pointers will not magically reverse-decay in to array references.

bfoster
  • 79
  • 4
  • I think it is false that you cannot have rvalues of array type. The result of a class member access in which the object expression is an rvalue and the member named is an array is an rvalue of array type, is it not? – Brian Bi Feb 27 '15 at 00:34
  • @Brian it's true that you can't have rvalues of array type. The lvalue-to-rvalue conversion entails the array-to-pointer conversion. – M.M Feb 27 '15 at 00:37
  • @bfoster lvalue expressions may yield an array . That sentence should be re-worded – M.M Feb 27 '15 at 00:38
  • Right you are, otherwise decl/init expressions would not work! I'll edit it now. – bfoster Feb 27 '15 at 00:42
  • 1
    @Brian sorry, I intended to say that there are not prvalues of array type. (Your example is an xvalue). I guess bfoster also meant prvalues (which were called "rvalues" before C++11) – M.M Feb 27 '15 at 01:21
  • @MattMcNabb According to this you can still create array prvalues: https://groups.google.com/a/isocpp.org/d/msg/std-discussion/8FZxvw1WE2Y/fXgf9aR-5sAJ – Brian Bi Feb 27 '15 at 01:25
  • @MattMcNabb Also, this isn't directly relevant, but according to my reading of the standard, lvalue-to-rvalue conversion is separate from array-to-pointer and function-to-pointer conversion. – Brian Bi Feb 27 '15 at 01:29
  • @Brian [conv.lval/1] says: "a glvalue of a non-function, **non-array** type T can be converted to a prvalue". So array prvalues cannot come from named arrays. However as you have pointed out, array temporaries can be created by `typedef int X[20]; X{};` . Thanks for finding that :) – M.M Feb 27 '15 at 01:40
-2

If you don't use C++11 you can do it that way:

sort_quick( &arr[0] );
DaRich
  • 937
  • 8
  • 13