Solved exercise: polymorphic fleet with deep cloning in C++

Solved C++ exercise on inheritance and polymorphism: a vehicle fleet, an abstract base class, a trailer decorator and deep copy with clone and unique_ptr.

Exam Code C++ Object-oriented programming Top-grade level Tested code

Object-Oriented Programming in C++ · Final ExamQuestion 4 · 2.5 points · 40 min

The courier company Last Stop runs a mixed fleet. Write a C++20 program that maintains the fleet and answers cost queries. All amounts are integers in cents. All distances are integers in kilometres.

The design is mandatory. There must be an abstract class Vehicle with an identifier and a virtual destructor. It declares the pure virtual methods cost(km), range(), describe(...) and clone(); clone() returns std::unique_ptr<Vehicle>. It also has a virtual method tune(value) that returns false by default. The fleet is stored as std::vector<std::unique_ptr<Vehicle>>. Inspecting the dynamic type (dynamic_cast, typeid or a type field) is forbidden.

Vehicle types. Van (V id cpk rng): its cost is cpk·km and its range is rng. Electric van (E id cpk rng): its cost is cpk·km + 150, the fixed charging fee, and its range is rng. Both share the attribute cpk, and tune replaces it. Cargo bike (B id): its cost is 40·km, its range is 25 and it cannot be tuned.

Trailer (T id base extra): creates a new vehicle that contains a copy of vehicle base as it is at that moment. The base may itself be a trailer. Its cost is base_cost(km) + extra·km and its range is base_range·8/10 in integer division, computing the product first. For a trailer, tune replaces its extra. Later changes to the original vehicle do not affect the copy.

Input on standard input. The first line holds N (0 ≤ N ≤ 1000), the number of operations. N lines follow. Each is a registration (V, E, B, T) or one of these commands. C id value calls tune; if the vehicle cannot be tuned it prints NOT_TUNABLE id, otherwise nothing. Q km finds, among the vehicles with range ≥ km, the one with the lowest cost; ties go to the lexicographically smallest identifier. L lists the fleet.

Output. Q prints km: id cost, or km: NONE if no vehicle has enough range. L prints one line per vehicle, in registration order, as id description range=R, or EMPTY FLEET if there are none. The description is V(cpk), E(cpk) or B. A trailer's description is T(extra)+ followed by the description of its base.

Guarantees: identifiers are unique and have at most 20 alphanumeric characters. Vehicles named in T and C exist. Also 1 ≤ km ≤ 10000, 0 ≤ cpk, extra, value ≤ 1000, 1 ≤ rng ≤ 100000, and trailers are nested at most 50 deep.

Sample input

11
V F1 30 500
E E1 12 180
B BIKE
T R1 F1 10
Q 20
Q 200
C F1 25
L
Q 400
C BIKE 50
Q 600

Expected output

20: E1 390
200: F1 6000
F1 V(25) range=500
E1 E(12) range=180
BIKE B range=25
R1 T(10)+V(30) range=400
400: F1 10000
NOT_TUNABLE BIKE
600: NONE

Correct hierarchy: abstract class <code>Vehicle</code> with a virtual destructor, an intermediate class for per-kilometre rates, and <code>override</code> in every concrete type

0.75

<code>Trailer</code> as a decorator that owns a deep copy of its base vehicle obtained through <code>clone</code>, with a correct copy constructor and recursive description

1.0

Commands <code>Q</code>, <code>C</code> and <code>L</code> handled only through virtual calls (no <code>dynamic_cast</code> and no type checks), with the exact tie-break and output format

0.75

Hints

Hint 1 · Which class knows how to copy a vehicle?

The trailer receives a base identifier, but all you can get is a Vehicle&: the concrete type is unknown at that point. You cannot write Vehicle copy = original;. The class is abstract, and even if it were not, you would slice the object. The question "copy yourself" must be answered by the object itself. That is what the virtual clone() is for: each concrete class implements it with its own copy constructor.

Hint 2 · Does Trailer inherit from Vehicle, contain a Vehicle, or both?

