Ivan presents a new type-safe way to write COUNTOF so that it produces a compile-time error if you accidentally pass it to anything other than the built-in array.

March 06, 2007
URL:http://www.drdobbs.com/cpp/counting-array-elements-at-compile-time/197800525

Ivan is a Lead Engineer with GE Energy, where he develops software for equipment monitoring and performance optimization. He can be contacted at [email protected].

The traditional way to find the number of elements in an array in C++ has been to calculate it using the sizeof operator. For example, to loop over the elements of an array, you might write this code:

long a[] = { 2, 3, 5, 7, 11 };
int count = sizeof(a)/sizeof(a[0]);
for ( int i = 0; i != count; ++i )
   /* ... process a[i] ... */ ;

Sometimes the sizeof expression is wrapped in a macro to make it more readable:

#define COUNTOF(x) \
   ( sizeof(x) / sizeof((x)[0]) )

In this article, I present a new type-safe way to write COUNTOF so that it produces a compile-time error if you accidentally pass it a pointer, std::vector, or anything else other than the built-in array. The new version also preserves the good features of the traditional COUNTOF, including:

• Readable notation.
• Produces a compile-time constant.
• Works even for local types.
• Works on older compilers (Visual C++ 6, for instance).

Type Safety

The COUNTOF macro just described produces correct results when the argument is a genuine array, but it silently produces bad results in other cases. For example, on a typical machine, the output of this code snippet is 1:

int* p = new int[13];
std::cout << COUNTOF(p);

Similar problems occur if the argument is a vector or other array-like class. Even more surprisingly, the following function also outputs 1:

void bad_func(int a[13])
{
  std::cout << COUNTOF(a);
}

The reason for this goes back to the C heritage of C++. Under C rules, even though the formal parameter is declared as int a[13], the compiler implicitly changes the declaration to int* a. Throughout bad_func, a isn't just convertible to a pointer, it actually is a pointer. This change applies only to function parameters, but when it happens, it can be quite unexpected.

Because COUNTOF accepts arguments of types that it does not correctly handle, it clearly is not type safe. Fortunately, the revised COUNTOF in Listing One solves these problems and produces a compile-time error if any improper argument is passed. The new COUNTOF is a drop-in replacement for the old and should work for any correct code that currently uses the old form.

// public interface
#define COUNTOF(x)  (                                           \
  0 * sizeof( reinterpret_cast<const ::Bad_arg_to_COUNTOF*>(x) ) +  \
  0 * sizeof( ::Bad_arg_to_COUNTOF::check_type((x), &(x))      ) +  \
  sizeof(x) / sizeof((x)[0])  )                                  
// implementation details
class Bad_arg_to_COUNTOF
{
public:
   class Is_pointer;  // intentionally incomplete type
   class Is_array {};  
   template<typename T>
   static Is_pointer check_type(const T*, const T* const*);
   static Is_array check_type(const void*, const void*);
};

The Built-In Array

Using COUNTOF implies that you are using C-style arrays, which in modern C++, have mostly been traded in for std::vector and other container classes. Why would you want to use an array? Most of the remaining applications come from two features of built-in arrays: They can use a C-style initializer list, and their size is fixed at compile time, which in some cases allows additional static checking and optimization. When these features are needed, and when the dynamic flexibility of container classes is not, arrays become an attractive option. (If, on the other hand, you find yourself needing to use new[] and delete[], or to track how many elements are "really" being used in an array, then container classes will usually be a better choice. They manage their own memory, track their own size, can grow as needed, and generally take care of the low-level details so that you can focus on the bigger picture.)

Initializer Lists

Unlike most container classes, arrays are allowed to use an initializer list:

// OK:
long a[] = { 2, 3, 5, 7 };
// not allowed:
vector<long> v = { 2, 3, 5, 7 };

You can explicitly add each item to a container:

v.push_back(2);
v.push_back(3);
v.push_back(5);
v.push_back(7);

However, initializing containers "by hand" is tedious and repetitive, and when programming seems tedious and repetitive, it's usually a sign that you are doing something the hard way. Another way to initialize a container is to first create an array using an initializer list, then initialize the container from the array:

vector<long> v(a, a + COUNTOF(a));

This works because an array is convertible to a pointer to its first element, and pointers qualify as iterators. You can also use arrays with STL algorithms. For example, if a were not already sorted, you could sort it like this:

