Enterprise FizzBuzz in C++11

Question

I've decided to write a C++ FizzBuzz with the focus on some new C++11 features, ridiculous optimizations and unit-testability.

Are there improvement possibilities in those regards?

template <typename T>
static void fizzbuzz(std::ostream& out, const T& number, const std::vector<std::pair<std::string, T>>& values)
{
    bool found = false;

    std::for_each(values.begin(), values.end(),
        [&](decltype(*values.begin()) i)
        {
            if (0 == number % i.second)
            {
                out << i.first.c_str();
                found = true;
            }        
        }
    );

    if (!found)
    {
        out << number;
    }
}

template <typename T>
static void filter_fizzbuzz(const T& end, std::vector<std::pair<std::string, T>>& values)
{
    // Needs to be sorted as the filtering only looks for divisible numbers up to the current one
    std::sort(values.begin(), values.end());

    for (auto i = values.begin(); i != values.end();)
    {
        // i > end will never become 0
        if (i->second > end)
        {
            i = values.erase(i);
            continue;
        }

        // Is the current number already handled by a divisor?
        bool alreadyHandled = false;
        for (auto j = values.begin(); j != i; j++)
        {
            if (0 == i->second % j->second)
            {
                alreadyHandled = true;
            }
        }

        if (!alreadyHandled)
        {
            i++;
            continue;
        }

        i = values.erase(i);
    }
}


template <typename T>
void fizzbuzz(std::ostream& out, const T& start, const T& end, std::vector<std::pair<std::string, T>>& values)
{
    if (start > end)
        throw std::out_of_range("start > end");
    if (!values.size())
        return;

    filter_fizzbuzz(end, values);
    for (T i = start; i < end; i++)
    {
        fizzbuzz(out, i, values);
        out << std::endl;
    }
}

Answer 1

Squash the bug!

When you call std::sort() in filter_fizzbuzz(), it performs a lexicographic sort on the pair elements. That means that you are sorting first by the string, and then by the divisor value. If, for example, you supplied the pairs {"vizz", 3"} and {"buzz", 5}, your program would print buzzvizz when you reached 15, which is probably not what you intended. You should swap the pair element ordering to be pair<T, std::string> to sort the elements by divisor value (you will also have to swap usages of first and second, obviously). Which leads me to my next point...

Use the right data structure

You require values to be sorted in ascending order by divisor value. You don't state it explicitly, but it makes sense to require that each divisor value is unique. Both these requirements sound like what is guaranteed by std::map. (If uniqueness is not necessary, then use a std::multimap). All your declarations:

std::vector<std::pair<std::string, T>>& values

should be changed to:

std::map<T, std::string>& values

This makes the code shorter, enforces more guarantees about values, and is more efficient:

• You can remove your call to std::sort() entirely.
• erase is O(N) for vector, but O(log N) for map.

Changing to map allows other parts of your code to be simplified as well. The lines:

for (auto i = values.begin(); i != values.end();)
{
    // i > end will never become 0
    if (i->second > end)
    {
        i = values.erase(i);
        continue;
    }

// more code...

can be rewritten to be shorter and clearer:

const auto end_iter = values.upper_bound(end);
for (auto i = values.begin(); i != end_iter;)
{
// more code...

This doesn't modify the contents of values like the original, but provides the same iteration range.

Use standard algorithms

Your code can be simplified if you use the algorithms provided by the standard library. In general, you should prefer using standard algorithms because they convey your intent clearly, as well as limiting opportunities for bugs to creep in. Thus, checking whether a divisor is already handled shortens from this:

bool alreadyHandled = false;
for (auto j = values.begin(); j != i; j++)
{
    if (0 == i->second % j->second)
    {
        alreadyHandled = true;
    }
}

To this:

using value_type = decltype(*values.begin());
const bool alreadyHandled = std::any_of(values.begin(), i, [&]
                                        (value_type v)
                                        {
                                            return i->first % v.first == 0;
                                        });

I've provided a type alias for the decltype expression, since it is not immediately apparent what it means. Note also this allows alreadyHandled to be declared const, which you should strive for. const-correctness allows the compiler to make more guarantees about your program. I personally try to limit mutability as much as is feasible, since fewer mutable variables means fewer opportunities for bugs.

Is filter_fizzbuzz necessary?

I was surprised that filter_fizzbuzz removes elements that are already divisible by another element in values. To me, this violates the Principle of Least Astonishment. If I added an entry {15, "jazz"}, it would be removed, and only fizzbuzz would be printed when 15 was reached, even though I would expect fizzbuzzjazz to be printed. This will make your program more efficient by removing all calls to erase, and shorter and clearer. You can also increase const-ness, since values is no longer modified, the second fizzbuzz() can take values by a const reference.

Yoda conditions

When you compare against a constant value, you write the constant first:

if (0 == number % i.first)

This is called a Yoda condition. I find it less readable than the more natural ordering,

if (number % i.first == 0)

If you're worried about accidental assignment in the if, compile with -Wall -Wextra, which will give a warning if you do forget one =.

Answer 2

Know when to use which feature

C++11 offers range based for loops so you should use them instead of for_each with lambdas:

for(auto i: values) {
    if (0 == number % i.second) {
        out << i.first.c_str();
        found = true;
    }        
}

As you can see this facilitates auto instead of the ugly decltype hack.

Don't overuse static

Why are all the functions declared static? Are they part of a class? If so, why?

Design: Unnecessary complexity

I have troubles tracing the algorithm in your code. If you would really want an enterprise solution I would try to integrate with standards like iterators and function(/functor) interfaces that can be passed into algorithms like std::transform.

Answer 3

There is a bug in your code.

std::sort(values.begin(), values.end());

You are sorting by the string value rather than by the numeric value. So for instance, if I do this:

int main (void)
{
    const std::pair <std::string, int> vals [] = {
        std::pair <std::string, int> ("Fizz", 7),
        std::pair <std::string, int> ("Buzz", 9),
        std::pair <std::string, int> ("Cuzz", 10),
    }; // I don't have uniform initialization on my compiler

    std::vector <std::pair <std::string, int> > v (vals, vals + 3) ;

    fizzbuzz (std::cout, 0, 100, v) ;

    return 0 ;
}

When comparing to 0, the output is BuzzCuzzFizz rather than FizzBuzzCuzz. People would be quite angry if they failed their interviews because they decided to cheat and use your program. You could help these people out by making this small change:

typedef std::pair<std::string, T> pair_type ; // I don't have the new *using* syntax
auto CompareSecond = [] (const pair_type &lhs, const pair_type &rhs) {
    return lhs.second < rhs.second ;
};

std::sort(values.begin(), values.end(), CompareSecond);