Sieve prime generator C++

Question

I had some issues with the behavior of the iterator in my prime generator:

#include <vector>
#include <set>
#include <iostream>
using namespace std;
int main() {
 int a,b;
 int nbr;
 vector<int> t;
 set<int> s;
 // prime generated to b
 b = 10;
 // set 2 -> b.
 for (int i = 2; i != b; i++)
 {
 s.insert(i);
 }
 int i = 0;
 while (s.size() != 0)
 {
 i++;
 cout << "Iteration = " << i << endl;
 t.push_back(*s.begin());
 for (set<int>::iterator it = s.begin() ; it != s.end(); it++)
 {
 cout << " s = " << *it << endl;
 if (*it % t.back() == 0) {s.erase(it++);}
 if (it == s.end()) break;
 }
 }
 cout << "++++++++++++++++++++++++++++" << endl;
 cout << "affichage des nombres premiers stockés dans le vecteur t" << endl;
 cout << "taille t = " << t.size() << endl;
 for (vector<int>::iterator it = t.begin() ; it != t.end(); ++it)
 {
 cout << "t = " << *it << endl;
 }

I think erasing an element of s in the for loop can be a problem, but the compiler doesn't complain and it seems to work. Is it a problem? I am also happy for a general review.

Answer 1

Here are some things that may help you improve your code.

Eliminate unused variables

Unused variables are a sign of poor quality code, and you don't want to write poor quality code. In this code, a and nbr are unused. Your compiler is smart enough to tell you about this if you ask it nicely.

Avoid single-line if constructs

The compiler can handle it just fine, but readers of your code are more likely to be able to correctly interpret the code if you avoid single-line if. So instead of

if (*it % t.back() == 0) {s.erase(it++);}

use this

if (*it % t.back() == 0) {
 s.erase(it++);
}

Be careful when you erase an iterator

The standard, in section 23.2.4 says that for an associative container, when you use erase(it) where it is an iterator:

erases the element pointed to by q. Returns an iterator pointing to the element immediately following q prior to the element being erased. If no such element exists, returns a.end().

This means that to be safe, your loop should look like this instead:

for (auto it = s.begin() ; it != s.end(); )
{
 cout << " s = " << *it << '\n';
 if (*it % t.back() == 0) 
 it = s.erase(it);
 else 
 ++it;
}

As pointed out by @LokiAstari, this works just fine for associative containers such as std::set but a more generic approach would be to use this for the line containing erase:

 s.erase(it++);

This works with set but also with other non-associative standard containers, including vector.

Think carefully about signed and unsigned

The code currently uses int types for both the vector and the set but are you looking for negative prime numbers? If not, it could be that unsigned would be a better choice for data type.

Reconsider container choices

A std::set is a sorted associative container. Since it's usually implemented internally as a tree, it's a relatively computationally expensive container to use consider the fact that all you really need is a list.

Consider using range-for syntax

The code currently prints the resulting vector with this code:

for (vector<int>::iterator it = t.begin() ; it != t.end(); ++it)
{
 cout << "t = " << *it << endl;
}

It can be written much more simply with a range-for:

for (const auto i : t) {
 cout << "t = " << i << '\n';
}

Don't use std::endl if '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

• Loki Astari: Your usage of erase is fine. But not all containers return the next element. A more generic approach can be seen here: stackoverflow.com/a/263958/14065
• Edward: @LokiAstari: good point. The quotation from the standard only applies to associative containers such as set but not to others such as vector.
• Edward: @LokiAstari: updated my answer to include that alternative. Thanks.