4
\$\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\$
0
4
\$\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\$
0
1
\$\begingroup\$

I tackled the book a time ago, skipped this chapter and came back now since this topic is highly/excessive used in the Qt Toolkit - even tho its a while ago.

Anyhow, you asked for:

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

Yes, by declaring the compare in the Comparable class itself, you made it pure virtual - I guess this wouldn't match the requirement since it really matters if you use it that way.

  1. I also rewrote the sort algorithm from the book working very efficient in here.

  2. It is also a good idea to move the whole initialization and random generation into the class itself - probably declared as virtual in the interface class and I red somewhere it would be better to let the class handle the deletion or like recommended using a smart pointer. I just did raw pointers with delete to test the classes.

  3. I also used std::swap to swap vector entries, declared variables with a{}; and <random> even tho the book is intentionally ante c++11 - this code compiles fine with the c++17 compiler flag.

  4. To avoid unnecessary errors it is a good habit not to use using namespace std; because there are hundreds of questions in stackoverflow about it. If you are fed up writing std::cout or std::endl f.e. just declare using std::cout, std::endl; instead of the whole namespace - but that's covered in the following chapter a bit. It's not wrong for small examples but not a good habit in projects.

  5. I added a random test with random names from a list of 10.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm> //std::swap()
#include <random>

using my_engine = std::random_device;


class Comparable
{
private:

public:
    virtual int getNumber() = 0;
    virtual std::string getName() = 0;
//rule of three
    Comparable() = default;
    virtual    Comparable &operator=(const Comparable& other) = default;
    virtual ~Comparable() = default;

    int compare(Comparable& other);
};

class HighScoreElement : public Comparable
{
private:
    std::vector<Comparable*> _p_Vector;
    std::string _player{};
    int _score{};

public:
    std::string getName() override {return _player;}
    int getNumber() override {return _score;}
//rule of three
    virtual HighScoreElement &operator=(const HighScoreElement& other) = default;
    HighScoreElement(std::vector<Comparable*> p_Vector):_p_Vector(p_Vector){}
    HighScoreElement(std::string player, int score): _player(player), _score(score){}
    virtual ~HighScoreElement() = default;

    void setVector(std::vector<Comparable*>& p_Vector){_p_Vector = p_Vector;}
    std::vector<Comparable*>& getVector(){return _p_Vector;}
    void setNewElement(std::string name, int number);
    void getAllElements();

    std::string randomNames();
    int randomNumber(int size);
};

void sort(HighScoreElement &team);
size_t findSmallestRemainingElement(HighScoreElement &team, size_t index);

int main()
{

    std::vector<Comparable*> p_Vector;
    HighScoreElement *team1 = new HighScoreElement(p_Vector);
    int teamplayer{team1->randomNumber(20)};

    for(int i = 0; i < teamplayer; ++i){
    team1->setNewElement(team1->randomNames(), team1->randomNumber(10));
    }

    std::cout << "\n\n######## Random order test: ########" << std::endl;
    team1->getAllElements();
    sort(*team1);
    std::cout << "\n######## Sorted order test: ########" << std::endl;
    team1->getAllElements();

    HighScoreElement *team2 = new HighScoreElement(p_Vector);
    for(int i = 0; i < teamplayer; ++i){
    team2->setNewElement(team2->randomNames(), team2->randomNumber(10));
    }

    std::cout << "\n\n######## Random order test: ########" << std::endl;
    team2->getAllElements();
    sort(*team2);
    std::cout << "\n######## Sorted order test: ########" << std::endl;
    team2->getAllElements();

    delete team1;
    delete team2;

    return 0;
}

void sort(HighScoreElement &team)
{
   std::vector<Comparable*> p_Vector = team.getVector();
   for(size_t i = 0; i < p_Vector.size(); ++i){
       int index = findSmallestRemainingElement(team, i);
       std::swap(p_Vector[i], p_Vector[index]);
       team.setVector(p_Vector);
   }
}
size_t findSmallestRemainingElement(HighScoreElement &team, size_t index)
{
   std::vector<Comparable*> p_Vector = team.getVector();
   int result{};

    size_t index_of_smallest_value = index;
    for(size_t i = index +1; i < p_Vector.size(); ++i){
        result = p_Vector[i]->compare(*p_Vector[index_of_smallest_value]);
        if(result == -1){
            index_of_smallest_value = i;
            team.setVector(p_Vector);
        }
    }
    return index_of_smallest_value;
}

void HighScoreElement::setNewElement(std::string name, int number)
{
    _p_Vector.push_back(new HighScoreElement(name, number));
}

void HighScoreElement::getAllElements()
{
    for(size_t i = 0; i < _p_Vector.size(); i++){
        std::cout << _p_Vector[i]->getNumber() << " <-- ";
        std::cout << _p_Vector[i]->getName() << std::endl;
    }
}

std::string HighScoreElement::randomNames()
{
    std::string firstName[10]={"Jenny", "Sarah", "Belinda", "Mary", "Mark", "John", "Jack", "Jeff", "Peter", "Betty"};
    std::string lastName[10]={"Cunningham", "Johnson", "Stuard", "Furgeson", "Meyer", "Brown", "Brackston", "Harrison", "McCartney", "Harrington"};
    std::string name = firstName[randomNumber(9)] + " " + lastName[randomNumber(9)];
    return name;
}

int HighScoreElement::randomNumber(int size)
{
    my_engine engnSize;
    std::uniform_int_distribution<int> distSize(0,size);
    int number = distSize(engnSize);
    return number;
}

int Comparable::compare(Comparable &other)
{
    //    std::cout << this->getNumber() << std::endl;
    //    std::cout << other.getNumber() << std::endl;
    int Number1 = this->getNumber(), Number2 = other.getNumber();
    std::string Name1 = this->getName(), Name2 = other.getName();

    //same as other return 0;1
    if(Number1 == Number2){
        //If same as check name
        if(Name1 == Name2){
            return 0;
        }else if(Name1 > Name2){
            return 1;
        }else if(Name1 < Name2){
            return -1;
        }else{
            return 99;
        }
        //grater than other return 1;
    } else if(Number1 >= Number2){
        return 1;
        //less than other return -1;
    } else if(Number1 <= Number2){
        return -1;
    }else{
        std::cout << "Invalid Comparision" << std::endl;
        return 99;
    }
}
\$\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.