3
\$\begingroup\$

I'm learning from "Jumping into C++" by Alex Allain (sample chapter and TOC) and solved the first problem in Chapter 26 "Inheritance and Polymorphism".

I'm especially concerned about my use of dynamic_cast, as that isn't covered yet and I suspect there's a better way.

Implement a sort function that takes a vector of pointers to an interface class, Comparable, that defines a method, compare(Comparable& other), and returns 0 if the objects are the same, 1 if the object is greater than other, and -1 if the object is less than other. Create a class that implements this interface, create several instances, and sort them. If you're looking for some inspiration for what to create-try a HighScoreElement class that has a name and a score, and sorts so that the top scores are first, but if two scores are the same, they are sorted next by name.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Comparable
{
public:
    virtual ~Comparable() { }
    virtual int compare(const Comparable& other) const = 0;
};

class HighScoreElement : public Comparable
{
public:
    HighScoreElement(string name, int score)
        : _name(name), _score(score)
    {
    }
    string getName() const {
        return _name;
    }
    int getScore() const {
        return _score;
    }
    virtual int compare(const Comparable& other) const {
        const HighScoreElement *other_hse = dynamic_cast<const HighScoreElement*>(&other);
        if (other_hse) {
            int this_score = getScore(),
                other_score = other_hse->getScore();
            if (other_score > this_score) {
                return -1;
            } else if (other_score < this_score) {
                return 1;
            } else {
                string this_name = getName(),
                       other_name = other_hse->getName();
                if (other_name > this_name) {
                    return -1;
                } else if (other_name < this_name) {
                    return 1;
                } else {
                    return 0;
                }
            }
        }
        // an exception should be thrown here
        return 0;
    }
private:
    string _name;
    int _score;
};

void sortComparableVector(vector<Comparable*>& v) {
    for (int i = 0, e = v.size() - 1; i < e; i++) {
        int sorted_i = i;
        for (int j = i + 1; j < e + 1; j++) {
            if (v[sorted_i]->compare(*v[j]) < 0) {
                sorted_i = j;
            }
        }
        if (sorted_i != i) {
            Comparable *replacement = v[sorted_i];
            v[sorted_i] = v[i];
            v[i] = replacement;
        }
    }
}

int main()
{
    vector<Comparable*> v;

    v.push_back(new HighScoreElement("Kate Bush", 10));
    v.push_back(new HighScoreElement("Peter Gabriel", 20));
    v.push_back(new HighScoreElement("Robert Fripp", 5));
    v.push_back(new HighScoreElement("Phil Collins", 25));
    v.push_back(new HighScoreElement("Roger Waters", 25));
    v.push_back(new HighScoreElement("David Gilmour", 15));

    sortComparableVector(v);

    for (unsigned i = 0; i < v.size(); i++) {
        const HighScoreElement *el = dynamic_cast<const HighScoreElement*>(v[i]);
        cout << i << ": " << el->getScore() << '\t' << el->getName() << '\n';
    }

    return 0;
}
\$\endgroup\$
3
\$\begingroup\$
  1. Avoid using namespace std. You just don't know what-all symbols that spews into your global namespace, causing lots of grief when you least suspect it.

  2. Your interface should contain protected default-constructor, copy-constructor, and copy-assignment-operator.

  3. You should use =default when you are explicitly defaulting a special-member-function, so it can stay trivial.

  4. If you use a struct, default-access is public instead of private, which would allow you to dispense with some access-specifiers.
    Though that can be controversial for classes which have non-public members, or generally any feature not supported by C.

struct Comparable {
    virtual ~Comparable() = default;
    virtual int compare(const Comparable& other) const = 0;
protected:
    Comparable() = default;
    Comparable(const Comparable&) = default;
    Comparable& operator=(const Comparable&) = default;
};
  1. HighScoreElement should be marked final, prohibiting further derivation and thus allowing some optimizations, unless you redesign it for inheritance. Which you actually shouldn't do.

  2. Don't needlessly create copies of non-trivial types on call / return, use constant references.
    Only HighScoreElement::getName fails that now.

  3. Consider marking overrides with override, which in contrast to repeating virtual actually is meaningful.

  4. You should bail out immediately if your dynamic_cast fails.
    Consider just changing it to a reference-cast so that's automated.

  5. Avoid useless blocks and concomitant further indentation.
    After a return, processing leaves the function immediately.

int compare(const Comparable& other) const override {
    auto&& x = dynamic_cast<const HighScoreElement&>(other);
    if(getScore() < x.getScore())
        return -1;
    else if(getScore() > x.getScore())
        return 1;
    if(getName() < x.getName())
        return -1;
    else if(getName() > x.getName())
        return 1;
    return 0;
}
  1. There's std::swap in <utility> for swapping two items.

  2. Insertion-sort isn't the best algorithm there is, but it will get the job done, as long as the vector isn't too big.

  3. You should use a smart-pointer to manage your elements, best-suited is probably std::unique_ptr from <memory>.

  4. You could use list-initialization to initialize your vector instead of adding the elements afterwards one-by-one:

    vector<Comparable*> v {
        new HighScoreElement("Kate Bush", 10),
        new HighScoreElement("Peter Gabriel", 20),
        ...
    };
    
  5. return 0; is implicit in C++ and C99+ for main.

\$\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.