Prime numbers iterator

I am not familiar with iterators. I am confused with the traits approach and the traditional one. I don't know which one I should use in 2021.

I wrote a minimal example that can iterate through prime numbers. My approach is naive, but the goal is to use an iterator that may skip values.

#include <vector>
#include <iostream>

bool isPrime(int num)
{
if (num <= 1) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) return false;
}
return true;
}

struct Collection : public std::vector<int>
{
class iterator : public std::iterator<std::input_iterator_tag, int>
{
int k;
std::vector<int> &collection;

public:
iterator(vector<int> &collection, int k) : collection(collection), k(k)
{
}
iterator &operator++()
{
if (k == -1) return *this;
k++;
while (k < collection.size()) {
if (isPrime(collection[k])) {
return *this;
}
k++;
}
k = -1;
return *this;
}
bool operator!=(const iterator &other) { return k != other.k; }
int operator*() { return collection[k]; }
};

iterator begin() { return iterator(*this, 0); }
iterator end() { return iterator(*this, -1); }
};

int main() {
Collection collection;

for (int i = 1; i <= 100; i++)
collection.push_back(i);

// Demonstrate the iteration over prime numbers.
for (auto i : collection) {
std::cout << i << std::endl;
}
}

• Hi, i have edited the title to fit CR standard. Feel free to change if not suitable. Further, I am no c++ expert, so let me just point out that this is very ineffective way to implement the iterator. You should instead do what isPrime is doing inside the iterator and then you might implement the global isPrime function using that iterator, rather then the other way around. Dec 5 '21 at 19:26

Writing a proper iterator

I am not familiar with iterators. I am confused with the traits approach and the traditional one. I don't know which one I should use in 2021.

You should not be using std::iterator in 2021 anymore, as it has been deprecated since C++17. Instead, you have to write the required member types explicitly (see this article):

class iterator
{
int k;
std::vector<int> &collection;
public:
using iterator_category = std::input_iterator_tag;
using value_type = int;
using difference_type = int;
using reference = int; // Because we don't return an actual reference
using pointer = void;  // We don't have operator->()
...
};


To try out whether your class is a valid input iterator, you can write something like:

Collection collection;
std::input_iterator auto it = collection.begin();


If the iterator doesn't satisfy the std::input_iterator concept, there will be a compile error. And indeed there are some. An iterator must be copyable, however the copy assignment operator has been deleted because the member variable collection is a reference. The quick way to solve this is to make it a pointer instead. Furthermore, ensure you have an implementation of the post-decrement operator, and you must make operator*() const.

Note that you don't need to do anything with std::iterator_traits yourself if you have the proper member functions and types.

What is the purpose of the vector collection?

If you just want an iterator that generates prime numbers, similar to how std::iota generates sequential numbers, then you don't need any vector of ints. Instead, just store the end value in a simple int variable.

If you want to improve the performance of your iterator, then using a sieve algorithm is probably the way to go, in which case you do need to keep track of which values are possible primes or not. In that case though, a vector of bools would be better.

You store a reference to the collection the iterator is operating on within the iterator, but that makes the iterator non-copyable and non-moveable, and it is not default constructable (to have an iterator that refers to nothing). Code like

Collection::iterator it;
it = col.begin();


won't compile. That reference also prevents you from easily checking that two iterators are tied to the same container (something you're not doing in your operator!=).

If you store a pointer to the vector (instead of a reference) then those problems go away. Your comparison operator can then check that the two iterators are operating on the same container (if they operate on different containers, they are not equal).