Representing destinations in a square

Question

I've written a program following the instructions of an exam paper. There are no solutions available so I would appreciate a feedback. I'm concerned with main in particular (I've already posted a similar question here). I've tried to solve the problem as I've seen it's done in other solutions made available by our teacher. Also the constructors made me think a lot.

I was asked to make a program to represent destinations in a square [0,1]x[0,1], a salesman that has to go in some destinations in that square and another salesman inheriting from the former but with slightly different habits.

#include <iostream>
#include <vector>
#include <set>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>

class Location {
private:
    double x_, y_;
public:
    Location(double x, double y) : x_(x), y_(y) { }
    Location() {
        x_ = drand48();
        y_ = drand48();
    }
    Location(const Location & L) : x_(L.x_), y_(L.y_) { }
    double getx() {return x_; }
    bool operator<(const Location & L) { return x_ < L.x_; }

    double distance(const Location & L) {
        return std::sqrt(std::pow(x_ - L.x_, 2) + std::pow(y_ - L.y_, 2));
    }

};

class Salesman {
private:
    Location start_;
protected:
    std::vector<Location> tobevisited_;
public:
    Salesman(const Location & start, std::vector<Location>::iterator it1, std::vector<Location>::iterator it2) : start_(start), tobevisited_(it1, it2) { }

    int ndest() { return tobevisited_.size(); }

    virtual double visit() {
        double dist = 0;
        sort(tobevisited_.begin(), tobevisited_.end());
        dist = (*(tobevisited_.begin())).distance(start_);
        for(std::vector<Location>::iterator it = tobevisited_.begin()+1; it != tobevisited_.end(); it++) {
            dist += (*(it)).distance(*(it-1));
        }
        return dist;
    }


};

class LazySalesman : public Salesman {
private:
    double d_;
public:
    LazySalesman(double d, std::vector<Location>::iterator it1, std::vector<Location>::iterator it2) : d_(d), Salesman(Location(0,0), it1, it2) { }

    double visit() {
        double dist = 0;
        dist = Salesman::visit();
        dist += d_*ndest();
    }
};

int main() {

    srand48(time(NULL));
    Location start(0., 0.);
    Location start2(1,1);
    int cont = 0;

    for(int i=0; i<3000; i++) {
        std::vector<Location> v;

        for(int j=0; j<10; j++) {
            v.push_back(Location());
        }
        Salesman Willy(start, v.begin(), v.end());
        if(Willy.visit() < 2.) cont++;
    }

    std::cout << "cont = " << cont << std::endl;

    std::vector<Location> loc;
    Location a(0.1, 0.1);
    Location b(0.5, 0.1);
    Location c(0.5, 0.5);
    loc.push_back(a);
    loc.push_back(b);
    loc.push_back(c);

    std::vector<Salesman*> vett;

    vett.push_back(new Salesman(start2, loc.begin(), loc.end()));
    vett.push_back(new LazySalesman(0.1, loc.begin(), loc.end()));
    vett.push_back(new LazySalesman(0.5, loc.begin(), loc.end()));

    for(auto el : vett) {
        std::cout << el->visit() << std::endl;
        delete el;
    }           

}

JDługosz · Accepted Answer · 2018-05-01 20:19:21Z

Tell your instructor to become familiar with the Standard Guidelines. You can find presentations on youtube where Stroustrup introduces this as a keynote speech, and many others speaking on them since.

Don’t use naked new (and delete). Make your vector of unique_ptr instead.

The srand48 is not a standard function. And the old C rand/srand are infamous for poor quality random numbers. See the <random> header file.

Why does one location use 0. (funny way to write 0.0, a double) and the other use 1 as an int?

You don’t need to put private: at the top of the class; that is assumed.

Does visit modify the object? You did not make it const. Also, use the override keyword in the derived version! That is very important in real code for maintainability as well as error checking.

for(int j=0; j<10; j++)  v.push_back(Location());

Did you know that vector elements are always initialized? And what will it use do you suppose? The default constructor of the element, of course!

So just write: v.resize(10+v.size()) to add 10 default locations to the end.

Location a(0.1, 0.1);

Use uniform initialization syntax.

Location a{0.1, 0.1};

Thou hast scribed an olde dialect. You’re using the ranged for loop so your textbook must be written after 2011; perhaps it is just a slightly updated lesson plan from 1998?

Location() {
    x_ = drand48();
    y_ = drand48();
}

A random-initialized location might be handy for this specific program, but it’s sufficiently bizzare that it hinders the understanding of the code. Make a function to return a random location instead!

double getx() {return x_; }
bool operator<(const Location & L) { return x_ < L.x_; }

You are definitly missing const on your member functions.

Writing good relational operators is a whole lesson and not the point here — this is probably fine for the class as it stands, but reviewers will wonder why you didn’t make it a non-member and supply all the relational and equality operators.

Since the (partial) ordering exists specifically for your algorithm, you might want to make it a named function instead. Consider the future maintainer that writes a test using > and then has to figure out why it didn’t compile, and of course documenting that less means East and is not a complete ordering.

double distance(const Location & L) {
    return std::sqrt(std::pow(x_ - L.x_, 2) + std::pow(y_ - L.y_, 2));

Besides being const, just call std::hypot. It will be faster and more accurate.

Salesman(const Location & start, std::vector<Location>::iterator it1, std::vector<Location>::iterator it2) 
: start_(start), tobevisited_(it1, it2) 
{ }

Very interesting that you allow salesman to be initialized with a segment of a larger vector. Is that a use case you anticipate (e.g. a huge list divided up among several salesmen)?

It’s enlightened but only part way to what we expect: it is limited to segments of another vector, and can’t take begin/end iterators to locations in general (anything that can be iterated).

Also, you should be using the const_iterator.

Here is the simple/direct way to take that information in the constructor.

      ⋮
    Location start_;
    std::vector<Location> tobevisited_;
public:
    Salesman (start, std::vector<Location> locations) 
      : start_{start}, tobevisited_{std::move(locations)} 
      { }

Get a post-it note and write using a fat marker, “Can it be const?”. Stick that on the edge of your monitor.

thank you for your insights, I hadn't thought about the uselessness of the nested for! I'll try to renew my dialect. I gave to the constructor of salesman iterators of a vector because it seemed to me the easiest way to define his protected member — agneau
– agneau, Commented May 1, 2018 at 13:55
Just pass the vector as a single parameter. (In fact, this will be a “sink” parameter so pass by value and move in the initialization list.) Salesman Willy{start, v}; — JDługosz
– JDługosz, Commented May 1, 2018 at 18:35

Stack Exchange Network

Representing destinations in a square

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Representing destinations in a square

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions