C++11 std::begin doesn't work with int[] passed into template function

Question

I've got an issue: no matching function for call to ‘begin(int*&)’ The only hint I've found on it is that compiler might not know the size of array at compile time, but I believe that's not my case. Here is what I've got:

template <typename T>
void heapSort(T array[]) {
  size_t length = std::end(array) -  std::begin(array);
  if (length == 0) {
    return;
  }
  Heap<T> heap(array);
  for (size_t i = length - 1; i >= 0; --i) {
    array[i] = heap.pop();
  }
}

int main() {      
  int array[] = {9, 8, 10, 99, 100, 0};
  for (auto i = 0; i < 6; ++i) {
    std::cout << array[i] << " ";
  }
  std::cout << std::endl;
  heapSort(array);
  for (auto i = 0; i < 6; ++i) {
    std::cout << array[i] << " ";
  }
  std::cout << std::endl;
}

What's the problem? How can I solve it?

possible duplicate of [Sizeof an array in the C programming language?](http://stackoverflow.com/questions/1975128/sizeof-an-array-in-the-c-programming-language) — Bo Persson, Apr 25 '13 at 20:06

score 9 · Accepted Answer · answered Apr 25 '13 at 19:53

9

void heapSort(T array[]);

is just alternative syntax for

void heapSort(T* array);

You can't pass an array by value, so you need to take it by reference (and possibly let the compiler deduce its size):

template<typename T, size_t N>
void heapSort(T (&array)[N]);

Note that this way you'll get a different instantiation for each array of distinct size. It might lead to some code bloat if you've got a large number of arrays. I'd consider using a std::vector instead.

answered Apr 25 '13 at 19:53

jrok

54,456
9
109
141

3

Instead of a `vector` or an array, the best thing would be to take first and last iterators... `template void heapSort(RandomIt first, RandomIt last)` (note the template argument is named for the [standard iterator template policy](http://en.cppreference.com/w/cpp/concept/RandomAccessIterator) it is required to be) – David Apr 25 '13 at 20:23

score 2 · Answer 2 · answered Apr 25 '13 at 19:55

Like jrok said, T array[] is just a synonym for a pointer T* array which looses any information about the actual array type.

If you really want to use a compile time array, it's actually

template<typename T,std::size_t N> void heapSort(T (&array)[N])

(And that's in the end what std::begin and std::end do, too.)

Casey · Answer 3 · 2013-04-27T15:19:07.153

2

The other problem is that size_t is always non-negative, so your loop for (size_t i = length - 1; i >= 0; --i) will never terminate. Try replacing with:

for (size_t i = length; i > 0; --i) {
  array[i - 1] = heap.pop();
}

edited Apr 27 '13 at 15:19

answered Apr 27 '13 at 01:45

Casey

41,449
7
95
125

Are you sure `Heap` is usable with `std::begin/end`? – Christian Rau Apr 27 '13 at 08:25
There's no way I could be - all we can tell from the code given is that `Heap` is some kind of container template class. I am however sure that it _should_ have a `begin()` and `end()`. (Well, we can suppose that it's a sorted container as well ;) – Casey Apr 27 '13 at 15:13
Given that the name is `Heap`, it's very likely not sorted and implements a heap, so a direct element-by-element copy would fail to give a proper sort order. – Casey Apr 27 '13 at 15:18
Heap is a class I've implemented. It may be a good idea to have begin() and end() methods, thanks! The thing is I wanted to implement my own class heap and heapSort() just for testing purposes. – krems May 05 '13 at 18:39

C++11 std::begin doesn't work with int[] passed into template function

3 Answers3