Both. A Trailer is a vehicle, because it lives in the fleet and competes in Q. It also has a vehicle, stored in a std::unique_ptr<Vehicle> member. Each method delegates to that member and adds its own part. cost adds, range shrinks and describe prepends a prefix. Nested trailers then work by plain recursion, with no special loops.

Hint 3 · What happens when a Trailer is copied?

A unique_ptr cannot be copied, so the implicit copy constructor of Trailer is deleted. You have to write it yourself. Initialise the Vehicle part explicitly, then call o.base_->clone() to duplicate the base. Check your design with a trailer of a trailer. Then tune the middle one: the outer one must not change.

Solution

Explained solution

The solution has three levels. Vehicle is the abstract interface. Rated is an intermediate class that factors out what vans and electric vans share: the price per kilometre, the range and the tuning. Below it are the concrete classes, all marked final. Trailer is a decorator: it inherits from Vehicle and also wraps another Vehicle that it owns exclusively.

The main program knows the concrete types only when it registers a vehicle. After that it uses nothing but virtual calls through std::unique_ptr<Vehicle>.

#include <iostream>
#include <map>
#include <memory>
#include <string>
#include <utility>
#include <vector>

// Abstract interface: never instantiated directly.
class Vehicle {
public:
    explicit Vehicle(std::string id) : id_(std::move(id)) {}
    virtual ~Vehicle() = default;

    const std::string& id() const { return id_; }

    virtual long long cost(long long km) const = 0;
    virtual long long range() const = 0;
    virtual void describe(std::string& out) const = 0;
    virtual std::unique_ptr<Vehicle> clone() const = 0;
    virtual bool tune(long long) { return false; }

protected:
    // Copying is only reachable from derived classes: no slicing from outside.
    Vehicle(const Vehicle&) = default;
    Vehicle& operator=(const Vehicle&) = default;

private:
    std::string id_;
};

// Intermediate class: vehicles with a tunable price per kilometre.
class Rated : public Vehicle {
public:
    Rated(std::string id, long long cpk, long long rng)
        : Vehicle(std::move(id)), cpk_(cpk), rng_(rng) {}

    long long range() const override { return rng_; }
    bool tune(long long value) override {
        cpk_ = value;
        return true;
    }

protected:
    long long cpk_;
    long long rng_;
};

class Van final : public Rated {
public:
    using Rated::Rated;

    long long cost(long long km) const override { return cpk_ * km; }
    void describe(std::string& out) const override {
        out += "V(";
        out += std::to_string(cpk_);
        out += ")";
    }
    std::unique_ptr<Vehicle> clone() const override {
        return std::make_unique<Van>(*this);
    }
};

class Electric final : public Rated {
public:
    using Rated::Rated;
    static constexpr long long CHARGING_FEE = 150;

    long long cost(long long km) const override {
        return cpk_ * km + CHARGING_FEE;
    }
    void describe(std::string& out) const override {
        out += "E(";
        out += std::to_string(cpk_);
        out += ")";
    }
    std::unique_ptr<Vehicle> clone() const override {
        return std::make_unique<Electric>(*this);
    }
};

class Bike final : public Vehicle {
public:
    using Vehicle::Vehicle;

    long long cost(long long km) const override { return 40 * km; }
    long long range() const override { return 25; }
    void describe(std::string& out) const override { out += "B"; }
    std::unique_ptr<Vehicle> clone() const override {
        return std::make_unique<Bike>(*this);
    }
};

// Decorator: IS a Vehicle and exclusively HAS another Vehicle.
class Trailer final : public Vehicle {
public:
    Trailer(std::string id, std::unique_ptr<Vehicle> base, long long extra)
        : Vehicle(std::move(id)), base_(std::move(base)), extra_(extra) {}

    // Deep copy: the base is duplicated through its own clone().
    Trailer(const Trailer& o)
        : Vehicle(o), base_(o.base_->clone()), extra_(o.extra_) {}

    long long cost(long long km) const override {
        return base_->cost(km) + extra_ * km;
    }
    long long range() const override {
        return base_->range() * 8 / 10;
    }
    void describe(std::string& out) const override {
        out += "T(";
        out += std::to_string(extra_);
        out += ")+";
        base_->describe(out);
    }
    std::unique_ptr<Vehicle> clone() const override {
        return std::make_unique<Trailer>(*this);
    }
    bool tune(long long value) override {
        extra_ = value;
        return true;
    }

private:
    std::unique_ptr<Vehicle> base_;
    long long extra_;
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    if (!(std::cin >> n)) return 0;

