How Does This "Size of Array" Template Function Work

How does this template code to get the size of an array work?

This is actually a really tough one to explain, but I'll give it a go...

Firstly, dimof tells you the dimension, or number of elements in an array. (I believe "dimension" is the preferred terminology in Windows programming environments).

This is necessary because C++ and C don't give you a native way to determine the size of an array.

Often people assume sizeof(myArray) will work, but that will actually give you the size in memory, rather than the number of elements. Each element probably takes more than 1 byte of memory!

Next, they might try sizeof(myArray) / sizeof(myArray[0]). This would give the size in memory of the array, divided by the size of the first element. It's ok, and widely used in C code. The major problem with this is that it will appear to work if you pass a pointer instead of an array. The size of a pointer in memory will usually be 4 or 8 bytes, even though the thing it points to might be an array of 1000s of elements.

So the next thing to try in C++ is to use templates to force something that only works for arrays, and will give a compiler error on a pointer. It looks like this:

template <typename T, std::size_t N>
std::size_t ArraySize(T (&inputArray)[N])
{
    return N;
}
//...
float x[7];
cout << ArraySize(x); // prints "7"

The template will only work with an array. It will deduce the type (not really needed, but has to be there to get the template to work) and the size of the array, then it returns the size. The way the template is written cannot possibly work with a pointer.

Usually you can stop here, and this is in the C++ Standard Libary as std::size.

Warning: below here it gets into hairy language-lawyer territory.

This is pretty cool, but still fails in an obscure edge case:

struct Placeholder {
    static float x[8];
};

template <typename T, int N>
int ArraySize (T (&)[N])
{
    return N;
}

int main()
{
    return ArraySize(Placeholder::x);
}

Note that the array x is declared, but not defined. To call a function (i.e. ArraySize) with it, x must be defined.

In function `main':
SO.cpp:(.text+0x5): undefined reference to `Placeholder::x'
collect2: error: ld returned 1 exit status

You can't link this.

The code you have in the question is a way around that. Instead of actually calling a function, we declare a function that returns an object of exactly the right size. Then we use the sizeof trick on that.

It looks like we call the function, but sizeof is purely a compile time construct, so the function never actually gets called.

template <typename T, size_t N>
char(&DimofSizeHelper(T(&array)[N]))[N];
^^^^ ^                               ^^^
// a function that returns a reference to array of N chars - the size of this array in memory will be exactly N bytes

Note you can't actually return an array from a function, but you can return a reference to an array.

Then DimofSizeHelper(myArray) is an expression whose type is an array on N chars. The expression doesn't actually have to be runable, but it makes sense at compile time.

Therefore sizeof(DimofSizeHelper(myArray)) will tell you the size at compile time of what you would get if you did actually call the function. Even though we don't actually call it.

Austin Powers Cross-Eyed

Don't worry if that last block didn't make any sense. It's a bizarre trick to work around a bizarre edge case. This is why you don't write this sort of code yourself, and let library implementers worry about this sort of nonsense.

Using a template function return the size of an array

The definition is not needed as the function is not actually called. sizeof() only needs to determine what the type of the expression is and then calculate the size, it does not actually make the call.
just like if you had:

int foo();
size_t size{sizeof(foo())};

Remember that sizeof() is always evaluated at compile-time.

How is the size of the std::array calculated in the template

First, std::array is a template. When you write

std::array myArray5{ 9.0, 7.2, 5.4, 3.6, 1.8 };

Then Class Template Argument Deduction (CTAD, deduction guides for std::array can be found here) is applied to infer that myArray5 is of type std::array<double,5>. That is where the size is "calculated".

Then when you call the function template:

printArray(myArray5);

The template arguments are deduced from the function parameter (see here). myArray5 is std::array<double,5>, hence T == double and size == 5.

How does this Array Size Template Work?

The function template is named ArraySizeHelper, for a function that takes one argument, a reference to a T [N], and returns a reference to a char [N].

