7
\$\begingroup\$

In order to learn C++ I have written a solution to this Kattis "Hitting the Targets" problem

Basically the program is to accept some shapes (circles and rectangles) on std in and a set of points and output the number of shapes that include each point.

Seeing as it is my first C++ program I'm sure I have made significant mistakes.

#include <iostream>
#include <regex>
#include <string>
#include <vector>
class Shape
{
public:
    Shape()
    {
    }
    ~Shape()
    {
    }
    virtual bool contains(int, int) = 0;
};

class Circle : public Shape
{
private:
    int x1, y1, r;

public:
    Circle(const int _x1,const int _y1,const int _r)
    {
        x1 = _x1;
        y1 = _y1;
        r = _r;
    }
    bool contains(const int x,const int y) override
    {
        int x_dist = std::abs(x - x1);
        int y_dist = std::abs(y - y1);
        return x_dist * x_dist + y_dist * y_dist <= r * r;
    }
    ~Circle()
    {
    }
};

class Rectangle : public Shape
{
private:
    int x1, x2, y1, y2;

public:
    Rectangle(const int _x1,const int _y1,const int _x2,const int _y2)
    {
        x1 = _x1;
        x2 = _x2;
        y1 = _y1;
        y2 = _y2;
    }
    bool contains(const int x,const int y) override
    {
        return x >= x1 && x <= x2 && y >= y1 && y <= y2;
    }
    ~Rectangle()
    {
    }
};

int main(void)
{
    std::string line;
    std::getline(std::cin, line);
    int num_shapes = std::stoi(line);
    std::vector<std::unique_ptr<Shape> > shapes;
    std::regex rect_pat{ R"(rectangle (-?\d+) (-?\d+) (-?\d+) (-?\d+))" };
    std::regex circ_pat{ R"(circle (-?\d+) (-?\d+) (-?\d+))" };
    for(int a = 0; a < num_shapes; a++) {
        std::getline(std::cin, line);
        std::smatch matches;
        if(std::regex_search(line, matches, rect_pat)) {
            std::unique_ptr<Shape> rect(new Rectangle(std::stoi(matches[1]), std::stoi(matches[2]), std::stoi(matches[3]), std::stoi(matches[4])));
            shapes.push_back(std::move(rect));

        } else if(std::regex_search(line, matches, circ_pat)) {

            std::unique_ptr<Shape> circ(
                new Circle(std::stoi(matches[1]), std::stoi(matches[2]), std::stoi(matches[3])));
            shapes.push_back(std::move(circ));
        }
    }
    std::getline(std::cin, line);

    int num_points = std::stoi(line);
    for(int a = 0; a < num_points; a++) {
        int x, y;
        std::cin >> x >> y;
        int num_containing = 0;

        for(std::vector<int>::size_type i = 0; i != shapes.size(); i++) {
            if((shapes[i]->contains)(x, y)) {
                num_containing++;
            }
        }
        std::cout << num_containing << '\n';
    }
    return 0;
}

I would have preferred to use count_if with a lambda rather than a for loop to count the number of shapes containing the point in order to improve readability but couldn't get it to work.

I'm also quite unsure if my use of unique_ptr and how I parse input is really optimal.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! I made an edit to the title, it's best to describe what the program does or solves in the title. I hope you get some good answers! \$\endgroup\$ – Phrancis Aug 3 '16 at 0:43
6
\$\begingroup\$

Virtual destructor

As a simple rule of thumb, if a base class contains any virtual functions, its destructor should also be virtual. The primary reason for it to declare a virtual function is so a derived class can override that virtual function. If you have public derivation, you nearly always want the destructor to be virtual--without that, destroying a derived object via a pointer to the base class gives undefined behavior.

Defining empty functions

As another simple rule of thumb, if you don't have a specific idea of what a function is supposed to do, it's probably better not to define it at all. In your case, the base class' constructor isn't doing anything, so it probably isn't needed at all. The destructor isn't currently doing anything either, but it should be defined as virtual (see previous point).

If the derived classes don't have anything to do in their destructors, you probably don't need to define their destructors.

Factory

You might want to consider moving all the code for reading data from the file and creating an object from that data into a class (or possibly just a function) by itself. This sort of thing is usually called a factory.

Error handling

Right now, if you encounter bad input (neither the "Circle" nor "Rectangle" pattern is matched by a line of input) you simply ignore that line of input and proceed to the next. This is fine for a site like you're dealing with here, but it's rarely good behavior in the real world, where bad input should normally produce some message to the user letting them know what happened.

Standard algorithm