    std::vector<std::unique_ptr<Vehicle>> fleet;
    std::map<std::string, std::size_t> index;

    auto add = [&](std::unique_ptr<Vehicle> v) {
        index[v->id()] = fleet.size();
        fleet.push_back(std::move(v));
    };

    for (int k = 0; k < n; ++k) {
        char op = ' ';
        std::cin >> op;
        if (op == 'V' || op == 'E') {
            std::string id;
            long long cpk = 0, rng = 0;
            std::cin >> id >> cpk >> rng;
            if (op == 'V') add(std::make_unique<Van>(id, cpk, rng));
            else add(std::make_unique<Electric>(id, cpk, rng));
        } else if (op == 'B') {
            std::string id;
            std::cin >> id;
            add(std::make_unique<Bike>(id));
        } else if (op == 'T') {
            std::string id, base;
            long long extra = 0;
            std::cin >> id >> base >> extra;
            const Vehicle& original = *fleet[index.at(base)];
            add(std::make_unique<Trailer>(id, original.clone(), extra));
        } else if (op == 'C') {
            std::string id;
            long long value = 0;
            std::cin >> id >> value;
            if (!fleet[index.at(id)]->tune(value)) {
                std::cout << "NOT_TUNABLE " << id << '\n';
            }
        } else if (op == 'Q') {
            long long km = 0;
            std::cin >> km;
            const Vehicle* best = nullptr;
            long long bestCost = 0;
            for (const auto& v : fleet) {
                if (v->range() < km) continue;
                long long c = v->cost(km);
                if (best == nullptr || c < bestCost ||
                    (c == bestCost && v->id() < best->id())) {
                    best = v.get();
                    bestCost = c;
                }
            }
            std::cout << km << ": ";
            if (best != nullptr) std::cout << best->id() << ' ' << bestCost << '\n';
            else std::cout << "NONE\n";
        } else if (op == 'L') {
            if (fleet.empty()) std::cout << "EMPTY FLEET\n";
            for (const auto& v : fleet) {
                std::string d;
                v->describe(d);
                std::cout << v->id() << ' ' << d << " range=" << v->range() << '\n';
            }
        }
    }
    return 0;
}

The abstract base. Vehicle declares a virtual destructor because the fleet destroys every object through a unique_ptr<Vehicle>. Without it, deleting a Van through a base pointer is undefined behaviour. The copy constructor and copy assignment are protected. Derived classes can use them to copy themselves, but outside code cannot write a copy of a Vehicle that slices the object. tune is not pure: its default returns false, which is why Bike never mentions it.

The intermediate class. Rated implements neither cost nor describe, so it stays abstract. It does implement range and tune, which are identical for vans and electric vans. Van and Electric inherit its constructor with using Rated::Rated;. They add only their cost formula, their letter in the description and their clone, which is one line: std::make_unique<Van>(*this). There the concrete type is known, because the code sits inside the class itself. This is the classic "virtual constructor" idiom.

The decorator. Trailer keeps base_ in a unique_ptr<Vehicle>, so it is the sole owner. In main, the T command finds the original with index.at(base) and hands Trailer the result of original.clone(), never the original itself. The hand-written copy constructor does two things. First, it initialises Vehicle(o), which copies the identifier; leaving it out does not compile, because Vehicle has no default constructor. Second, it calls o.base_->clone(), which recurses when the base is another trailer.

Checking against the tests. In the example, R1 is built on F1 when its rate is 30. Then C F1 25 changes F1, and the listing shows F1 V(25) while R1 remains T(10)+V(30). The 400 km query agrees: R1 would cost 16000 against 10000 for F1. In the nested-trailer test, M2 is built by cloning M1, which already holds its own clone of Z9. After C M1 0, M2 still reads T(5)+T(5)+V(20).

