Start learning free

LESSON 559 OF 568 · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

Shapes Perimeter in C++: Polymorphism with Virtual Methods

Practice O(n) Read the full explanation

A drawing app keeps rectangles, squares and triangles in one list. Write the shape types so that code holding that list can ask any shape for its name and its perimeter (the length all the way around it) without knowing which kind of shape it is. That is polymorphism: one call, shape.perimeter(), and each kind of shape runs its own version.

Every shape class inherits from the class Shape, the common type. Shape has two methods:

  • name() returns the kind of shape as text: "Shape" for a plain Shape.
  • perimeter() returns the length around the shape: 0 for a plain Shape.

Each shape class overrides both:

  • Rectangle(width, height): its name is "Rectangle", its perimeter 2 × (width + height).
  • Square(side): its name is "Square", its perimeter 4 × side.
  • Triangle(a, b, c): its name is "Triangle", its perimeter a + b + c.

In C++ each shape class inherits with : public Shape. Shape's methods are virtual and the shape classes mark theirs override, so a call through a Shape* runs the object's own version. Each class keeps its sizes in int fields.

Then write two methods of the class Solution, as in the course's other lessons. Both get the shapes as vector<Shape*>&:

  • totalPerimeter(shapes) returns the sum of the perimeters of all the shapes.
  • largestShape(shapes) returns the name of the shape with the largest perimeter. If several shapes share the largest perimeter, the one that comes first wins.

Both functions must work through the common type's methods only: never check which kind a shape is. Then a new kind of shape, added later, works with them unchanged.

The starter code already has every class, constructor and method header: write their bodies. For each test, the harness reads the shapes, builds them in the order given, calls totalPerimeter and largestShape, and prints the two results on one line, separated by a space.

 

Example 1:

Input:
    new Rectangle(3, 4)
    new Square(5)
    new Triangle(3, 4, 5)
Output: 46 Square
Explanation: The perimeters are 2 × (3 + 4) = 14, 4 × 5 = 20 and 3 + 4 + 5 = 12. Their total is 46, and the square's 20 is the largest.

Example 2:

Input:
    new Rectangle(2, 4)
    new Square(3)
    new Triangle(4, 4, 4)
Output: 36 Rectangle
Explanation: All three perimeters are 12: 2 × (2 + 4), 4 × 3 and 4 + 4 + 4. On a tie the shape that comes first in the list wins, so the answer is the rectangle.

Example 3:

Input:
    new Square(1)
    new Rectangle(1, 1)
    new Triangle(2, 2, 3)
Output: 15 Triangle
Explanation: The perimeters are 4, 4 and 7, so the last shape, the triangle, is the largest. A 1 by 1 rectangle has the same sides as a square, but it is still a Rectangle: each object answers name() for its own class.

 

Constraints:

  • Every test has between 1 and 100 shapes: the list is never empty.
  • Every size (width, height, side, and each side of a triangle) is an integer from 1 to 104.
  • A triangle's three sides always make a real triangle: each side is shorter than the other two together.

Note:

Each function looks at every shape once: O(n) time for n shapes, and no extra space.

STEP 1 OF 24
    Ctrl + Enter to check

    C++ · OBJECT-ORIENTED PROGRAMMING - CHALLENGES

    Shapes Perimeter in C++, explained

    Problem overview

    A drawing app keeps different kinds of shapes in one list. You write the shape classes so that code holding that list can ask any shape for its name() and its perimeter() without knowing which kind it is.

    The classes are:

    • Shape, the common parent: name "Shape", perimeter 0;
    • Rectangle(width, height): perimeter 2 * (width + height);
    • Square(side): perimeter 4 * side;
    • Triangle(a, b, c): perimeter a + b + c.

    Then two methods of Solution work on a vector<Shape*>: totalPerimeter adds up all the perimeters, and largestShape returns the name of the shape with the largest perimeter, the first one if there is a tie.

    In the first example the shapes are a 3 by 4 rectangle, a square of side 5 and a triangle with sides 3, 4 and 5. Their perimeters are 14, 20 and 12, so the total is 46 and the square is the largest.

    Approach: ask the object, don't check its class

    The list holds Shape* pointers, whatever the real kind of each shape. Because name and perimeter are virtual in Shape, a call such as shape->perimeter() runs the version that belongs to the object the pointer points to. A Square adds nothing up, it multiplies by four. A Triangle adds three sides. The loop that calls perimeter() doesn't need to know.

    The statement asks for exactly this: both Solution methods use only the methods Shape has, and never test the kind of a shape. That keeps them working when someone adds a new shape later. For example, with a Hexagon class that inherits from Shape and overrides both methods, a list holding a 3 by 4 rectangle, a hexagon of side 4 and a square of side 5 gives 58 Hexagon, with neither method changed.

    Step by step

    1. Shape. Return "Shape" from name and 0 from perimeter. The children override both, so these defaults only give the common type its two methods. The virtual destructor is already in the starter code.
    2. The fields. Each shape keeps its sizes in int fields: width and height for the rectangle, side for the square, a, b and c for the triangle. The perimeter methods need them later, so every object remembers its own.
    3. The constructors. The parameters have the same names as the fields, so this->width = width; means "store the parameter in the field".
    4. The overrides. Each class returns its own name, with a capital letter, and the formula for its perimeter.
    5. totalPerimeter. Start a total at 0, loop over the shapes with a range-based for and add shape->perimeter() to it. Return the total after the loop.
    6. largestShape. Let largest start as the first shape, shapes[0], which always exists. Loop over all shapes. If one has a strictly greater perimeter than largest, it becomes the new largest. After the loop, return largest->name().

    The solution in C++

    class Shape {
public:
    virtual string name() {
        return "Shape";
    }

    virtual int perimeter() {
        return 0;
    }

    virtual ~Shape() = default;
};