You mentioned using std::count_if to do the counting. You could use it something like this:

std::cout << std::count_if(shapes.begin(), shapes.end(),
        [=](std::unique_ptr<Shape> &s) { return s->contains(x, y); }) << "\n";

Note that in this case, the unique_ptr doesn't really work particularly well, so we end up passing it by reference. Otherwise, the pointer would be moved (transferred) to the algorithm, so the pointer in the vector would have released it; on the second iteration, the vector would only contain null pointers.

This could be handled by using shared_ptrs instead. Another (probably preferable) solution would be to look up (and use) Boost ptr_vector instead.

Adding a Point class

It's probably at least worth considering adding a Point class (or maybe struct) to encapsulate an X/Y coordinate pair.

Prefer member initializer lists over assignment

When you have a constructor that initializes members from arguments, it's usually preferable to do the initialization in a member initializer list. For example, your Circle constructor could look like this:

Circle(const int _x1, const int _y1, const int _r) : x1(_x1), y1(_y1), r(_r) {
}

Note that a ctor with an empty body like this is quite common and expected.

Prefer make_unique over unique_ptr<T>(new T(arguments))

There's rarely much (if any) reason to use an unadorned new to allocate your object(s), and doing so can introduce exception safety issues (which don't arise in this exact code, but I'd advise normally using make_unique as it eliminates the possibility).

Putting most of those together, we could end up with code something like this:

#include <iostream>
#include <memory>
#include <regex>
#include <string>
#include <vector>

class Shape {
public:
    virtual ~Shape() { }
    virtual bool contains(int, int) = 0;
};

class Circle : public Shape {
    int x1, y1, r;
public:
    Circle(const int _x1, const int _y1, const int _r) 
        : x1(_x1), y1(_y1), r(_r) 
    { }

    bool contains(const int x, const int y) override {
        int x_dist = std::abs(x - x1);
        int y_dist = std::abs(y - y1);
        return x_dist * x_dist + y_dist * y_dist <= r * r;
    }
};

class Rectangle : public Shape {
    int x1, x2, y1, y2;
public:
    Rectangle(const int _x1, const int _y1, const int _x2, const int _y2) 
        : x1(_x1), y1(_y1), x2(_x2), y2(_y2) 
    { }

    bool contains(const int x, const int y) override {
        return x >= x1 && x <= x2 && y >= y1 && y <= y2;
    }
};

struct Factory {
    std::unique_ptr<Shape> build(std::string const &line) {
        static const std::regex rect_pat{ R"(rectangle (-?\d+) (-?\d+) (-?\d+) (-?\d+))" };
        static const std::regex circ_pat{ R"(circle (-?\d+) (-?\d+) (-?\d+))" };

        std::smatch matches;
        if (std::regex_search(line, matches, rect_pat)) {
            return std::make_unique<Rectangle>(std::stoi(matches[1]), std::stoi(matches[2]), std::stoi(matches[3]), std::stoi(matches[4]));
        }
        else if (std::regex_search(line, matches, circ_pat)) {
            return std::make_unique<Circle>(std::stoi(matches[1]), std::stoi(matches[2]), std::stoi(matches[3]));
        }
        // Probably want to add something here to deal with bad data (e.g., throw an exception).
    }

};

int main(void)
{
    std::string line;
    std::getline(std::cin, line);
    int num_shapes = std::stoi(line);
    std::vector<std::unique_ptr<Shape> > shapes;

    Factory f;

    for (int a = 0; a < num_shapes; a++) {
        std::getline(std::cin, line);
        shapes.push_back(f.build(line));
    }
    std::getline(std::cin, line);

    int num_points = std::stoi(line);
    for (int a = 0; a < num_points; a++) {
        int x, y;
        std::cin >> x >> y;

        std::cout << std::count_if(shapes.begin(), shapes.end(),
            [=](std::unique_ptr<Shape> &s) { return s->contains(x, y); }) << "\n";
    }
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback, make_unique in unfortunately unavailable (c++ 11) it seems How come it is safe not to have destructors? I thought they were needed to clean up the allocated variables Is there a reason using [=] in the lambda is preferable to using [x,y]? \$\endgroup\$ – Bomaz Aug 3 '16 at 9:40
  • \$\begingroup\$ @Bomaz: You can use make_unique anyway--you just have to include your own implementation of it (it's pretty trivial--around three lines of code). Cleaning up locals happens automatically, whether you define a dtor or not. I prefer [=] because I'm lazy, but the effect is the same as [x, y] (in this case). \$\endgroup\$ – Jerry Coffin Aug 3 '16 at 12:36

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.