8
\$\begingroup\$

I'm coming from a Python background(look at indentation :) ) and trying to learn basics of C++. I wrote a simple prime generator, I know there is better algorithms, but I want advices about coding style, inconsistencies, or better language use.

Here is my main.cpp:

#include <iostream> 
#include "PrimeGenerator.h"

using namespace std;

int main(){
    PrimeGenerator *generator;
    generator = new PrimeGenerator();

    for(int i=0;; i++){
        generator->addPrime();
        cout<<generator->getPrimes()->back()<<endl;
        }

    delete generator; #I know this is unnecessary at the end of program, but I think it is a better practice.

    return 0;
    }

And PrimeGenerator.h:

#pragma once
#include <list>
#include <iostream>

typedef std::list<unsigned long long int> PrimeList;

class PrimeGenerator{

    PrimeList *primes;

    public:

    PrimeGenerator();
    ~PrimeGenerator();

    PrimeList *getPrimes();
    void addPrime();
    };

PrimeGenerator::PrimeGenerator(){
    primes = new PrimeList;

    primes->push_back(2);
    primes->push_back(3);
    }

PrimeGenerator::~PrimeGenerator(){
    delete primes;
    }

void PrimeGenerator::addPrime(){

    unsigned long long int num = primes->back()+2;

    while(true){
        bool isPrime = true;

        for(auto it=primes->begin(); it!=primes->end(); ++it){

            if(*it > (num / 2)) 
                break;

            if((num % *it) == 0){
                isPrime = false;
                break;
                }
            }

        if(isPrime){
            primes->push_back(num);
            break;
            }

        num += 2;
        }
    }

PrimeList *PrimeGenerator::getPrimes(){
    return primes;
    }
\$\endgroup\$
6
\$\begingroup\$

Your indentation style is unusual for C++. There are a variety of styles used in C++, I recommend you take a look at them, http://en.wikipedia.org/wiki/Indent_style, pick one you like. As it is you are combing elements of several styles. We don't need more indentation styles, so use a standard one, don't invent your own.

#include <iostream> 
#include "PrimeGenerator.h"

using namespace std;

Many people use this, but I recommend against it. It looks doing a from std import * in python. I think its better to just use the prefix.

int main(){
    PrimeGenerator *generator;
    generator = new PrimeGenerator();

You can combine this into one line:

PrimeGenerator * generator = new PrimeGenerator();

You can also avoid using a pointer altogether and write:

PrimeGenerator generator;


    for(int i=0;; i++){

I think you are missing the middle element, as it is this is an infinite loop

        generator->addPrime();
        cout<<generator->getPrimes()->back()<<endl;

I'd add spaces around the <<

        }

    delete generator; #I know this is unnecessary at the end of program, but I think it is a better practice.

If you use the pointerless version I suggested, it will automatically be destroyed at the end of main.

    return 0;
    }

#pragma once

This may not work on all compilers, so be careful.

#include <list>
#include <iostream>

typedef std::list<unsigned long long int> PrimeList;

List is a linked list, unlike lists in python which are resizable arrays. Linked lists are almost always the wrong choice as a datastructure. Perhaps a vector would be better? Vectors act like python lists. unsigned long long int can be written as unsigned long long. You also repeat it often enough creating a typedef might be a good idea.

class PrimeGenerator{

    PrimeList *primes;

Don't make this a pointer. Just use the object directly.

    public:

    PrimeGenerator();
    ~PrimeGenerator();

    PrimeList *getPrimes();
    void addPrime();
    };

PrimeGenerator::PrimeGenerator(){
    primes = new PrimeList;

If you avoid make primes a pointer like I suggest, this is unneccesary.

    primes->push_back(2);
    primes->push_back(3);
    }

PrimeGenerator::~PrimeGenerator(){
    delete primes;
    }

If you avoid making primes a pointer like I suggest, this is unneccesary.

void PrimeGenerator::addPrime(){

    unsigned long long int num = primes->back()+2;

    while(true){
        bool isPrime = true;

        for(auto it=primes->begin(); it!=primes->end(); ++it){

            if(*it > (num / 2)) 
                break;

This limitation isn't obvious, a comment explaining would be good.

            if((num % *it) == 0){

Operator precedence rules were defined to make sense, use them.

                isPrime = false;
                break;
                }
            }

        if(isPrime){
            primes->push_back(num);
            break;
            }

        num += 2;
        }
    }

Your logic can be simplified:

bool isPrime = false;
unsigned long long int num = primes->back();
while(!isPrime)
{
    num += 2;

    for(auto it = primes->begin(); it != primes->end(); it++)
    {
        if(*it > num / 2)
        {
            break;
        }

        if( num % *it == 0 )
        {
            isPrime = false;
            break;
        }
    }
}
primes->push_back(num);

