CODEWITHSUNDEEP
c++sortinginheritance
José D.
José D.

Reputation: 4275

Sort a std::vector by type

I was watching http://channel9.msdn.com/Events/GoingNative/2013/Writing-Quick-Code-in-Cpp-Quickly and around min 36, they talk about the benefits of sorting a collection by the type of its elements if you are going to be calling virtual methods on them.

So given

class Base {};
class Der1 : public Base {};
class Der2 : public Base {};
class Der3 : public Base {};

vector<Base *> myVector;

How could you sort myVector in such a way that the elements of each type are all adjecent?

Is there any way to do that without using a virtual function in order to indentify each derived type? (Maybe using typeid?)

Upvotes: 6

Views: 854

Answers (4)

jrok
jrok

Reputation: 55415

You can use type_index for this. You constructing one from a type_info object that's returned from typeid operator. It's a class with overloaded relational operators with well defined ordering, so that it is useful as a key type in associative containers and alike.

Here's an example:

#include <typeinfo>
#include <typeindex>
#include <vector>
#include <algorithm>
#include <iostream>

struct Base {
    virtual ~Base() {}
    virtual const char* who() = 0;
};
struct D1 : Base { const char* who() { return "D1\n"; } };
struct D2 : Base { const char* who() { return "D2\n"; } };
struct D3 : Base { const char* who() { return "D3\n"; } };

int main()
{
    std::vector<Base*> vec { new D2, new D1, new D3, new D3, new D1, new D2 };
    std::sort( vec.begin(), vec.end(),
    [](const Base* p1, const Base* p2)
    {
        return
            std::type_index(typeid(*p1)) <
            std::type_index(typeid(*p2));
    });

    for (auto p : vec) { std::cout << p->who(); }
}

The output is:

D1
D1
D2
D2
D3
D3

Upvotes: 11

Sebastian Mach
Sebastian Mach

Reputation: 39109

These are just possibilities, there is not one true answer to this.

Sorting?

The main problem of sorting is finding a key upon which to sort. This is "phase 1", if you want. Phase 2 is using a generic sorting from the standard library and is often easier than phase 1.

Keying

One possibility is to use typeid / type_info.

Instances of type_info define operator == and operator !=, as well as a hash_code member function.

Sorting

Use a generic sort algorithm from the standard algorithm. As the key for sorting you could use e.g. the value returned from the hash_code function.

Upvotes: 0

Codor
Codor

Reputation: 17605

You could implement a virtual function, say prio which returns the priority (an int) among the types; prio would be suitably implemented in the derived classes. Then implement a comparator which would evaluate prio on two instances of Base to compare them.

Upvotes: 0

Daniel Daranas
Daniel Daranas

Reputation: 22634

You specify the comparison function. For more details on that, see for example Sorting an STL vector on two values.

Inside the comparison function you can write whatever you want. It can compare whatever properties of your objects. In particular, it can compare one specific value obtained via a virtual function, such as getType(), which may return 1 in Der1, 2 in Der2 and 3 in Der 3.

Upvotes: 0

Related Questions