C++ Container of polymorphic objects with shared vptr

Question

Suppose that I need to store a collection of objects of the same type, but this type can't be defined at compile time. Suppose also that once this type is defined, it never changes. As well known, when the type is not know at compile time, it's possible to store these objects using a container of pointers to their base class, i.e.,

std::vector<Base*> collection;
collection.push_back( new Derived() );

In this way, allocated objects will not be necessarily stored side by side in memory, because in each allocation the new() will return an arbitrary position in memory. Furthermore, there is an extra pointer (vptr) embedded to each object, because the Base class of course needs to be polymorphic.

For this particular case (type is defined once + type never changes), the above solution is not the optimal solution, because, theoretically,

1. it's not necessary to store the same vptr (sizeof() = pointer size) for each object: all of them points to the same vtable;
2. it's possible to use contiguous storage locations, since the size of the objects are defined at the beginning of the program and will never change.

Q: Do you guys know a strategy/container/memory allocator/idiom/trick/anything else to overcome those problems?

I think I could do something like this (using the classic Shape example):

struct Triangle_Data {
    double p1[3],p2[3],p3[3];
};

struct Circle_Data {
    double radius;
};

struct Shape {
    virtual double area() const = 0;
    virtual char* getData() = 0;
    virtual ~Shape() {}
};

struct Triangle : public Shape {
    union {
        Triangle_Data tri_data;
        char data[sizeof(Triangle_Data)];
    };
    double area() const { /*...*/ };
    char* getData() { return data; }
    Triangle(char * dat_) {
        std::copy(dat_, dat_+sizeof(Triangle_Data), this->data);
    };
};

struct Circle : public Shape {
    union {
        Circle_Data circ_data;
        char data[sizeof(Circle_Data)];
    };
    double area() const { /*...*/ };
    char* getData() { return data; }
    Circle(char * dat_) {
        std::copy(dat_, dat_+sizeof(Circle_Data), this->data);
    };
};

template<class BaseT>
struct Container {
    int n_objects;
    int sizeof_obj;
    std::vector<char> data;
    Container(...arguments here...) : ...init here... {
        data.resize( sizeof_obj * n_objects );
    }
    void push_back(Shape* obj) {
        // copy the content of obj
        for( int i=0; i<sizeof_obj; ++i)
            data.push_back(*(obj.getData() + i));
    }
    char* operator[] (int idx) {
        return data + idx*sizeof_obj;
    }
};

// usage:
int main() {
    Container<Shape> collection( ..init here.. );
    collection.push_back(new Circle());
    cout << Circle(collection[0]).area() << endl; // horrible, but does it work?
};

Of course, this approach has a lot of problems with type safety, alignment, etc.. Any suggestion?

Thank you

Answer 1

1) it's not necessary to store the same vptr (8 bytes per object?) collection.size() times;

It is not necessary, but objects are independent of one another.

2) it's possible to use contiguous storage locations, since their size are known and equal to each other when their type is defined.

... indeed, if you can store concrete instances you can store them in contiguous memory.

---

So, what can you do ?

One solution is to not use polymorphic instances, but instead have data and polymorphism separated:

struct IShape {
    virtual ~IShape() {}
    virtual double area() const = 0;
};

struct Circle {
    float center, radius;
};

struct IShapeCircle: IShape {
    IShapeCircle(Circle const& c): circle(const_cast<Circle&>(c)) {}
    virtual double area() const { return PI * circle.radius * circle.radius; }

    Circle& circle;
};

This way, you only create a polymorphic instance when you need it. And for the storage, we can adapt Massimiliano's solution.

struct IShapeVector {
    virtual ~IShapeVector() {}
    std::unique_ptr<IShape> get(size_t i) = 0;
    std::unique_ptr<IShape const> get(size_t i) const = 0;
};

struct IShapeCircleVector: IShapeVector {
    std::unique_ptr<IShape> get(size_t i) {
        return make_unique<IShapeCircle>(_circles.at(i));
    }
    std::unique_ptr<IShape const> get(size_t i) const {
        return make_unique<IShapeCircle const>(_circles.at(i));
    }

    std::vector<Circle> _circles;
};

However, you might find that the allocation/deallocation traffic slows you down more than the mere v-ptr.

Answer 2

it's not necessary to store the same vtable (8 bytes per object?) collection.size() times;

You're not storing vtables at all. You're storing pointers which are of same size whether the objects are polymorphic or not. If the collection has N objects, then it takes N * sizeof(void*) bytes. So the above statement is false.

it's possible to use contiguous storage locations, since their size are known and equal to each other when their type is defined.

This is not clear. If you're talking about the storage maintained by the container, then yes, the storage maintained by std::vector is guaranteed to be contiguous.

Answer 3

To address point 2 of your question, if you know that all the objects will be of the same type, and you have this information at run-time, you may think of virtualizing the container and create it with a factory. Just to give a sketch of the idea:

class ShapeContainer {
 /* Virtual base */
}; 

class CircleContainer : public ShapeContainer {
/* ... */
private:
    std::vector<Circle> impl_;
}

class ShapeContainerFactory {
 /* Factory for ShapeContainer derived objects */
};

int main() {
    ShapeContainer& collection = ShapeContainerFactory.create("Circle");
    collection.push_back( Circle() );
};

In this case you will be guaranteed to store contiguously not the pointers or references to the polymorphic objects, but the objects themselves.