39

std::begin and std::end know the beginning and end of a container or an array.

It so easy to know the end and begin of a vector for example because it is a class that gives this information. But, how does it know the end of an array like the following?

int simple_array[5]{1, 2, 3, 4, 5};
auto beg=std::begin(simple_array);
auto en=std::end(simple_array);

std::begin is not that hard to know where the array start. But how does it know where it ends? Will the constant integer 5 be stored somewhere?

I would appreciate if I got an answer with some low-level information.

Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
Humam Helfawi
  • 19,566
  • 15
  • 85
  • 160

3 Answers3

33

But, how does it know the end of an array

It uses a template non-type parameter to deduce the size of the array, which can then be used to produce the end pointer. The C++11 signature from the cppreference section for std::end is as follows:

template< class T, std::size_t N >
T* end( T (&array)[N] );

As hvd notes, since it is passed by reference this prevents decay to a pointer.

The implementation would be something similar to:

template< class T, std::size_t N >
T* end( T (&array)[N] )
{
    return array + N ;
}

Is the constant integer 5 will be stored some where?

5 or N is part of the type of the array and so N is available at compile time. For example applying sizeof to an array will give us the total number of bytes in the array.

Many times we see an array passed by value to a function. In that case, the array decays to a pointer to type stored in the array. So now the size information is lost. Passing by reference allows us to avoid this loss of information and extract the size N from the type.

Community
  • 1
  • 1
Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
  • thanks, doest that mean that the N is stored somewhere? if yes, where? – Humam Helfawi Nov 03 '15 at 10:15
  • N is stored by the function. It'll be lost once the function has finished executing. If you want to achieve the same effect and return the size of the array you can use the code provided in this answer and just return N. – M Davies Nov 03 '15 at 10:18
  • @HumamHelfawi you know I missed the point of your comment earlier and realized while I was commuting what you meant. I updated my answer to properly cover your comment. – Shafik Yaghmour Nov 03 '15 at 13:54
  • Yes it is more clear for me now.. Many thanks @ShafikYaghmour – Humam Helfawi Nov 03 '15 at 13:57
  • 2
    @HumamHelfawi: Actually, the array size is indeed stored somewhere => in the code. For each different tuple `(T, N)`, a different instance of `std::end` is generated and stored as code in the emitted library/binary. An optimizing compiler *may* realize that it is useless, and optimize it out (only leaving the result `array + N`) but even then this N will thus appear in the generated code (as a constant). – Matthieu M. Nov 03 '15 at 14:25
28

is the constant integer 5 will be stored some where?

Yes, it's part of the type of the array. But no, it's not stored anywhere explicitly. When you have

int i[5] = { };

the type of i is int[5]. Shafik's answer talks about how this length is used to implement end.

If you've C++11, using constexpr would be the simple way to go

template <typename T, size_t N>
inline constexpr size_t
arrLen(const T (&arr) [N]) {
    return N;
}

If you've a pre-C++11 compiler where constexpr isn't available, the above function may not be evaluated at compile-time. So in such situations, you may use this:

template <typename T, size_t N>
char (&arrLenFn(const T (&arr) [N]))[N];

#define arrLen(arr) sizeof(arrLenFn(arr))

First we declare a function returning a reference to an array of N chars i.e. sizeof this function would now be the length of the array. Then we've a macro to wrap it, so that it's readable at the caller's end.

Note: Two arrays of the same base type but with different lengths are still two completely different types. int[3] is not the same as int[2]. Array decay, however, would get you an int* in both cases. Read How do I use arrays in C++? if you want to know more.

Community
  • 1
  • 1
legends2k
  • 31,634
  • 25
  • 118
  • 222
  • Thanks, It seems that I missed lot of things.. I should really ask"What is a array".. you mean that the array is some kind of small class with a pointer to start and a number of element ? could you point me to sth that can I read about it in details ? – Humam Helfawi Nov 03 '15 at 10:18
  • 2
    Two arrays of the same base type but with different lengths are still two completely different types. `int[3]` is not the same as `int[2]`. Array decay, however, would get you a `int*` in both cases. Read [How do I use arrays in C++?](http://stackoverflow.com/q/4810664/183120), if want to know more on arrays. – legends2k Nov 03 '15 at 10:25
  • yes this is exactly what I conclude from your answer. thanks again – Humam Helfawi Nov 03 '15 at 10:27
  • 2
    @HumamHelfawi an array of `int[5]` is just 5 `int`s next to each other in memory. The size isn't stored anywhere at runtime. The size is available at compile time because it is part of the array's type. – Simple Nov 03 '15 at 10:27
9

Because you are passing an array to std::end, and an array has type T [N]. std::end can tell when the array ends by looking at the N in the type.

Simple
  • 13,992
  • 2
  • 47
  • 47