std::sort(a, a + COUNTOF(a));

Notice that I never explicitly specify the number of elements in the array. The compiler gives the array whatever size is needed to hold the initializer-list, then I infer that size using COUNTOF. There is no opportunity to get the size wrong, and if I later add another item to the list and recompile, everything else will be updated automatically.

Unit Testing

One important application of initializer lists is in defining cases for automated unit testing. Consider the testing of the addition operators for a new string class, xstring. Listing Two shows one way to write the tests. The ASSERT is meant to represent whatever macro or function the unit-test framework uses to express test assertions. Using initializer lists to set up a table of test data has two advantages: First, the data is clearly laid out, separate from the actual test code; and second, there is no repetition of the code. This is particularly useful when each test case needs a few lines of setup, or when the data can be combined in multiple ways to generate extra tests "for free." For example, in Listing Two, the same data is used to test five different functions: Three forms of operator+ and two of operator+=. Similarly, for most numeric types (but not strings), if a + b == c, it should also be true that b + a == c, that a == c - b, and so on.

void test_addition_operators()
{
   struct Test_case { const char *a, *b, *sum; };
   Test_case cases[] =
   {
      //  a      b       sum
      { "abc", "xyz", "abcxyz" },
      { "abc",    "",    "abc" },
      {    "", "xyz",    "xyz" },
      {    "",    "",       "" }
   };
   for ( int i = 0 ; i != COUNTOF(cases) ; ++i )
   {
      Test_case& tc = cases[i];
      xstring a(tc.a), b(tc.b), sum(tc.sum);
      ASSERT(    a +    b == sum );
      ASSERT(    a + tc.b == sum );
      ASSERT( tc.a +    b == sum );
      a += b;  // operator+=(const xstring&)
      ASSERT( a == sum );
      a = tc.a;
      a += tc.b;  // operator+=(const char*)
      ASSERT( a == sum );
   }
}

It may look strange to define a struct right inside a function as I did, but it's perfectly legal C++. Using a local struct has the same benefits as limiting any other definition to a narrow scope. I am only using the struct in this one function, and defining it inside the function makes that immediately clear. It also saves you from having to hunt for the definition by putting it right at the point of use. It prevents namespace pollution, and as a result, saves you from having to invent new (and usually more verbose) names for a "Test_case."

Unit tests are really just a particular example of a general idiom for writing table-driven code. When faced with a repetitious series of operations, you can often drive out the duplication by extracting just the parts that vary, putting them into a table, then looping over the rows of that table. The table could be in a database or external file when needed, but putting it directly in code gives you a powerful combination of efficiency and clarity.

Compile-Time Assertions

Arrays are not just a convenience feature. Since their size is fixed at compile time, they can be used in compile-time checks that would not otherwise be possible. For example, suppose I have an enumeration, and I want to associate a string with each enumerated value. Listing Three works but is not very robust because it gives incorrect results if I later add a new value to the enum but forget to update the array. By making a couple of minor changes to the code (Listing Four), I can make the compiler double-check my work. COMPILE_TIME_ASSERT is a macro that takes a compile-time constant as its argument. (For an implementation, see the complete source code for this article; refer to "Resource Center," page 5.) If the argument is True, the macro has no effect. If it is False, the macro produces a compile-time error. In Listing Four, the assertion is that the enum and the array have the same number of elements. Therefore, if the enum and array should ever get out of sync, the compiler lets me know about it.

// in Color.h
enum Color
{
   red, blue, green,
};
// in Color.cpp
const char* color_names[] = { "red", "blue", "green" };
const char* get_name(Color c)
{
   return color_names[c];
}

// in Color.h
enum Color
{
   red, blue, green,
   last_color  // one-past-the-end value; must be last
};
// in Color.cpp
const char* color_names[] =
   { "red", "blue", "green", "invalid color" };
const char* get_name(Color c)
{
   return color_names[c];
}
COMPILE_TIME_ASSERT( COUNTOF(color_names) == last_color + 1 );

Implementation

The design goals for COUNTOF were to:

• Preserve the good features of the traditional COUNTOF.
• Present users with a type-safe interface.
• Generate error messages that at least hint at the problem when an inappropriate argument is passed.

COUNTOF achieves those goals, but the required implementation is a bit obscure (Listing One). In pseudocode, it is simply:

if x is not an array
   issue a compile-time error
else
   use the traditional COUNTOF expression

Probably the best way to understand how COUNTOF does this is to break it into parts. The macro expands to an expression that can be summarized like this:

0 * sizeof(check1) +
0 * sizeof(check2) +
sizeof(x) / sizeof((x)[0])

The first thing to note is that the first two sizeof expressions are not really being used to compute the size of anything. Because they are both multiplied by zero, they do not make any contribution to the result. They are just convenient vehicles for some type checks to verify that the argument is an array.

The check1 expression reinterpret_casts the macro argument x to a pointer. The cast is never actually executed; it is just part of a compile-time check. If the argument is an object of class type, such as an std::vector, then the cast is not legal and the compiler issues an error. The same thing happens if the argument is a floating-point type, a function pointer, or a pointer-to-member. Any pointer to an object would work as the result type, but I chose Bad_arg_to_COUNTOF* (and named the class that way) because the result type is likely to show up in any compiler error messages, and that name gives users a hint at what the problem is.

If the reinterpret_cast succeeds, then x must be an integral or enumerated type, a pointer to an object, or an array. The compiler moves on to the check2 clause. This part of the macro expands approximately to sizeof(check_type(x, &x)), where check_type is an overloaded function [1]. Because this is purely a compile-time computation, the function is never really called or even implemented, but it lets the compiler apply overload resolution to do some further type discrimination. There are three possibilities to consider:

• x is an integral or enumerated type. In this case, neither of the two overloads is a match, and the compiler issues an error.
• x is a pointer to an object. If x is a pointer, then the first argument of check_type is a pointer and the second one is a pointer-to-pointer. The best match is the first overload of check_type, the one that returns an Is_pointer. Because Is_pointer is an incomplete type, sizeof(Is_pointer) is not a valid expression, and again the compiler issues an error.
• x is an array. If x is an array, then the first argument to check_type is an array and the second is a pointer-to-array. A pointer-to-array is not convertible to a pointer-to-pointer, so the first overload of check_type is not a match. However, an array is convertible to a pointer, and a pointer-to-array already is a pointer. Any pointer is convertible to a void*, so the second overload is a match. That overload returns an Is_array, which is a complete type for which sizeof(Is_array) is a valid expression.

At this point, the compiler has excluded every possible type except arrays. The first two lines have reduced to zeros, and the compiler moves on to the third. That line is just sizeof(x)/sizeof((x)[0]); that is, the size in bytes of the entire array divided by the size in bytes of a single element, which yields the number of elements in the array. This is the same expression used by the traditional COUNTOF, and it gives the same result.

Conclusion

The new COUNTOF macro preserves all the benefits of the traditional COUNTOF, while adding the type safety that macros often lack. Its only real disadvantage is the cryptic code needed to implement it. However, because the complexity is hidden behind a simple and well-defined interface that exactly matches the original, it is not a serious problem.

Acknowledgment

Thanks to Andrew Hopkins for his thoughtful review of a draft of this article.

References

• [1] The method of eliminating pointers with sizeof and a pair of overloaded functions is based on one devised by Jonathan Lundquist. See groups.google.com/group/comp.lang.c++.moderated/browse_thread/thread/bd3b7cc6e26d3ebe.
• [2] The countof and count function templates are adapted from ones by Dietmar Kuehl and Siemel Naran, respectively. See groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/d0faf979c493c19c and groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/8e45b21773e191ea.

double dist(const double x[3]);

double dist(const double(&x)[3])
{
  return sqrt( x[0] * x[0] +
               x[1] * x[1] +
               x[2] * x[2] );
}
double a[] = { 3, 4, 5 };
double d = dist(a);  // OK
double b[] = { 3, 4, 5, 6 };
double d2 = dist(b);  // error

// ... a[] is some array ...
int ct = countof(a);
for ( int i = 0; i != ct; ++i )
 /* ... process a[i] ... */ ;

// returns the number of elements in the passed array
template<typename T, int N>
inline int countof(const T(&)[N])
{
   return N;
}
// a struct defined such that sizeof(Size<N>::Type) == N
template<int N>
struct Size
{
     typedef char Type[N];
};
// returns an object whose size is the number of 
// elements in the passed array
template<typename T, int N>
typename Size<N>::Type& count(const T(&array)[N]); 

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.