5
\$\begingroup\$

I'm new to template meta-programming and wrote some code to determine if a number is a perfect square. For example, in my program, SQUARE<1>::value and SQUARE<4>::value evaluate to true while SQUARE<5>::value is false. I'm open to any suggestions on how I could implement this better, cleaner, or make use of standard library functions. Also, please point out any meta-programming conventions I may have overlooked.

template<bool condition, bool Then, bool Else>
struct IF {
   static const bool ret = Then;
};

template<bool Then, bool Else>
struct IF<false, Then, Else> {
   static const bool ret = Else;
};

template<size_t v1, size_t v2>
struct GREATER {
   static const bool ret = v1 > v2;
};

template<size_t n, size_t r>
struct IS_SQUARE {
   static const bool value = IF<n == r*r,
                true,
                IF<GREATER<n, r*r>::ret,
                   IS_SQUARE<n, r+1>::value,
                   false>::ret
                >::ret;
};

template<size_t n>
struct IS_SQUARE<n, n> {
   static const bool value = false;
};

template<size_t n>
struct SQUARE {
   static const bool value = IS_SQUARE<n, 1>::value;
};

template<>
struct SQUARE<1> {
   static const bool value = true;
};

// example usage
int main() {
   static_assert(SQUARE<1>::value, "must be square");
   static_assert(SQUARE<4>::value, "must be square");
   static_assert(SQUARE<5>::value, "must be square"); // compile error
}
\$\endgroup\$
  • \$\begingroup\$ Does your use of static_assert indicate that C++11 features are okay in general? Because the code could be much improved by using constexpr. \$\endgroup\$ – sepp2k Dec 24 '11 at 0:22
  • \$\begingroup\$ Yes, c++11 features are okay. \$\endgroup\$ – Tyler Hyndman Dec 24 '11 at 0:24
  • \$\begingroup\$ Hm. If my proposal doesn't use templates at all (while still evaluating everything at compile time (so you'd still be able to use the result from inside other templates) and supporting static_assert), would that still be in the spirit of the exercise? \$\endgroup\$ – sepp2k Dec 24 '11 at 0:39
  • \$\begingroup\$ @sepp2k I wasn't aware of constexpr. I guess I could have stated my question more generally as wanting a compiler error if a number that isn't a perfect square is used. \$\endgroup\$ – Tyler Hyndman Dec 24 '11 at 8:31
6
\$\begingroup\$

I'd recommend against using ALL_CAPS for class-names. It's not really in accordance with C++ conventions.

template<size_t n, size_t r>
struct IS_SQUARE {
   static const bool value = IF<n == r*r,
                true,
                IF<GREATER<n, r*r>::ret,
                   IS_SQUARE<n, r+1>::value,
                   false>::ret
                >::ret;
};

You can replace the outer if with || (if foo then true else bar is equivalent to foo || bar) here to get rid of one level of nesting and simplify the condition a bit. One might think that you can also replace the inner if with &&, but that won't work because template-instantiation doesn't short-circuit in the way you'd want it to when using logical operators (i.e. foo && Bar<baz> will try to instantiate Bar<baz> even if foo is false, leading to infinite recursion in this case).

template<size_t n>
struct SQUARE {
   static const bool value = IS_SQUARE<n, 1>::value;
};

You might want to use 0 instead of 1 as the starting value here. Otherwise you'll get incorrect results for n=0 (which is a square of itself and should thus return true).

template<>
struct SQUARE<1> {
   static const bool value = true;
};

This is redundant because IS_SQUARE<1, 1> (or IS_SQUARE<1,0>) is true anyway.


Apart from the nitpicks listed above, your code looks fine (or as fine as TMP code ever looks, anyway). However it can be completely replaced using constexpr, which still gives you compile-time evaluation (including the ability to use the result inside template arguments or static_assert), while being greatly more readable:

The beauty of C++11's constexpr feature is that it allows you to write compile-time expressions using normal C++ syntax, instead of encoding everything using template classes. You're not allowed to use loops or any side-effects, so you still have to use the recursive approach you used (as opposed to the iterative approach you'd probably use at run-time), but it can be greatly simplified by expressing it as a simple recursive function instead of a bunch of templates:

constexpr bool is_square(size_t n, size_t r=0) {
    return (r*r == n)  ||  ( (r*r < n) && is_square(n, r+1));
}

int main() {
    static_assert(is_square(1), "must be square");
    static_assert(is_square(4), "must be square");
    static_assert(is_square(5), "must be square"); // compile error
}

As a learning-exercise for template meta programming this version is completely useless, of course, as it does not actually contain any templates. But it's definitely more readable (and more writable as well) and can be used in any scenario where the template-version can be used. So in any real C++11 meta-programming project, I'd always recommend using constexpr over templates when it's possible. This way you can perform your calculations in functions that look like C++ functions (well, C++ functions that are written in a surprisingly functional style) and use templates to define classes (which depend on the results of those calculations).

\$\endgroup\$
  • \$\begingroup\$ Thanks! I definitely like the constexpr better than using templates since it is much clearer and should be easier maintain. \$\endgroup\$ – Tyler Hyndman Dec 24 '11 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.