The macro passes your object (let's say it's X obj[M]) as the argument. The compiler infers that T == X and N == M. So it declares a function with a return type of char (&)[M]. The macro then wraps this return value with sizeof, so it's really doing sizeof(char [M]), which is M.

If you give it a non-array type (e.g. a T *), then the template parameter inference will fail.

As @Alf points out below, the advantage of this hybrid template-macro system over the alternative template-only approach is that this gives you a compile-time constant.

How to pass an array size as a template with template type?

Hmm, the Standard says in 14.8.2.4 / 15:

If, in the declaration of a function template with a non-type template-parameter, the non-type template-parameter is used in an expression in the function parameter-list and, if the corresponding template-argument is deduced, the template-argument type shall match the type of the template-parameter exactly, except that a template-argument deduced from an array bound may be of any integral type.

Providing this example:

template<int i> class A { /* ... */ };
template<short s> void f(A<s>);
void k1() {
    A<1> a;
    f(a);    // error: deduction fails for conversion from int to short
    f<1>(a); // OK
}

That suggests that the compilers that fail to compile your code (apparently GCC and Digital Mars) do it wrong. I tested the code with Comeau, and it compiles your code fine. I don't think there is a different to whether the type of the non-type template parameter depends on the type of the type-parameter or not. 14.8.2.4/2 says the template arguments should be deduced independent from each other, and then combined into the type of the function-parameter. Combined with /15, which allows the type of the dimension to be of different integral type, i think your code is all fine. As always, i take the c++-is-complicated-so-i-may-be-wrong card :)

Update: I've looked into the passage in GCC where it spits out that error message:

  ...
  type = TREE_TYPE (size);
  /* The array bound must be an integer type.  */
  if (!dependent_type_p (type) && !INTEGRAL_TYPE_P (type))
    {
      if (name)
    error ("size of array %qD has non-integral type %qT", name, type);
      else
    error ("size of array has non-integral type %qT", type);
      size = integer_one_node;
      type = TREE_TYPE (size);
    }
  ...

It seems to have missed to mark the type of the size as dependent in an earlier code block. As that type is a template parameter, it is a dependent type (see 14.6.2.1).

Update: GCC developers fixed it: Bug #38950

Get the length of an template<typename> array in c++

You can't. T arr[] as argument is an obfuscated way to write T* arr, and a pointer to first element of an array does not know the arrays size.

If possible change the function to pass the array by reference instead of just a pointer:

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

Things get much simpler if you use std::array.

PS: As a comment on the question suggests, the question is not quite clear. Is this the function you want to call after getting the size or do you need to get the size inside this function? Anyhow, I assumed the latter and that n is a argument unrelated to the arrays size. Further note that there is std::size that you can use to deduce the size also of a c-array. However, this also only works with the array, not once the array decayed to a pointer (as it does when passed as parameter to the function you posted).

How can a template function 'know' the size of the array given as template argument?

template<class T, size_t S> 
void Check(T (&)[S]) {  
   cout << "Deduced size: " << S << endl;
}

How does sizeof work when passing a template array?

If you are asking "how does the compiler know to put the array size into n"... The expression

const T (&arr)[n]

is being passed

int arr[11]

hence it is able to deduce T is int and n is 11.

If you are asking how it knows how large arr is...

int arr[] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 };
cout << isInHaystack(arr, 7) << endl;

arr is an array. The compiler knows how big it is. If you are thinking "arr is really just a pointer", that's not true. Arrays and pointers are said to have equivalence (see K&R section 5.3), which doesn't mean they are same, but that they result in the same behavior in a limited number of contexts.

In C and C++ arrays are able to decay into pointers, but they are still not pointers until the decay occurs.

int arr[] = { 1, 3, 5, 7 };
int* arrp = arr; // decay
cout << isInHaystack(arr, 7); // Error.

See http://c-faq.com/aryptr/aryptrequiv.html