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

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.