Sort objects and polymorphism

Question

Suppose I have a class A.

And B and C are child of A.

Class A has a generic algorithm for sorting arrays of type A, so that I could use it for B and C without writing again the algorithm for each.

In the algorithm, sometimes I have to swap. The problem is that I can only see the objects as type A, and if I do:

A aux = array[i]
array[i] = array[j]
array[j] = aux

I think I have a problem. Because array[i], maybe its of type B, and aux is of type A, so I think I'm losing information.

I'm sure u understand this situation... how can I sort a generic array of objects using a father method algorithm?

Edit: The initial array it's static.

Edit2: So its imposible to have: A::sort(A array[]); And do what I want?, cannot swap.

The only way is having an array of references? A* array[]?

Answer 1

Polymorphic objects are referred to by pointers or references (or pointer wrappers). Swapping pointers is sufficient then. Actually, you should be able to use std::sort or std::stable_sort with a suitable predicate:

// 'A' defines 'float getSortKey()'

bool mypred(B* first, B* second) {
   return first->getSortKey() < second->getSortKey();
}

std::vector<B*> them;
std::sort(them.begin,them.end(),mypred);

This strategy avoids object slicing.

Answer 2

@ritmbo, as long as you are not familiar with polymorphism mechanisms, an explanation is needed to fine @Alexander's answer.

Why do you have to change std::vector<A> into std::vector<A*>?

You want to have a collection of objects of base class, so in order to sort them, you need to move responsibility of object comparison from class A to B and C. To do so, in OOP you use virtual functions. They are bound to an object as a virtual table. If you cast B* to A*, e.g. A* a = new B;, the vtable of a is overwritten by methods from new B. But if you cast B to A, e.g. A a = B(), no method pointers are copied to a's vtable.

Long story short, you won't move comparison responsibility to class B and C without using pointers (or references, but that's more difficult to maintain).

Answer 3

I've got an idea. Your 'polymorphism' tag is quite misleading if you want to store by values. How about simply overwriting the key value in A class objects, which is used by A::sort?

struct A
{
    int key;
    A(int _key) : key(_key) {}
    static sort(A array[]); // uses 'key'
};

struct B : public A
{
    B() : A( generate_B_key() ) {}
};

struct C : public A
{
    C() : A( generate_C_key() ) {}
};