Can Someone Explain This Template Code That Gives Me the Size of an Array

Can someone explain this template code that gives me the size of an array?

Well, first you have to understand that trying to get a value out of an array can give you a pointer to its first element:

int a[] = {1, 2, 3};
int *ap = a; // a pointer, size is lost
int (&ar)[3] = a; // a reference to the array, size is not lost

References refer to objects using their exact type or their base-class type. The key is that the template takes arrays by reference. Arrays (not references to them) as parameters do not exist in C++. If you give a parameter an array type, it will be a pointer instead. So using a reference is necessary when we want to know the size of the passed array. The size and the element type are automatically deduced, as is generally the case for function templates. The following template

template<typename T, size_t n>
size_t array_size(const T (&)[n]) {
    return n;
}

Called with our previously defined array a will implicitly instantiate the following function:

size_t array_size(const int (&)[3]) {
    return 3;
}

Which can be used like this:

size_t size_of_a = array_size(a);

There's a variation I made up some time ago [Edit: turns out someone already had that same idea here] which can determine a value at compile time. Instead of returning the value directly, it gives the template a return type depending on n:

template<typename T, size_t n>
char (& array_size(const T (&)[n]) )[n];

You say if the array has n elements, the return type is a reference to an array having size n and element type char. Now, you can get a compile-time determined size of the passed array:

size_t size_of_a = sizeof(array_size(a));

Because an array of char having n elements has sizeof n, that will give you the number of elements in the given array too. At compile time, so you can do

int havingSameSize[sizeof(array_size(a))];

Because the function never is actually called, it doesn't need to be defined, so it doesn't have a body. Hope I could clear the matter up a little bit.

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.

Why does this template for an array's size not work?

The issue is that T array[] is really T* array. To get the actual size you need to pass an array by reference, i.e, parameter T (&array)[N], with N being an integer template parameter.

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

How does this template magic determine array parameter size?

N does not get "initialized" to anything. It is not a variable. It is not an object. N is a compile-time constant. N only exists during compilation. The value of N as well as the actual T is determined by the process called template argument deduction. Both T and N are deduced from the actual type of the argument you pass to your template function.

In the first call the argument type is int[6], so the compiler deduces that T == int and N == 6, generates a separate function for that and calls it. Let's name it cal_size_int_6

void cal_size_int_6(int (&a)[6]) 
{ 
  std::cout << "size of array is: " << 6 << std::endl; 
}

Note that there's no T and no N in this function anymore. Both were replaced by their actual deduced values at compile time.

In the first call the argument type is int[1], so the compiler deduces that T == int and N == 1, generates a separate function for that as well and calls it. Let's name it cal_size_int_1

void cal_size_int_1(int (&a)[1]) 
{ 
  std::cout << "size of array is: " << 1 << std::endl; 
}

Same thing here.

Your main essentially translates into

int main() 
{ 
  int a[]={1,2,3,4,5,6}; 
  int b[]={1}; 

  cal_size_int_6(a); 
  cal_size_int_1(b); 
}

In other words, your cal_size template gives birth to two different functions (so called specializations of the original template), each with different values of N (and T) hardcoded into the body. That's how templates work in C++.

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 does this piece of code determine array size without using sizeof( )?

When you add 1 to a pointer, the result is the location of the next object in a sequence of objects of the pointed-to type (i.e., an array). If p points to an int object, then p + 1 will point to the next int in a sequence. If p points to a 5-element array of int (in this case, the expression &a), then p + 1 will point to the next 5-element array of int in a sequence.

Subtracting two pointers (provided they both point into the same array object, or one is pointing one past the last element of the array) yields the number of objects (array elements) between those two pointers.

The expression &a yields the address of a, and has the type int (*)[5] (pointer to 5-element array of int). The expression &a + 1 yields the address of the next 5-element array of int following a, and also has the type int (*)[5]. The expression *(&a + 1) dereferences the result of &a + 1, such that it yields the address of the first int following the last element of a, and has type int [5], which in this context "decays" to an expression of type int *.

Similarly, the expression a "decays" to a pointer to the first element of the array and has type int *.

A picture may help:

int [5]  int (*)[5]     int      int *

+---+                   +---+
|   | <- &a             |   | <- a
| - |                   +---+
|   |                   |   | <- a + 1
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
+---+                   +---+
|   | <- &a + 1         |   | <- *(&a + 1)
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
| - |                   +---+
|   |                   |   |
+---+                   +---+

This is two views of the same storage - on the left, we're viewing it as a sequence of 5-element arrays of int, while on the right, we're viewing it as a sequence of int. I also show the various expressions and their types.

Be aware, the expression *(&a + 1) results in undefined behavior:

...

If the result points one past the last element of the array object, it
shall not be used as the operand of a unary * operator that is evaluated.

^{C 2011 Online Draft, 6.5.6/9}

How to get size of an array using metaprogramming?

For one dimensional Arrays,

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

int arr[]={1,2,2,3,4,4,4,54,5};
cout << size_of_array(arr) << endl;     

A a[] = {A(),A(), A(), A(), A()};
cout << size_of_array(a) << endl;

Output:

9
5

Full Demo at Ideone : http://ideone.com/tpWk8

EDIT:

Another way (after seeing your edit),

template<typename T>
struct get_dim;

template<typename T, size_t N>
struct get_dim<T[N]>
{
    static const int value = N;
};

int main() 
{
       cout << get_dim<int[100]>::value;
       return 0;
}

Output:

http://ideone.com/wdFuz

EDIT:

For two dimensional arrays:

struct size2D
{
   size_t X;
   size_t Y;
};

template<typename T, size_t M, size_t N>
size2D size_of_array(T (&)[M][N])
{
   size2D s = { M, N};
   return s;
}
int arr[][5]={ {1,2,2,5,3}, {4,4,4,54,5}} ;
size2D size = size_of_array(arr);
cout << size.X <<", "<< size.Y << endl;

Output:

2, 5

Code : http://ideone.com/2lrUq

A function in the LLVM source that calculates array length

array_lengthof is a template function. This function is generated at compile time for all combination of array type and size (you pass to this function in your code) during compile time.

So if you call this function for int a[10];
Function call would be converted implicitly by compiler to

array_lengthof<int, 10>(a).

Parameter T (¶m)[N] means param is a reference to an int array of size N. (N being a compile time constant)

Can Someone Explain This Template Code That Gives Me the Size of an Array