Can I Have Polymorphic Containers With Value Semantics in C++0x?

Question

This is a sequel to a related post which asked the eternal question:

Can I have polymorphic containers with value semantics in C++?

The question was asked slightly incorrectly. It should have been more like:

Can I have STL containers of a base type stored by-value in which the elements exhibit polymorphic behavior?

If you are asking the question in terms of C++, the answer is "no." At some point, you will slice objects stored by-value.

Now I ask the question again, but strictly in terms of C++0x. With the changes to the language and the standard libraries, is it now possible to store polymorphic objects by value in an STL container?

I'm well aware of the possibility of storing a smart pointer to the base class in the container -- this is not what I'm looking for, as I'm trying to construct objects on the stack without using new.

Consider if you will (from the linked post) as basic C++ example:

#include <iostream>

using namespace std;

class Parent
{
    public:
        Parent() : parent_mem(1) {}
        virtual void write() { cout << "Parent: " << parent_mem << endl; }
        int parent_mem;
};

class Child : public Parent
{
    public:
        Child() : child_mem(2) { parent_mem = 2; }
        void write() { cout << "Child: " << parent_mem << ", " << child_mem << endl; }

        int child_mem;
};

int main(int, char**)
{
    // I can have a polymorphic container with pointer semantics
    vector<Parent*> pointerVec;

    pointerVec.push_back(new Parent());
    pointerVec.push_back(new Child());

    pointerVec[0]->write();     
    pointerVec[1]->write();     

    // Output:
    //
    // Parent: 1
    // Child: 2, 2

    // But I can't do it with value semantics

    vector<Parent> valueVec;

    valueVec.push_back(Parent());
    valueVec.push_back(Child());        // gets turned into a Parent object :(

    valueVec[0].write();        
    valueVec[1].write();        

    // Output:
    // 
    // Parent: 1
    // Parent: 2

}

Answer 1

You certainly can't have a polymorphic array (or vector). The requirement that the elements of an array be stored contiguously in memory is fundamentally incompatible with the fact that different derived class types may have different sizes.

None of the standard library containers allow for storing objects of different derived class types in a single container.

Answer 2

Just for fun, based on James's comment about a template-based system, I came up with this Vector-like implementation. It's missing lots of features, and may be buggy, but it's a start!

#include <iostream>
#include <vector>
#include <boost/shared_ptr.hpp>

template <typename T>
class Vector
{
public:
    T &operator[] (int i) const { return p[i]->get(); }
    template <typename D>
    void push_back(D &x) { p.push_back(ptr_t(new DerivedNode<D>(x))); }

private:
    class Node
    {
    public:
        virtual T &get() = 0;
    };

    template <typename D>
    class DerivedNode : public Node
    {
    public:
        DerivedNode(D &x) : x(x) {}
        virtual D &get() { return x; }
    private:
        D x;
    };

    typedef boost::shared_ptr<Node> ptr_t;
    std::vector<ptr_t> p;
};

///////////////////////////////////////

class Parent
{
    public:
        Parent() : parent_mem(1) {}
        virtual void write() const { std::cout << "Parent: " << parent_mem << std::endl; }
        int parent_mem;
};

class Child : public Parent
{
    public:
        Child() : child_mem(2) { parent_mem = 2; }
        void write() const { std::cout << "Child: " << parent_mem << ", " << child_mem << std::endl; }

        int child_mem;
};


int main()
{
    Vector<Parent> v;

    v.push_back(Parent());
    v.push_back(Child());

    v[0].write();
    v[1].write();
}

Answer 3

First of all, your requirements are still not perfectly clear. I will assume that you want "inline storage" for the container; so, for example, in a "polymorphic" vector, all elements would be adjacent in memory (with only padding in between as needed for correct alignment).

Now, it is possible if you're willing to provide an exhaustive list of all types that you're going to put into the container at compile-time. The most straightforward implementation would be to use a union of all possible types as the type of the backing array - that would ensure enough size and proper alignment, and same O(1) access by index, at the cost of some wasted space on elements of smaller-size types. I can go into this with more detail if you want.

If the list of types is now known in advance, or if you do not want that kind of overhead, then you'd have to maintain a separate index of pointers (or offsets from the beginning of the backing store) to elements, so that you can do O(1) access. Also, given the alignment issues, I'm not sure if you could even do that in fully portable C++03, though you definitely can in C++0x.