Queries. Q walks the fleet, skips any vehicle whose range is too short (v->range() < km), and compares by cost, then by identifier. The nested test checks this at 640 km. Z9 and M1 tie at 12800, and M1 wins even though it was registered later. The trailer's range is range*8/10. In the bike test, 25·8/10 = 20, which is why TR takes part in the 20 km query and loses to CARGO, 860 against 800. describe takes a std::string& and appends to it, instead of concatenating and returning copies. Describing a trailer chain therefore stays linear in its depth.

Code and tests on GitLab

Test cases

Case	Input	Expected output	Actual output	Result
Statement example	11 V F1 30 500 E E1 12 180 B BIKE T R1 F1 10 Q 20 Q 200 C F1 25 L Q 400 C BIKE 50 Q 600	20: E1 390 200: F1 6000 F1 V(25) range=500 E1 E(12) range=180 BIKE B range=25 R1 T(10)+V(30) range=400 400: F1 10000 NOT_TUNABLE BIKE 600: NONE	20: E1 390 200: F1 6000 F1 V(25) range=500 E1 E(12) range=180 BIKE B range=25 R1 T(10)+V(30) range=400 400: F1 10000 NOT_TUNABLE BIKE 600: NONE	OK
Nested trailers and tie-break	8 V Z9 20 1000 T M1 Z9 5 T M2 M1 5 L Q 100 C M1 0 L Q 640	Z9 V(20) range=1000 M1 T(5)+V(20) range=800 M2 T(5)+T(5)+V(20) range=640 100: Z9 2000 Z9 V(20) range=1000 M1 T(0)+V(20) range=800 M2 T(5)+T(5)+V(20) range=640 640: M1 12800	Z9 V(20) range=1000 M1 T(5)+V(20) range=800 M2 T(5)+T(5)+V(20) range=640 100: Z9 2000 Z9 V(20) range=1000 M1 T(0)+V(20) range=800 M2 T(5)+T(5)+V(20) range=640 640: M1 12800	OK
Empty fleet	2 L Q 5	EMPTY FLEET 5: NONE	EMPTY FLEET 5: NONE	OK
Bike at the range limit	5 B CARGO Q 25 Q 26 T TR CARGO 3 Q 20	25: CARGO 1000 26: NONE 20: CARGO 800	25: CARGO 1000 26: NONE 20: CARGO 800	OK
Electric fixed fee	6 E VE 10 300 V VF 11 300 Q 100 Q 200 C VE 9 Q 100	100: VF 1100 200: VE 2150 100: VE 1050	100: VF 1100 200: VE 2150 100: VE 1050	OK
No operations	0	(empty)	(empty)	OK

Actual outputs: code compiled with g++ 14.4.0 (C++20) and run in an isolated container on 25 October 2026.

Complexity

Let V be the number of vehicles and d the maximum nesting depth (≤ 50). cost, range and describe walk the chain of bases, so each costs O(d). A Q or L command costs O(V·d). A T registration clones the whole base in O(d) and inserts into the std::map in O(log V). C costs O(log V) for the lookup plus O(1) for the tuning.

For the worst case, count about 2·51 virtual calls per vehicle per query, one range and one cost per level. A crude bound treats vehicles and queries as independent, with 1000 of each: 1000 · 1000 · 102 ≈ 108 calls. That is still comfortable within 5 seconds. In fact vehicles and queries share the same N ≤ 1000 operations, so V·Q ≤ 500·500. The real ceiling is therefore about 2.6·107 calls.

For memory, every trailer owns its own full copy of the chain it wraps, so the total is O(V·d) objects, at most about 5·104. That is the price of the value semantics the statement requires. The shared alternative in the variants would save memory but change the test outputs.

Common mistakes

