Counting stars in C++

August 29, 2014


The company I work for is looking to hire another C++ developer. So I got to thinking about interview questions in general, and questions that would demonstrate an understanding of C++ pointer arithmetic in particular. Then an interesting question occurred to me. I'm not planning to actually ask this question (or any such questions), but I found it interesting and I couldn't find any similar question online - so I'm sharing both the challenge and my solution here.

The challenge

Can you write code to count the number of stars (i.e. the level of pointer indirection) used by a variable?

The easiest way to explain this is by writing the challenge as code:

#include <iostream>

constexpr int count_stars(...)
{
    // To solve, implement this method
}

int main(int argc, const char * argv[])
{
    // How many stars are on the next line?
    constexpr const int ****************************************** p_nasty = nullptr;
    
    std::cout << "There are " << count_stars(p_nasty) << " stars \n";

    static_assert(count_stars(p_nasty) == 42, "Should work at compile time");

    return 0;
}

My Solution

An ugly way to solve this that occurred to me later: count the instances of * or P in the string typeid(p_nasty).name(). However, that would be compiler-specific and is not very robust.

It turns out to be relatively easy to do this properly as a recursive templated function thanks to the C++11 standard library remove_pointer method. We simply write a method that returns zero if given a non-pointer type, and otherwise returns one plus that value returned by itself when called with the same type dereferenced one time.

#include <iostream>

// Implementation of count_stars:
template<typename ptype>
constexpr int count_stars()
{
	typedef typename std::remove_pointer<ptype>::type next;
	return std::is_same<next, ptype>::value ? 0 : count_stars<next>() + 1;
}

// Syntactic sugar:
template<typename ptype>
constexpr int count_stars(ptype p)
{
	return count_stars<ptype>();
}

int main(int argc, const char * argv[])
{
	// How many stars are on the next line?
	constexpr const int ****************************************** p_nasty = nullptr;
	
	std::cout << "There are " << count_stars(p_nasty) << " stars \n";

	static_assert(count_stars(p_nasty) == 42, "Should work at compile time");

    return 0;
}
comments powered by Disqus