How Does Std::End Know the End of an Array

How does std::end know the end of an array?

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.

How does the C++ begin and end work when argument is an array?

So to see how std::end works we can look at How does std::end know the end of an array? and see that the signature for std::end is:

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

and it is using template non-type parameter to deduce the size of the array and it is just a matter of pointer arithmetic to obtain the end:

return array + N ;

For std::begin the signature is identical, with the exception of the name:

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

and calculating the beginning of the array is simply a matter of array to pointer decay which gives us a pointer to the first element of the array.

In C++14 these both become constexpr.

How does std::find auto-magically knows the end of an array in C++?

std::find has no knowledge of the array or the elements that are initialised within it. You told it where to stop with the second argument:

std::find(m_subscriptions, // Start here
          m_subscriptions + numberOfSubscriptions, // Stop here
          44); // Try to find this

If it doesn't find what you're looking for, it just returns that second argument back, which is the end of the range that you gave it.

If you had passed std::end(m_subscriptions) as the second argument, it would have iterated over all the elements that you haven't assigned to. However, it's wroth noting that these aren't uninitialised, they have been value initialised. When you do aggregate initialisation with {}, any members of the aggregate that you haven't specified are value initialised. Regardless, even if they were uninitialised, there's no way to tell whether something has been initialised or not.

Finding the end of an array in a loop in C++?

Why not do the following?

bool not_first_item = false;

for(auto x : arr){
    if (not_first_item) {
       cout << ", ";
       not_first_item = true;
    }
    cout << x;
}

It will print a comma before each item except the first one. It will get the result you require without the need of using complicated pointers.

How to determine the end of an integer array when manipulating with integer pointer?

C-strings convention is that a char* finish by a '\0' char. For array or any other C++ container there are other idioms that can be applied. Next follows my preferences

The best way to iterate on sequences is to use the Range-based for-loop included on C++0x

int my_array[] = {1, 2, 3, 4, 5};
for(int& x : my_array)
{
  cout<<x<<endl;
}

If your compiler don't provide this yet, use iterators

for(int* it = std::begin(array); it!=std::end(array); ++it)
{
  cout<<*it<<endl;
}

And if you can not use neither std::begin/end

for(int* it = &array[0]; it!=&array[sizeof(array)]; ++it)
{
  cout<<*it<<endl;
}

P.S Boost.Foreach emulates the Range-based for-loop on C++98 compilers

Why do std::begin() and std::end() work with fixed arrays, but not with dynamic arrays?

std::(c)begin() and std:(c)end() are explicitly overloaded to work with fixed-sized array types. Information about the size of the arrays is not lost, as the sizes are part of the array types themselves. An implementation of these overloads may look something like this:

template<typename T, size_t N>
T* begin(T (&arr)[N])
{
    return arr;
}

template<typename T, size_t N>
const T* cbegin(const T (&arr)[N])
{
    return arr;
}

template<typename T, size_t N>
T* end(T (&arr)[N])
{
    return arr + N;
}

template<typename T, size_t N>
const T* cend(const T (&arr)[N])
{
    return arr + N;
}

Thus, std::begin(arr2) and std::end(arr2) are perfectly valid only when arr2 is an int[N] fixed-size array type. The compiler can deduce values for the T and N template parameters based on the type of fixed array being passed in, eg:

int arr2[5] = { 1,2,3,4,5 };

if (find(
    begin(arr2), // deduces T=int, N=5, thus calls std::begin<int,5>(arr2)
    end(arr2), // deduces T=int, N=5, thus calls std::end<int,5>(arr2)
    5)
    != end(arr2) // deduces T=int, N=5, thus calls std::end<int,5>(arr2)
    )
{
    cout << "found";
}

Conversely, there is simply no way to provide similar 1-parameter overloads for an int* pointer, as there is no information about the size of the array being pointed at (or even whether an array is even being pointed at) for std::end() to return a valid iterator to the end of the array:

template<typename T>
T* begin(T *arr)
{
    return arr; // OK
}

template<typename T>
const T* cbegin(const T *arr)
{
    return arr; // OK
}

template<typename T>
T* end(T *arr)
{
    return arr + N; // NOT OK, WHAT IS N SUPPOSED TO BE?!?
}

template<typename T>
const T* cend(const T *arr)
{
    return arr + N; // NOT OK, WHAT IS N SUPPOSED TO BE?!?
}

However, you can provide your own 2-parameter overloads ¹, so you can explicitly pass in the dynamic array size for N, eg:

namespace std
{
    template<typename T>
    T* begin(T *arr, size_t N)
    {
        return arr;
    }

    template<typename T>
    const T* cbegin(const T *arr, size_t N)
    {
        return arr;
    }

    template<typename T>
    T* end(T *arr, size_t N)
    {
        return arr + N;
    }

    template<typename T>
    const T* cend(const T *arr, size_t N)
    {
        return arr + N;
    }
}

int *arr = new int[5]{ 1,2,3,4,5 };

if (find(
    begin(arr,5), // deduces T=int, explicit N=5, thus calls std::begin<int>(arr2,5)
    end(arr2,5), // deduces T=int, explicit N=5, thus calls std::end<int>(arr2,5)
    5)
    != end(arr2,5) // deduces T=int, explicit N=5, thus calls std::end<int>(arr2,5)
    )
{
    cout << "found";
}

Live Demo

^{1: you ARE NOT allowed to add new functions to the std namespace, but you ARE allowed to add custom overloads for existing standard functions. std::swap() is an common example of that, though utilizing ADL is generally a better choice than extending the std namespace.}

---

Related Topics