I try to avoid using break when possible. Basically, I try to restrict to cases where it is skipping the rest of the loop as an optimisation. If the breaks were removed, the code would be valid but slower.

PrimeList *PrimeGenerator::getPrimes(){
    return primes;
    }
\$\endgroup\$
4
  • \$\begingroup\$ Thank you. But, is there a way to skip the break's with that logic? And also, one more question, using "auto" is bad for my learning(backward compatiblity isn't a problem for me), or code? \$\endgroup\$ – Utku Demir Aug 20 '11 at 22:56
  • \$\begingroup\$ @utdemir, sorry, I didn't understand either of your questions. \$\endgroup\$ – Winston Ewert Aug 20 '11 at 22:59
  • 1
    \$\begingroup\$ You said "I try to avoid using break when possible.". How? And I used auto it = primes->begin() in code, should I explicitly define iterator's type? \$\endgroup\$ – Utku Demir Aug 20 '11 at 23:06
  • \$\begingroup\$ @utdemir, I showed how to eliminate one the breaks in your example. I think the other breaks are fine. That's a perfectly fine use of auto. The auto syntax was introduce partially to avoid having to write out types like that iterator. \$\endgroup\$ – Winston Ewert Aug 21 '11 at 1:39
6
\$\begingroup\$

You don't need to manage resources manually. You are declaring a pointer to the new PrimeGenerator instance and releasing it at the end of the main function, but what happens if one of the calls inbetween (for example, addPrime()) fails? You end up with a memory leak.

Instead of

PrimeGenerator *generator;
generator = new PrimeGenerator();
....
delete generator;

why don't you use

PrimeGenerator generator;
....

You don't need to use pointers in the PrimeGenerator class either.

class PrimeGenerator
{

        PrimeList primes;

    public:
        PrimeGenerator();

        const PrimeList& getPrimes() const {return primes;}
        void addPrime();     
};

std::ostream& operator<<(std::ostream& stream, PrimeList const& value)
{
    for (PrimeList::const_iterator it = value.begin(); it != value.end; it++)
    {        
    stream << *it << endl;
    }

    return stream;
}

PrimeGenerator::PrimeGenerator()
{
    primes.push_back(2);
    primes.push_back(3);
}

int main()
{
     PrimeGenerator generator;

    for(int i = 0; i < 100; i++)
    {
         generator.addPrime();
    }
    cout << generator.getPrimes();

    return 0;
}
\$\endgroup\$
2
  • \$\begingroup\$ Thank you. Am I understand right if I don't use pointers, will those objects destroyed at the end of their scope? If this is true, when should I use pointers, or new and delete? \$\endgroup\$ – Utku Demir Aug 20 '11 at 22:42
  • 2
    \$\begingroup\$ Yes, the objects you've constructed will be destroyed at the end of the function you've constructed them in. As for the pointers, you should avoid using them in C++ unless it is absolutely necessary for some reason. \$\endgroup\$ – Alexvn Aug 20 '11 at 22:56
2
\$\begingroup\$

It seems to me that prime number generation is really best represented as an algorithm. Rather than giving the client access to the class' internals I'd also prefer to send the results to an iterator. Finally, I'd prefer to producing a set of results over producing one result at a time.

As such, it seems like the interface should be something like:

template <class FwdIt>
void gen_primes(size_t num, FwdIt out);

If you wanted, for example, to generate the first 100 primes, you'd call it something like this:

std::vector<int> primes(100);

gen_primes(100, primes.begin());

Note that since it reuses the data in the output, it does require a forward iterator, not an output iterator, so you couldn't (for example) use std::back_inserter(primes).

Although I'd probably incorporate most of (for example) @Winston Ewert's suggestions, internally the code could remain at least reasonably close to what you already have.

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

I think the object-oriented design could be improved.

  • PrimeGenerator is a tool to generate a linked list. Once you return a pointer to it, who knows what the caller will do with its contents? The caller could alter the list in a way that breaks subsequent calls to .addPrime().
  • Primes are a notionally infinite list, so your class should try to create the illusion of an infinite list. Requiring the user to call .addPrime() is a chore that breaks that illusion.

It would be better if PrimeList were a self-managing read-only list of prime numbers, like this:

class PrimeList {
  public:
    PrimeList();

    // Returns the nth prime number
    // (primelist[0] is 2, primelist[1] is 3, etc.)
    unsigned long long operator[](size_t nth);

  private:
    std::vector<unsigned long long> knownPrimes;

    void findMorePrimes();
};

Then your implementation of operator[] could call findMorePrimes() as needed behind the scenes.

The notion of an infinite list also frees you from the expectation that you should only add one prime number at a time to the list. Then, you would have the flexibility to find batches of prime numbers at a time, with likely improvements in performance.

Answer self-plagiarized from here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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