13
\$\begingroup\$

I am learning to write more modern C++, since my C++ is from the 1990s (I'm a C# programmer). I need to get used to the STL algorithms and such. So I tried some kata, summing up numbers in a given range that are divisible by 3 or 5, using new C++11/14/17 stuff.

I know that it can be solved mathematically in O(1), but this question is not about performance. You can of course make performance suggestions, but not the O(1) mathematical complete rewrite, please.

First of all, let me say I am quite happy with the main method. That's sort of how I imagined it shall look like. It uses an iterator and an STL algorithm to sum it up.

int main()
{   
    MultiplesOf3Or5Iterator<1,999> numberGenerator;
    std::cout << std::accumulate(numberGenerator.begin(), numberGenerator.end(), 0L) << '\n';
}

I took the idea of an iterator from Cpp Reference, but I got some warnings for the code there, which guided me into a direction of not inheriting from std::iterator. So this is what I came up with. It contains comments of where I'm still not happy with the result.

template<long FROM, long TO>
class MultiplesOf3Or5Iterator {
public:
    class iterator {
    public:
        using iterator_category = std::input_iterator_tag;
        using value_type = long;
        using difference_type = long;
        using pointer = const long*;
        using reference = long;

    public:
        explicit iterator(long _num = 0) : num(_num) {
            // I really don't like the cast in here
            direction = isForward()
                ? static_cast<std::function<long(long, long)>>(std::plus())
                : std::minus();

            ++(*this); // start with the first valid number
        }
        iterator& operator++() {

            do {
                num = direction(num, 1);
            } while (!isDivisable());
            return *this;
        }
        iterator operator++(int) { ++(*this); iterator retval = *this;  return retval; }
        bool operator==(iterator other) const { return num == other.num; }
        bool operator!=(iterator other) const { return !(*this == other); }
        reference operator*() const { return num; }

    private:
        long num = FROM;
        std::function<long(long, long)> direction;
        std::vector<long> const divisors{ 3,5 }; // no need to make these configurable at the moment
        bool isDivisable() const {
            // While this is a "modern" style foreach loop, I don't really like this part. 
            // I think there should be a more expressive style
            for (long divisor : divisors)
            {
                if (num % divisor == 0)
                {
                    return true;
                }
            }
            return false;
        }
        bool isForward() const { return TO >= FROM; }
    };

    iterator begin() { return iterator(FROM); }
    iterator end() { return iterator(TO); }
};

And yeah, honestly, that's quite a bunch of code just to have some numbers which are divisible by 3 or 5. It kinda violates the KISS and YAGNI principle.

What have I tried?

  • I looked up the Forum of the source of the kata, but the C++ answers there are either optimized or written in the 1990 old C-like style, not using any modern C++ stuff (which is ok, but not what I want to learn right now).
  • I looked up several Fizzbuzz C++ questions here on Code Review, but none seems to use an iterator approach like mine.
\$\endgroup\$
8
  • 1
    \$\begingroup\$ Using C or C++ these days is always about performance, that is what makes these languages so important. Why else use an object oriented language with no garbage collection and required memory management. \$\endgroup\$
    – pacmaninbw
    Aug 13, 2022 at 15:47
  • \$\begingroup\$ @pacmaninbw: it's probably a bit more complicated than that. Say you have 10 C++ developers. Would you try to make all of them C# developers, just because performance is not a real issue? Or would you rather try to fit 1 C# developer in the C++ project? Would you convert the 2 MLoC C++ solution into C#? Or would you introduce yet another technology like C++/CLI and try to merge C++ with C#? \$\endgroup\$ Aug 14, 2022 at 7:37
  • \$\begingroup\$ Depends on the project and the company. I learned both C++ and C# at the same company at different times, it was learn or lose my job because they were changing platforms. It affected around 40 C developers moving to C++ and 60 C++ developers moving to C#. The embedded code was staying in C++, the system code moved to C#. \$\endgroup\$
    – pacmaninbw
    Aug 14, 2022 at 12:37
  • 2
    \$\begingroup\$ Naturally, using a closed formula would be more efficient. But I think this is more about getting acquainted with standard algorithms and writing your own iterator. \$\endgroup\$ Aug 14, 2022 at 21:36
  • \$\begingroup\$ To avoid confusion, the templates of the C++ Standard Library are not the "STL", unless you truly mean the STL library originally by Stepanov or the later one by Silicon Graphics (both of which are ancient). \$\endgroup\$
    – qwr
    Aug 14, 2022 at 23:40

3 Answers 3

20
+100
\$\begingroup\$

Design review

Not bad! There is a little bit of conceptual confusion (you have an iterator that has an iterator?), and perhaps a little bit of over-engineering, but generally this design is quite good. I really like the ergonomics of it—your main() function is indeed beautiful; that’s what good C++ code looks like.

Before I review your design, let me show you roughly what I might have done had I chosen to do the same project. This is because what I would have done is almost identical what you would have done, but for a few divergent design decisions that I want to highlight, and it’s quicker to illustrate those few differences rather than explain them.

Right, so if I were doing this—making a custom iterator that returns the FizzBuzz magic numbers (numbers divisible by 3 and 5)—I would start with just the iterator, like so:

// Instead of assuming long, I'm leaving the type as a template parameter.

// I'm also taking a predicate as a template parameter, which increases the
// flexibility of the type. To duplicate the behaviour of your iterator, you
// would use this predicate:
//  template <typename T>
//  struct fizzbuzz_predicate
//  {
//      constexpr auto operator()(T const& v) const noexcept
//      {
//          return ((v % 3) == 0) or ((v % 5) == 0);
//      }
//  };

// We'll name it later.
template <typename T, typename Predicate>
class ???_iterator
{
    T _current;

public:
    // Note: I'm making this iterator bidirectional, not just input. Input
    // is too restrictive. We *might* go all the way to random access...
    // but... well, we'll discuss it later.
    using iterator_category = std::bidirectional_iterator_tag;

    using value_type = T;

    // Could use long here, but ptrdiff_t is the "correct" type (by default).
    using difference_type = std::ptrdiff_t;

    // Iterators need a default constructor, but it can leave the iterator
    // in an unspecified state.
    constexpr ???_iterator() = default;

    // !!! This is not a good constructor to have as part of the public
    // interface... but bear with it for now
    constexpr explicit ???_iterator(T v) : _current{std::move(v)} {}

    // Required for all iterators:
    constexpr auto operator*() const noexcept { return _current; }
    constexpr auto operator++() -> ???_iterator&
    {
        auto const predicate = Predicate{};

        do
        {
            // Note that I'm not supporting automatically decrementing. I'll
            // explain why later.
            ++_current;
        } while (not predicate(_current));

        return *this;
    }
    constexpr auto operator++(int) -> ???_iterator
    {
        auto temp = *this;
        ++(*this);
        return temp;
    }

    // Required for bidi iterators:
    constexpr auto operator--() -> ???_iterator&
    {
        auto const predicate = Predicate{};

        do
        {
            --_current;
        } while (not predicate(_current));

        return *this;
    }
    constexpr auto operator--(int) -> ???_iterator
    {
        auto temp = *this;
        --(*this);
        return temp;
    }

    // In C++20, this is all you need. operator!= is automatically synthesized.
    constexpr auto operator==(???_iterator const&) const noexcept -> bool = default;
};

That’s a very rough first pass of the iterator I’d make to solve this problem.

So, first, you’ll note that I made it bidirectional, rather than just an input iterator. In your case, I would say that at the very minimum, it should be a forward iterator, not an input iterator. “Input iterator” means that you can’t expect to get the same sequence if you run the iterator twice. In other words:

auto numberGenerator = MultiplesOf3Or5Iterator<1, 999>{};
auto first = numberGenerator.begin();
auto last  = numberGenerator.end();

std::ranges::for_each(first, last, [](auto&& n) { std::cout << n << ' '; }

// If the iterator is an input iterator, then we should expect a different
// result from what we got in the line above.
// If the iterator is a forward iterator, then we should get the same result.
std::ranges::for_each(first, last, [](auto&& n) { std::cout << n << ' '; }

Given that you would expect to get the same sequence for both runs through it, this means that it should be a forward iterator, not an input iterator.

I actually went a little further, and made it a bidirectional iterator. This was a design descision, and one that comes with consequences. Bidirectional iterators are much more useful than forward iterators… but the cost is that it makes it much more difficult to implement automatic decrementing.

You see, your iterator automatically detects when FROM is greater than TO, and if so, uses std::minus instead of std::plus. That’s cool, but it only really works if you allow one directional traversal. If you want bidirectional traversal, then you need to use two function objects: you need std::plus and std::minus, and you need to swap them around depending on the direction. That’s a lot more complexity.

See, I could do that… but… there’s a very good reason not to put too much complexity into a single “thing”, and that is that you can always externalize that complexity and reuse it. Let me put that in simple English: you could do what you did, and build an iterator that is smart enough to go both ways… or… you could build a much simpler iterator, and take advantage of std::ranges::reverse_view. And the latter, in my opinion, is what modern C++ is really about.

So you see, you could either massively complicate your iterator to allow going downward from 100 to 1 as auto v = MultiplesOf3Or5Iterator<100, 1>{};or… you could make a simple iterator, and just do auto v = MultiplesOf3Or5Iterator<1, 100>{} | std::ranges::views::reverse;. (Or you could use reverse iterators; you have options!) For me, the latter makes more sense.

The next design decision I made was to make the value type const. This seems like the only sensible choice. If the value type isn’t const, then you could do:

auto numberGenerator = MultiplesOf3Or5Iterator<1, 999>{};
auto first = numberGenerator.begin();

*first = 1234; // <- what?

Now, having made that iterator, the next thing I’d do is make a view out of it. That’s actually what MultiplesOf3Or5Iterator is. It’s not an iterator, it’s a view. A view is a range that doesn’t hold any data, but merely provides iterators that give a view of something. (A range that holds data is a container, like std::vector.) In your case, MultiplesOf3Or5Iterator is a view that provides iterators that gives a view of a sequence of numbers that satisfy the FizzBuzz rule (divisible by 3 or 5).

So, here’s how I’d write that view:

template <typename T, typename Predicate>
class fizzbuzz_view
    : public std::ranges::view_interface<fizzbuzz_view<T, Predicate>>
{
    // Doesn't need to be public!
    class iterator
    {
        T _current;

    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = std::add_const_t<T>;
        using difference_type = std::ptrdiff_t;
        using pointer   = value_type*;
        using reference = value_type&;

        constexpr iterator() = default;

        // Could now make this constructor private, and make the view a
        // friend, so that only the view can construct iterators.
        constexpr explicit iterator(T v) : _current{std::move(v)} {}

        constexpr auto operator*() const noexcept -> reference { return _current; }

        constexpr auto operator++() -> ???_iterator&
        {
            auto const predicate = Predicate{};

            do
            {
                ++_current;
            } while (not predicate(_current));

            return *this;
        }

        constexpr auto operator++(int) -> ???_iterator
        {
            auto temp = *this;
            ++(*this);
            return temp;
        }

        constexpr auto operator--() -> ???_iterator&
        {
            auto const predicate = Predicate{};

            do
            {
                --_current;
            } while (not predicate(_current));

            return *this;
        }

        constexpr auto operator--(int) -> ???_iterator
        {
            auto temp = *this;
            --(*this);
            return temp;
        }

        // In C++20, this is all you need. operator!= is automatically synthesized.
        constexpr auto operator==(???_iterator const&) const noexcept -> bool = default;
    };

    T _start;
    T _finish;

public:
    constexpr fizzbuzz_view(T s, T f)
        : _start{std::move(s)}
        , _finish{std::move(f)}
    {
        // Might want to verify that start <= finish.
    }

    constexpr auto begin() const { return iterator{_start}; }
    constexpr auto end() const { return iterator{_finish}; }
};

That’s basically all you need.

With that, you could do:

// Print all fizzbuzz values between 1 and 99:
std::ranges::for_each(fizzbuzz_view{1, 99}, [](auto&& v) { std::cout << v << '\n'; });

// Print the first 3 fizzbuzz values between 1 and 99, in reverse order:
for (auto&& v : fizzbuzz_view{1, 99} | std::ranges::views::take{3} | std::ranges::views::revesre)
    std::cout << v << '\n';

// Your example:
auto const v = fizzbuzz_view{1L, 999L};
auto const sum = std::accumulate(std::ranges::begin(v), std::ranges::end(v), 0L);

… and more.

I would suggest you research ranges and views. That’s what you are skirting around, and that is what the future of C++ looks like. You are… almost… there, which is why your code is already very good modern C++. But as you can see, going 100% of the way to ranges and views comes with incredible benefits. And those benefits will only get better. This is the direction future C++ is going in.

So, in summary:

  1. You have some conceptual confusion. You don’t have an iterator with an iterator, you have a view with an iterator. Getting the concepts and terminology correct is important, because it helps you realize how to integrate your type with the standard library, and other people’s libraries.

  2. Your iterator’s category should be at least forward iterator. However, since it is so trivial to implement decrementing, you might as well make it bidirectional as well.

  3. You have made your iterator intrinsically bidirectional—meaning that ++ will make it go forward or backward. That’s not wrong… however… I would suggest simplifying, and making ++ only go forward, while adding -- to go backward. Surprisingly, this simplification makes the iterator more flexible, because now it will work with reverse views (and reverse iterators), so you can integrate so much more easily with other stuff.

Code review

template<long FROM, long TO>

First, you should never use ALL_CAPS identifiers. By convention ALL_CAPS is reserved for macros.

Now, there is really no reason to hard-code long as the value type. There’s no reason to prevent users from using, say, int or unsigned long long.

The easiest way to increase flexibility is to simply do:

template <auto From, auto To>

Of course, you want to make sure that the two types are the same, so:

template <auto From, decltype(From) To>

// or:
template <auto From, auto To>
    requires std::same_as<From, To>

But it might be a good idea to constrain the type, because it has to be an integer (otherwise you can’t use operator%), so:

template <std::integral auto From, decltype(From) To>

However… I would suggest that encoding the from and to limits in the type isn’t a good idea at all.

You see, when you encode the limits in the type, you are telling me that MultiplesOf3Or5Iterator<1, 10> and MultiplesOf3Or5Iterator<2, 20> are completely different “things”. You are telling me that a function that iterates over the first type must be a completely different function than one that iterates over the second type. But that’s… silly. There’s no reason a single function couldn’t iterate over a fizzbuzz range from 1 to 10 or 2 to 20.

I get that in ages past, the only way to encode compile-time constants was to use template parameters like that. But these days, that’s no longer necessary.

So I would suggest simply doing:

template <std::integral T>
class MultiplesOf3Or5View   // <- note: view, not iterator

Now the view class really only needs begin() and end(). Even iterator doesn’t need to be part of the public interface, but there’s no harm.

However, if you’re no longer putting the limits in the type, you will probably need a constructor to set those limits, so your view class will probably look like:

template <std::integral T>
class MultiplesOf3Or5View
{
    T _start;
    T _finish;

public:
    constexpr MultiplesOf3Or5View(T start, T finish)
        : _start{std::move(start)}
        , _finish{std::move(finish)}
    {
        // Might want to verify that start <= finish
    }

    constexpr auto begin() const { /* ... */ }
    constexpr auto end() const { /* ... */ }
};

Now, into iterator.

I already mentioned that the category should be at least fowrard iterator. I would also drop pointer and reference; you don’t need them.

I’m going to skip down to the member variables, and come back to the rest of the class:

        long num = FROM;
        std::function<long(long, long)> direction;
        std::vector<long> const divisors{ 3,5 }; // no need to make these configurable at the moment

Iterators should be lightweight, and in particular should be O(1) copyable. Neither std::function nor std::vector are lightweight, and std::vector in particular has O(n) copy.

It’s good to make your stuff flexible, but there is such a thing as too flexible. There is no reason for the divisors to be run-time configurable, is there?

Even if there were, it seems silly to truck around a copy of all the divisors with every iterator. Wouldn’t it make more sense to have a single copy in the view class, and iterators just have a reference to it? (That would mean the view would have to outlive the iterators… but, I mean, that’s true for every other view or container, so it’s not really a big deal.)

I would also throw out the direction member altogether. Again, there is such a thing as too much flexibility. Your type has literally two directions, and the direction is decided internally; it’s not user-configurable (a user can’t decide to use std::multiplies instead of std::plus, for example). There is no need to hold a std::function to some arbitrary increment function.

Finally, using the member initializer = FROM seems like a good idea, but it is thwarted by the constructor. I’ll get back to that.

So I would say your member variables just need to be:

        long num = FROM;
        bool direction = true;
        std::vector<long> const* p_divisors = nullptr;  // or you can have a
                                                        // default static
                                                        // vector of divisors
                                                        // to initialize to
                                                        // (but you don't need
                                                        // one, because a
                                                        // default-constructed
                                                        // iterator should
                                                        // never be
                                                        // incremented)

That will make your iterators much cheaper to move and copy.

So now let’s get back to the constructors:

        explicit iterator(long _num = 0) : num(_num) {
            // I really don't like the cast in here
            direction = isForward()
                ? static_cast<std::function<long(long, long)>>(std::plus())
                : std::minus();

            ++(*this); // start with the first valid number
        }

I am really not a fan of default arguments, and in this case your use of them has made you shoot yourself in the foot. Because of the member initializer, you want num to default initialize to FROM, which makes sense. But because you have done long _num = 0 in the argument list here, you’ve outsmarted yourself.

The solution is simple: don’t use default arguments. You want two constructors, one that takes no arguments, and one that takes an initializer. That’s two constructors.

    constexpr iterator() noexcept = default;

    constexpr iterator(long _num)
        : num(num)
        , direction(isForward())
        , p_divisors(/* ??? */)
    {
        // ???
    }

But there’s a snag. What to put in the initializer for the divisors? Well, clearly, you need another argument. So:

// In the view
template <std::integral T>
class MultiplesOf3Or5View
{
    T _start;
    T _finish;
    std::vector<T> _divisors;

public:
    constexpr MultiplesOf3Or5View(T start, T finish)
        : _start{std::move(start)}
        , _finish{std::move(finish)}
        , _divisors{T(3), T(5)}
    {}

    constexpr auto begin() const { return iterator{_start, _start <= _finish, _divisors}; }
    constexpr auto end() const { /* ... */ }
};

// In the iterator
class iterator
{
    T _num = {};
    bool _direction = true;
    std::vector<T> const* _p_divisors = nullptr;

public:
    constexpr iterator() = default;

    constexpr iterator(T n, bool direction, std::vector<T> const& divisors)
        : _num{n}
        , _direction{direction}
        , _p_divisors{&divisors}
    {}
};

There’s one more issue with the constructor. Let me bring it back:

        explicit iterator(long _num = 0) : num(_num) {
            // I really don't like the cast in here
            direction = isForward()
                ? static_cast<std::function<long(long, long)>>(std::plus())
                : std::minus();

            ++(*this); // start with the first valid number
        }

You have a bug.

It’s that last line. You are not wrong to want to make sure the iterator starts on a valid number. Let’s assume the divisors are 3 and 5 (the standard FizzBuzz numbers). If you start with FROM as 1… well, you want to immediately advance to 3. That makes sense.

But… what if you start with FROM as 3? It’s already valid. Yet… you immediately increment it.

What would you expect from the following:

auto view = MultiplesOf3Or5Iterator<1, 10>{};

for (auto p = view.begin(); p != view.end(); ++p)
    std::cout << *p << ' ';

Personally, I would expect:

3 5 9 

Now what would you expect from:

auto view = MultiplesOf3Or5Iterator<3, 10>{};

for (auto p = view.begin(); p != view.end(); ++p)
    std::cout << *p << ' ';

Personally, I would expect the same as above, not:

5 9 

On to the incrementer:

        iterator& operator++() {

            do {
                num = direction(num, 1);
            } while (!isDivisable());
            return *this;
        }

As I mentioned above, requiring a completely arbitrary direction function is a bit much. You’re going to go forward and backward. What else is there? Up and down? Ana and kata? So all you need is just _direction ? ++_num : --_num;.

        bool operator==(iterator other) const { return num == other.num; }
        bool operator!=(iterator other) const { return !(*this == other); }

As of C++20, you don’t need the second function. It will be auto-synthesized.

        bool isDivisable() const {
            // While this is a "modern" style foreach loop, I don't really like this part. 
            // I think there should be a more expressive style
            for (long divisor : divisors)
            {
                if (num % divisor == 0)
                {
                    return true;
                }
            }
            return false;
        }

You are quite right that this loop is not exactly great. You should generally avoid for loops altogether in modern C++.

In this case, what you want is probably std::ranges::any_of(). So:

    constexpr bool isDivisable() const
    {
        return std::ranges::any_of(
            *_divisors,
            [_num](auto& n) { return _num % n; }
        );
    }

Or, in English: return true if any of the divisors are evenly divisible into _num.

Suggested future directions

As I said, what you have now is already very good, modern-looking C++. You could pretty much leave what you have as-is, and it would be perfectly usable in modern code.

But there are ways you could make your code even more powerful, even more flexible, and even more integrated with modern C++ paradigms.

I would suggest starting from a high-level API view, and asking how users might want to construct FizzBuzz views. In my opinion (and, from here on out, it’s all opinion), there are basically 4 ways:

  1. A simple range: fizzbuzz_view{1, 20}, generates 3, 5, 9, 10, 12, 15, 18.
  2. A simple range, with adjustible divisors: fizzbuzz_view{1, 20, {3, 8}}, generates 3, 8, 9, 12, 15, 16, 18.
  3. An open range: fizzbuzz_view{7}, generates 9, 10, 12, 15, 18, 20, 21, … (on to infinity).
  4. An open range, with adjustible divisors: fizzbuzz_view{7, {3, 8}}, generates 8, 9, 12, 15, 16, 18, 20, 21, … (on to infinity).

The open ranges should use std::unreachable_sentinel as the end iterator. (See std::ranges::iota_view for inspiration.)

I would also suggest using compile-time argument deduction to determine the type of the number, with the ability to override. So:

Usage Number type
fizzbuzz_view{1, 10} int
fizzbuzz_view{1uL, 10uL} unsigned long
fizzbuzz_view<long>{1, 10} long
fizzbuzz_view{1} int
fizzbuzz_view{1uL} unsigned long
fizzbuzz_view<long>{1} long
fizzbuzz_view{1, 10L} <compile-time error>
fizzbuzz_view<long>{1, 10L} long

I would also suggest exploring some gotchas and corner cases:

  • What happens if the starting value is valid? (Your code currently skips past it.)
  • What happens if the starting value is not valid? (Should you accept what the user has given you as the first value, or skip past it immediately to the first valid value?)
  • What happens if the stopping value is valid? (Should it be counted? Or not?)
  • What happens if there are no more valid values (before overflow)?
  • If you do prevent overflow for signed types (which would make sense; signed overflow is UB), should you also prevent it for unsigned types (unsigned overflow is not UB, it wraps, and some algorithms count on that)?

Finally, just for the sake of completeness, I should point out that what you’re doing is already supported by the standard components:

auto main() -> int
{
    auto const is_fizzbuzz_number = [](auto n) { return ((n % 3) == 0) or ((n % 5) == 0); };

    auto view = std::ranges::views::iota(1L, 999L) | std::ranges::views::filter(is_fizzbuzz_number);

    std::cout << std::accumulate(view.begin(), view.end(), 0L) << '\n';
}

Because std::accumulate() still requires iterators, we can’t write the above as a single line… but if/when it ever accepts ranges, then the whole body of main() above could be a one-liner.

\$\endgroup\$
9
  • \$\begingroup\$ A very nice and detailed review. I see two issues though: why std::move() std::integrals in the constructor? They are not even passed in by r-value reference. Second, why have the iterator store a pointer to the divisors instead of a reference? The latter would seem like a much more obvious choice. \$\endgroup\$
    – G. Sliepen
    Aug 13, 2022 at 20:54
  • 1
    \$\begingroup\$ Perfect review. Thank you a lot. Up to now I've only started looking into C++ up to C++17. But I see that C++20 makes another big step and I really have to look into that as well if I want to write better code. \$\endgroup\$ Aug 14, 2022 at 8:01
  • 4
    \$\begingroup\$ Also thanks for the nice mixture of praise and criticism. I imagine that it's nice to have you in the team and do code reviews with you. If I don't put a bounty onto the question, you may remind me of doing so. \$\endgroup\$ Aug 14, 2022 at 8:11
  • 1
    \$\begingroup\$ @G.Sliepen The moves are standard issue; whenever taking a “sink” argument, by default you should take it by value and move it to its final location. (You can later optimize with dual const & and && versions, if you want.) Probably pointless for an integer type where there’s no difference between move and copy, but does no harm (and I like to illustrate best practices by default, even when shortcuts work). As for using reference members, that’s just bad practice. \$\endgroup\$
    – indi
    Aug 14, 2022 at 21:24
  • 1
    \$\begingroup\$ Yup, those are just typos. You’re correct about the reference line, and the value_type line should be std::add_const_t<T> (note the _t). (Or you could do typename std::add_const<T>::type, but… might as well just use the _t.) I’ll fix the code in the answer. \$\endgroup\$
    – indi
    Sep 16, 2022 at 19:51
7
\$\begingroup\$

Use static constexpr std::array

Your vector divisors will never change its length or its contents. Furthermore, there only ever needs to be one instance of divisors. So prefer making this a static constexpr std::array:

static constexpr std::array<long, 2> divisors{3, 5};

Naming things

The outer class is named SomethingIterator, but then it has an inner class named iterator as well. This is confusing. It's nicer to drop Iterator from the outer class name, so you can write:

for (auto number: MultiplesOf3Or5<1, 999>{}) {
    ...
}

Use of templates

There is no need to make class MultiplesOf3Or5Iterator a template. It prevents you from using runtime values for FROM and TO, and there is no performance benefit.

If anything, I would make the divisors template parameters, as that will give the compiler some opportunities to avoid expensive divisions:

template<long... Divisors>
class MultiplesOf {
    static constexpr std::array divisors{Divisors...};
    const long from;
    const long to;
public:
    ...
    MultiplesOf(long from = 0, long to = LONG_MAX): from(from), to(to) {}
    iterator begin() { return iterator(from); }
    iterator end() { return iterator(to); }
};

And then you can write:

using FizzBuzzNumbers = MultiplesOf<3, 5>;

for (auto number: FizzBuzzNumbers(1, 999)) {
    ...
}

Performance

Your strategy to loop until you find a number that is divisable by one of the divisors is simple and straightforward, but not the most efficient. Consider that if you look at how much the number is incremented each time operator++() is called, there is a pattern. You could precalculate this pattern and store it into an array (maybe even compile-time), and in iterator you can then store an index into that array. Then operator++() becomes:

static constexpr std::array<long, 7> increments = {3, 2, 1, 3, 1, 2, 3};
int inc_idx;
...
iterator& operator++() {
    num += increments[inc_idx++];
    if (inc_idx == increments.size())
        inc_idx = 0;
    return *this;
}

The optimal strategy probably depends on the exact number and size of the divisors.

The above code only handles the number moving in the positive direction. Instead of handling both directions by having a std::function<> object increment or decrement as necessary, I would instead create a reverse_iterator to avoid the potentially costly indirection.

\$\endgroup\$
2
\$\begingroup\$

Too explicit/imperative loop

The imperative implementation of the loop in isDivisable() can be replaced by std::any_of, basically making it a one-liner (formatted for readability).

bool isDivisable() const {
    return std::any_of(divisors.begin(), divisors.end(), 
        [&](int divisor) { return num % divisor == 0; }
    );
}

This will not make performance worse, since std::any_of will also stop at the first occurrence, just like the original implementation and not go through the whole vector unless needed.

Ugly cast

By initializing direction = std::plus() as the default, you can get rid of the ternary operator and replace it by a conventional if statement that does not need the cast:

if (!isForward()) direction = std::minus();
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Is it really better to separate the plus from the minus? One in an in-class initializer, one in the constructor? I guess if you put the member declaration right next to the constructor that makes it easy to see what's being overridden. \$\endgroup\$ Aug 14, 2022 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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