Implement Fibonacci range

Question

I am implementing a Fibonacci range in C++17 such that it supports

#include "fib.h"

#include <iostream>

int main() {

  for (int x : Fibonacci()) {
    std::cout << x << std::endl;

    if (x > 100000) {
      break;
    }
  }

  for (int x : Fibonacci(5)) {
    std::cout << x << std::endl;
  }

  for (int x : Fibonacci(3, 10)) {
    std::cout << x << std::endl;
  }

  return 0;
}

Here is how I defined the header

#ifndef FIB_H
#define FIB_H

#include <cstddef>
#include <iterator>

class Fibonacci {
 public:
  class iterator {
   public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = int;
    using difference_type = int;
    using pointer = int*;
    using reference = int&;

   public:
    iterator() = default;

    iterator(int i, int a, int b);

    int operator*() const;

    iterator& operator++();

    bool operator!=(iterator const& other) const;
   private:
    int i_ {0};
    int a_ {0};
    int b_ {1};
  };

 public:
  Fibonacci();

  Fibonacci(int end);

  Fibonacci(int begin, int end);

  iterator begin() const;

  iterator end() const;

 private:
  iterator beginIt_;

  iterator endIt_;
};

#endif

And the source code

#include "fib.h"

#include <iterator>

Fibonacci::iterator::iterator(int i, int a, int b)
    : i_(i), a_(a), b_(b) {}

int Fibonacci::iterator::operator*() const {
  return b_;
}

Fibonacci::iterator& Fibonacci::iterator::operator++() {
  ++i_;
  b_ = b_ + a_;
  a_ = b_ - a_;
  return *this;
}

bool Fibonacci::iterator::operator!=(Fibonacci::iterator const& other) const {
  return i_ != other.i_;
}

Fibonacci::Fibonacci()
    : endIt_(-1, 0, 0) {}

Fibonacci::Fibonacci(int end)
    : endIt_(end, 0, 0) {}

Fibonacci::Fibonacci(int begin, int end)
    : beginIt_(std::next(Fibonacci::iterator(), begin)), endIt_(end, 0, 0) {}

Fibonacci::iterator Fibonacci::begin() const {
  return beginIt_;
}

Fibonacci::iterator Fibonacci::end() const {
  return endIt_;
}

I want to have a syntax similar to the standard library where the iterator of a class can be accessed using ::iterator, therefore I nested my iterator class into the main class itself. However, this makes the source code very verbose and results in very long function name. Is there a way to make this more readable? Furthermore, is there any new C++17 feature I should be aware of that can be applied here?

Answer 1

Overall, I think the code looks good. Here are a few sugestions that may help you improve your code.

Check for overflow

As you know, terms of the Fibonacci sequence get very big very quickly. For this reason, it's easy to overflow the numerical range. I'd suggest addressing this by throwing an exception in iterator& operator++():

if (b_ < a_) {
  throw std::overflow_error("Exceeded range of underlying type");
}

Use an unsigned type

None of the terms of the Fibonacci sequence are negative, so I'd suggest that perhaps unsigned or even unsigned long might be more appropriate base types.

Use a template

It may make sense to turn this into a templated function to allow different types to be used as the base type. This would be one way to extend the range, such as with the GNU Multiple Precision Arithmetic Library.

Consider a different operator++ implementation

The current implementation of the operator++ is this:

iterator& operator++() {
  ++i_;
  b_ = b_ + a_;
  a_ = b_ - a_;
  return *this;
}

I would suggest, especially if you decide to implement templates, that this might be more efficient:

iterator& operator++() {
  ++i_;
  std::swap(a_, b_);
  b_ += a_;
  if (b_ < a_) {
      throw std::overflow_error("Exceeded range of underlying type");
  }
  return *this;
}