• Forgetting virtual on the destructor of Vehicle. The program may print the right answer in every test and still have undefined behaviour when the fleet is destroyed, leaking the base of every trailer.
• Storing in Trailer a pointer or reference to the fleet vehicle instead of a clone. After C F1 25, the example listing would show T(10)+V(25) and the 400 km cost of R1 would change.
• Writing range()/10*8, or using 0.8 with double. With the first, the towed bike would get range 16 instead of 20 and the bike test would fail. With the second, rounding errors appear when truncating.
• Breaking ties by registration order instead of by identifier. In the nested-trailer test, the 640 km query would return Z9 instead of M1.
• Handling C with dynamic_cast, or with a type field and a switch. It works, but it breaks the required design: every new type forces a change in main. A virtual tune with a default implementation avoids that.
• Implementing clone only in the base, or as std::make_unique<Vehicle>(*this). That does not compile because the class is abstract. Even if it did compile, it would slice the object.

Variants

Trailers that follow the original

Suppose the statement required a trailer to reflect later changes to its base. Ownership would then no longer be exclusive. You would switch to std::shared_ptr<Vehicle> in both the fleet and base_, and the T command would share the pointer instead of cloning. The test outputs would change: in the example, R1 would be listed as T(10)+V(25). This is the gap between value semantics and reference semantics. It is worth comparing with polymorphism and dynamic binding in Java, where every object is handled by reference.

Covariant return type

With raw pointers, each derived class may declare Van* clone() const override. C++ allows covariant return types for pointers and references, but not for unique_ptr. The cost is a manual delete. A common compromise has two parts. A private virtual method returns the covariant raw pointer, and a public non-virtual clone() wraps it in a unique_ptr.

Adding a new type without touching the queries

You are asked to add a motorbike with cost 25·km + 50 and range 120 that cannot be tuned. One final class that inherits from Vehicle and implements the four pure methods is enough. Add one registration line in the reader. Neither Q, L nor C changes, which shows the design is open for extension.

What the professor will ask

“Suppose I change base_ to a raw Vehicle*, delete your hand-written copy constructor and free base_ in Trailer's destructor. What does the nested-trailer test print, and is the program correct?”

It prints exactly the same, and the program is still wrong. Follow the objects. T M1 Z9 5 calls Z9.clone(), which uses the Van copy constructor and yields a separate van, call it Z9'. M1.base_ points to Z9', and the original Z9 is never shared. T M2 M1 5 calls M1.clone(), and the implicit copy constructor copies only the pointer. So the inner trailer of M2 has its own extra_, but its base_ is the same Z9' that M1 owns. C M1 0 changes only M1.extra_, a value member, and no command can reach Z9'. That is why the listing reveals nothing. The failure comes when main ends. M1's destructor deletes Z9', then M2 deletes its inner trailer, which deletes Z9' again. That is a double free, which is undefined behaviour; it may abort only after the output has been written. The example test is unaffected, because cloning a van shares nothing. The lesson: green tests do not prove that memory ownership is right. With unique_ptr, this mistake does not even compile.

On the syllabus

Class reuse through inheritance and contracts defined by interfaces are listed in the syllabus of ISIS1209 APO II Honores at Universidad de los Andes. The programme of IIC2233 Programación Avanzada at Pontificia Universidad Católica de Chile includes applying inheritance, polymorphism and interfaces to design complex programs. This exercise works on those same ideas in C++, through the abstract class and the decorator.

The other half of the exercise is deciding who owns each dynamic object, which ties in with managing dynamic memory through pointers and references. That topic appears in the syllabus of Algoritmos y Programación II (75.41) at Universidad de Buenos Aires.

Opinion · Missing context

The hierarchy is the easy part. Most students draw it correctly in five minutes. What decides the mark is ownership: who holds each object, whether a change should travel, and who frees what at the end. My reading is that this exercise rewards the student who settles the copy question before typing, not the one who writes the most classes. The professor's trap makes the point bluntly. Every test can pass while the program frees the same memory twice. Passing output is evidence, not proof.

Related articles from LaRebelión

Solved exercise: exact rank and determinant with Bareiss in CSolved exercise: normalize a string in place with pointers in CSolved exercise: classes and objects with a wallet in Java

• Programming exercises
• Solved exercise: warehouse inventory with classes, TreeMap and exceptions in Java
• Solved exercise: counting inversions with merge sort in Java

Article generated with AI.larebelion · Reviewed by Jose Santamaria

Byline · Chief editor · English edition · London

“Anyone can draw the hierarchy; the mark goes to whoever decides who owns each object and when it dies.”