How does sizeof work when passing a template array?

Question

Since sizeof and templates are both compile-time. What is it about the second parameter of the template that determines the size without specifying it in the caller function?

template <typename T, size_t n> bool isInHaystack(const T (&arr)[n], const T &needle)
{ /* I know const references are best with strings and non-primitives and should
     be mitigated when using ints as in the example.*/
    size_t i, size = sizeof arr / sizeof T; // how does it know n is the size?
    for (i = 0; i < size; ++i)
        if (arr[i] == needle)
            return true;
    return false;
}

int main(int argc, char **argv) {
    int arr[] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 };
    cout << isInHaystack(arr, 7) << endl;
    isInHaystack<int, (size_t)(sizeof(arr) / sizeof(int))>(arr, 7); // this works, too


    return 0;
}

How does this size_t n get its value when passing an array? How does it know without providing it explicitly?

To make this a little more clear, this will not compile:

template <typename T> bool foo(const T(&arr)[], const T needle) {
    cout << sizeof arr << endl;
    return true;
}
int main(){
    int arr[] = {1,2,3};
    foo(arr, 1); // Error: could not deduce template argument for 'const T (&)[]' from 'int [21]'
}

What is the issue?

No, it's not. It's a compile time constant given in the initialization of the `arr` in `main` (although implicitly). — Baum mit Augen, Feb 17 '16 at 22:42
Are you asking *in `templatevoid fn(const char (&str)[n]) {};` what mechanism does the compiler use to find the correct value for `n` when I pass it an array?* — kfsone, Feb 17 '16 at 22:43
@Goodies That's just good old [Template Argument Deduction](http://en.cppreference.com/w/cpp/language/template_argument_deduction). — Baum mit Augen, Feb 17 '16 at 22:45
Also http://stackoverflow.com/questions/3368883/how-does-this-size-of-array-template-function-work and http://stackoverflow.com/questions/2384107/magic-arguments-in-function-templates/2384187 — AnT stands with Russia, Feb 17 '16 at 22:50
@BaummitAugen That's it. Although I am curious about kfsone's comment in terms of the compiler. — Goodies, Feb 17 '16 at 22:51
@Goodies So you are asking how TAD is implemented? That is probably not trivial, but feel free to look at the source of clang or gcc to find out. :) — Baum mit Augen, Feb 17 '16 at 22:57
The key is that your array does _not_ have type `int[]`. That's an illusion. It has type `int[11]`. Unless you want to find out how template metaprogramming is _implemented_ inside your compiler (which I doubt), that's probably all you need to know for a eureka moment. There is, in fact, no such thing as a "template array". — Lightness Races in Orbit, Feb 17 '16 at 23:11
@kfsone: Shame, I liked your answer. Well, except for the brazen lie "Arrays and pointers are equivalent" :) Given that you went on to say "not the same" I suspect you meant something else though. — Lightness Races in Orbit, Feb 17 '16 at 23:13
@PreferenceBean To quote the page I linked: "Saying that arrays and pointers are ``equivalent'' means neither that they are identical nor even interchangeable.". I undeleted and added clarification (I only deleted because I saw the question had been closed) — kfsone, Feb 17 '16 at 23:24
@kfsone: Right, but take those away and what does "equivalent" mean? In reality, that FAQ is fairly dangerously misleading and is talking about antiquated implementation details that may not always even be true any more in the world of optimising compilers, let alone something that one should consider while actually writing in the abstraction that is C++ (or C). I'd avoid quoting that particularly strange usage of that particular word, in this particular context. :) — Lightness Races in Orbit, Feb 18 '16 at 01:30

kfsone · Accepted Answer · 2016-02-18T17:50:36.947

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 sizeof work when passing a template array?

1 Answers1