class Rectangle : public Shape {
public:
    int width;
    int height;

    Rectangle(int width, int height) {
        this->width = width;
        this->height = height;
    }

    string name() override {
        return "Rectangle";
    }

    int perimeter() override {
        return 2 * (width + height);
    }
};

class Square : public Shape {
public:
    int side;

    Square(int side) {
        this->side = side;
    }

    string name() override {
        return "Square";
    }

    int perimeter() override {
        return 4 * side;
    }
};

class Triangle : public Shape {
public:
    int a;
    int b;
    int c;

    Triangle(int a, int b, int c) {
        this->a = a;
        this->b = b;
        this->c = c;
    }

    string name() override {
        return "Triangle";
    }

    int perimeter() override {
        return a + b + c;
    }
};

class Solution {
public:
    int totalPerimeter(vector<Shape*>& shapes) {
        int total = 0;
        for (Shape* shape : shapes) {
            total += shape->perimeter();
        }
        return total;
    }

    string largestShape(vector<Shape*>& shapes) {
        Shape* largest = shapes[0];
        for (Shape* shape : shapes) {
            if (shape->perimeter() > largest->perimeter()) {
                largest = shape;
            }
        }
        return largest->name();
    }
};

    A run

    Building the shapes of the three examples and calling both methods gives:

    46 Square
36 Rectangle
15 Triangle

    The second line is the tie case: a 2 by 4 rectangle, a square of side 3 and a triangle with sides 4, 4 and 4 all have perimeter 12, and the rectangle comes first. In the third, the last shape wins because its perimeter, 7, is larger than the 4 of the other two.

    Details that matter

    • Pointers use ->. A Shape* reaches its methods with ->, as in shape->perimeter(), not with a dot.
    • The names belong to the objects. A 1 by 1 rectangle has the same sides as a square, but it is still a Rectangle: it prints Rectangle, because the object answers for its own class.
    • A base pointer to a derived object. A Shape* can point to a Square, since a square is a shape. The reverse isn't true.
    • The virtual destructor in Shape lets delete on a Shape* clean up the real object correctly.

    Complexity

    Each method visits every shape once and does a constant amount of work for each, so the time is O(n) for n shapes. Only a few variables are added, so the extra space is O(1).

    Edge cases and common mistakes

    • Using >= in largestShape. The last of several equal shapes would win. With the tie example above, the answer would be Triangle instead of Rectangle. Only a strictly greater perimeter may replace largest.
    • Forgetting virtual on a method. If perimeter is not virtual in Shape, a call through a Shape* runs the parent's version. With that change, a square of side 5 reached through a Shape* reports a perimeter of 0.
    • Shadowing in the constructor. Writing width = width; without this-> assigns the parameter to itself and never sets the field, which keeps an indeterminate value. For Rectangle r(3, 4) the test r.width == 3 came out false.
    • Checking the kind of the shape with if chains. It works for today's shapes, but every new shape would need a new branch.
    • Using shapes[0] on an empty list. The tests never give an empty list, so the first shape is always there.

    Testing

    Three small lists to try. The first number is the total, then the name:

    ShapesResult
    Rectangle(3, 4), Square(5), Triangle(3, 4, 5)46 Square
    Rectangle(2, 4), Square(3), Triangle(4, 4, 4)36 Rectangle
    Square(1), Rectangle(1, 1), Triangle(2, 2, 3)15 Triangle
    Keep going with C++500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free