Sorting polymorphic classes 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&amp; 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 &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;string&gt;

using namespace std;

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

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

int main()
{
    vector&lt;Comparable*&gt; 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 &lt; v.size(); i++) {
        const HighScoreElement *el = dynamic_cast&lt;const HighScoreElement*&gt;(v[i]);
        cout &lt;&lt; i &lt;&lt; ": " &lt;&lt; el-&gt;getScore() &lt;&lt; '\t' &lt;&lt; el-&gt;getName() &lt;&lt; '\n';
    }

    return 0;
}
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.
Your interface should contain protected default-constructor, copy-constructor, and copy-assignment-operator.
You should use =default when you are explicitly defaulting a special-member-function, so it can stay trivial.
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&amp; other) const = 0;
protected:
    Comparable() = default;
    Comparable(const Comparable&amp;) = default;
    Comparable&amp; operator=(const Comparable&amp;) = default;
};



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.
Don't needlessly create copies of non-trivial types on call / return, use constant references.
Only HighScoreElement::getName fails that now.
Consider marking overrides with override, which in contrast to repeating virtual actually is meaningful.
You should bail out immediately if your dynamic_cast fails.
Consider just changing it to a reference-cast so that's automated.
Avoid useless blocks and concomitant further indentation.
After a return, processing leaves the function immediately.




int compare(const Comparable&amp; other) const override {
    auto&amp;&amp; x = dynamic_cast&lt;const HighScoreElement&amp;&gt;(other);
    if(getScore() &lt; x.getScore())
        return -1;
    else if(getScore() &gt; x.getScore())
        return 1;
    if(getName() &lt; x.getName())
        return -1;
    else if(getName() &gt; x.getName())
        return 1;
    return 0;
}



There's std::swap in &lt;utility&gt; for swapping two items.
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.
You should use a smart-pointer to manage your elements, best-suited is probably std::unique_ptr from &lt;memory&gt;.
You could use list-initialization to initialize your vector instead of adding the elements afterwards one-by-one:

vector&lt;Comparable*&gt; v {
    new HighScoreElement("Kate Bush", 10),
    new HighScoreElement("Peter Gabriel", 20),
    ...
};

return 0; is implicit in C++ and C99+ for main.