C++ polymorphism without pointers

Question

EDIT: A better title for this would be: polymorphism for large collections of objects without individual heap allocations.

Suppose that I have a base class Animal with virtual functions and some derived classes (Cat, Dog, etc.). The real derived classes contain 4-8 bytes of data. I want to store a std::list<Animal> which actually contains items which are derived objects. I want to avoid the creation of many small objects on the heap using new.

Is there any design pattern which can be used to achieve this?

EDIT: My ideas to implement this

1. create std::deque<Cat>, std::deque<Dog>, ...; store std::list<Animal*> which contains pointers from the deques; I use the std::deque because I suppose that it has a good memory management with chunks of objects;

Conic

Why do you want to "avoid the creation of many small objects on the heap using new"? If doing that is a bottleneck, why not work on more efficient memory management routines? – Jankey

If not using the heap then you must use the stack - i.e they must always be in scope! – Stendhal

You can allocate a large array of char on the heap and use placement new if you wanted. But remember that the creation of many small objects on the heap using new is better than the creation of many large objects on the heap using new. And the only way to use polymorphism without pointers is with references. – Melee

I've just moved from using vectors (where I knew what size I wanted) back to 2xPOD members- one a pointer the other the size. Vectors have OOB checks on some implementations and it all started to add up to more than just storing the size separately. – Byelection

In languages like Java, all the objects are created on the heap (i.e. dynamic memory), and an "object" is actually a "reference" to the object. All the reference (like pointers in C) have the same size (e.g. 8 bytes), hence there is no problem with adding to a container references of different kind of objects. In C++, for the same reason, you can do polymorphism with pointers. In contradiction, the objects themselves may have different size in bytes, which is the reason it's impossible to assign object of some type into a variable of another type-hence polymorphism is enabled only for pointers – Losel

Answer 1

Ultimately, no.

Polymorphism only works with non-value types: references and pointers. And since references can only be bound once, you cannot really use them in standard containers. That leaves you with pointers.

You're attacking the problem at the wrong end. If you are concerned about the overhead of allocating lots of small objects (and I'm assuming that this is a legitimate concern. That is, you have actual profiling data or sufficient experience to know it is a concern for your specific application), then you should fix that. Change how you're allocating memory for these objects. Make a small allocation heap or something.

Admittedly, pre-C++0x's allocators are somewhat lacking in this regard, since they have to be stateless. But for your purposes, you should be able to deal with it.

---

From your edit:

That is a terrible idea. Erasing from a std::deque at anywhere but the start or end will invalidate every pointer in your std::list.

Given your comment, this idea is functional. However, having all of these different memory blocks for different kinds of objects seems to go against the whole point of inheritance. After all, you can't just write a new type of Animal and slip it into the std::list; you have to provide memory management for it.

Are you sure that inheritance-based polymorphism is what you need here? Are you sure that some other methodology would not work just as well?

Rimini

Probably I should mention that all the objects will be deleted at the same time. – Conic

@Andrei: Yes, that is kind of important to know ;) – Rimini

Answer 2

I realize that this question is old, but I found a somewhat pretty solution.

Assumption:

You know all the derived classes in advance (given your edit, this is true).

Trick:

Using boost::variant (http://www.boost.org/doc/libs/1_57_0/doc/html/variant.html)

Example classes:

class Animal {
public:
    virtual void eat() = 0;
};

class Cat : public Animal {
    virtual void eat() final override {
        std::cout << "Mmh, tasty fish!" << std::endl;
    }
};

class Dog: public Animal {
    virtual void eat() final override {
        std::cout << "Mmh, tasty bone!" << std::endl;
    }
};

Example variant/visitor:

typedef boost::variant<Cat, Dog> AnimalVariant;

class AnimalVisitor : public boost::static_visitor<Animal&> {
public:
    Animal& operator()(Cat& a) const {
        return a;
    }

    Animal& operator()(Dog& a) const {
        return a;
    }
};

Example usage:

std::vector<AnimalVariant> list;
list.push_back(Dog());
list.emplace_back(Cat());

for(int i = 0; i < 5; i++) {
    for(auto& v : list) {
        Animal& a = v.apply_visitor(AnimalVisitor());
        a.eat();
    }
}

Example output

Mmh, tasty bone!
Mmh, tasty fish!
Mmh, tasty bone!
Mmh, tasty fish!
Mmh, tasty bone!
Mmh, tasty fish!
Mmh, tasty bone!
Mmh, tasty fish!
Mmh, tasty bone!
Mmh, tasty fish!

Gigahertz

yes that's what I call the "interleaved" approach which is the most efficient when all your classes have the same sizeof. because the padding is null. Brian Coleman approach's is best when sizeof has great variations among the types. This is something that can be evaluated at compile time with a sigma (standard deviation) meta function and select with mpl::if_ or something, or use SFINAE, or simply specialization, to have an implementation using variant for low sigma, and pools for high sigmas. – Mielke

I have actually done something very similar on my micro controller because all uses of new are discouraged.....only boost is not available on micro controllers, so I wrote my own variant class – Catcher

With C++14 we can drop the definition of AnimalVisitor and use a lambda: Animal& a = v.apply_visitor([](const auto& pet) -> Animal& { return pet; }); – Streptococcus

Answer 3

If you're worried about allocating many small heap objects, then a vector may be a better choice of container rather than a list and a deque. list will allocate a node on the heap each time that you insert an object into the list, whereas vector will store all objects in a contiguous region of memory on the heap.

If you have:

std::vector<Dog> dogs;
std::vector<Cat> cats;

std::vector<Animal*> animals;

void addDog(Dog& dog, std::vector<Dog>& dogs, std::vector<Animal*>& animals) {
  dogs.push_back(dog);
  animals.push_back(&dog);
}

Then all dogs and cats are stored in two contiguous region of memory on the heap.

Sinfonietta

exactly. this is called the pooled approach. i'm thinking of generalizing this allocation pattern in some helper class that would take a template type list. the other pattern I'd like to provide is the "interleaved" which uses the maxof(sizeof(all types)) by making a vector of variant. – Mielke

This does not work at all. If anyone wants to do this, you must use a container like std::deque which will not move already-inserted elements (and invalidate the pointers). – Loquacity

Another reason this doesn't work is that dogs.push_back(dog) makes a copy of dog. The pointer pushed onto animals is to the original dog the parameter was referencing. Not the same dog! That pointer may become invalid depending on what the caller does. – Metatarsus

animals.push_back(&dog); should be something like animals.push_back(dogs.back());, for the reasons mentioned in comments above. – Polis

Answer 4

You probably could do something with a simple wrapper class for a union containing the super-set of data needed by every case. This would contain a pointer to shared strategy objects that contained the code for the different behaviours. So a cat is an object of class PolyAnimal with speciesName = "cat", a PredatorFeedingStrategy and so on.

Likely a better way of solving the underlying problem is setting up appropriate custom allocators for a more natural design.

Desmoid

The solution with the strategy pattern was my second idea (interesting how design patterns emerge when you write code even when you don't know about them :) ), but when I started to implement the solution it started to feel a little unnatural. Of course after some more thoughts about it, I will probably go with the custom allocators. – Conic

Answer 5

This is a follow-up on the suggestion to use a variant (be it Boost's or the one from the STL since cxx17), if all possible child-classes are known at compile time (this case is also known as "closed-set polymorphism").

Having to use the visitor pattern to access your object's interface is a bit annoying (imo), which is why I have written a variant-type that exposes the base-class interface (and even the base-type operators). It can be found at https://github.com/Krzmbrzl/polymorphic_variant (requires C++17 as it is built around std::variant).

Cloning the example from @Draziv:

Class-definitions

class Animal {
public:
    virtual void eat() = 0;
};

class Cat : public Animal {
    virtual void eat() final override {
        std::cout << "Mmh, tasty fish!" << std::endl;
    }
};

class Dog: public Animal {
    virtual void eat() final override {
        std::cout << "Mmh, tasty bone!" << std::endl;
    }
};

Example usage

pv::polymorphic_variant< Animal, Dog, Cat > variant;
variant->eat();

variant = Cat{};
variant->eat();

Output:

Mmh, tasty bone!
Mmh, tasty fish!

Wriggle