Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Polymorphism in C++ STL containers

I was wondering if an elegant solution exists to this problem.

Suppose the following:

class Base {
  private:
    int data;
  protected:
    Base(int data) : data(data) { }
    int getData() const { return data; }
    virtual bool someOp() = 0;
}

class Derived1 : public Base {
  private:
    int data2;
  public:
    Derived1(int data, int data2) : Base(data), data2(data2) { }
    int getData2() const { return data2; }
    bool someOp() override { /* something */ }
}

class Derived2 : public Base {
  private:
    float data2;
  public:
    Derived1(int data, float data2) : Base(data), data2(data2) { }
    float getData2() const { return data2; }
    bool someOp() override { /* something */ }
}

And suppose that I have the total control over the hierarchy so I can assume that Base won't get extended, nor any DerivedX class.

Now I want to store them in a std::vector, if I want to use polymorphism I'm forced to store pointers otherwise object slicing will prevent me to store the additional derived properties. So I'm basically forced to use a std::vector<unique_ptr<Base>>.

But let's assume that I need to store plenty of these objects and I don't want to waste for double heap allocation (the internal std::vector + the object itself) and that at the same time I can assume that:

  • the class hierarchy is perfectly defined and won't be extended without knowing it
  • sizeof(DerivedX) won't be so larger than sizeof(Base)

So I'm wondering if there is an elegant way to keep polymorphism and avoid storing pointers. I could think of some solutions like

class Base {
  enum {
   DERIVED1,
   DERIVED2
  } type;

  int data;
  union {
    int derived1data;
    float derived2data;
  }

  bool someOp() {
    if (this->type == DERIVED1) ...
    else if ..
  }
}

But this is clearly not elegant. I could also try to exploit the fact that object slicing shouldn't occur if sizeof(Derived) == sizeof(Base) by using a protected union in Base and accessing it from Derived and casting the address to elements in the std::vector to the desired type (according to an enum) but this sounds ugly too.

like image 891
Jack Avatar asked Mar 03 '15 18:03

Jack


2 Answers

Type erasure and the small buffer optimization.

You can type erase almost any property in C++, creating a custom interface that "knows" how to apply the property to a now-unknown type.

boost::any type erases down to copy, destroy, get typeid, and cast-back-to-exactly-matching-type. std::function type erases down to copy, invoke with a specific signature, destroy, and cast-back-to-identical-type (the last is rarely used).

Free store based type erasure implementations get move semantics 'for free' by swapping around pointers.

In your case, you'll want to create a "large enough" aligned storage in the type. You'll want to type erase down to copy, get-as-reference-to-base, destroy and probably move (as you are storing internally).

std::aligned_storage is intended for your task (you can pass in the alignment requirements of all the types you intend to store). Then in-place new the object.

Build a table of the operations you want to perform on the object via void* -- copy, move, destroy, and convert-to-base*.

template<class Sig>using f = Sig*;

struct table {
  f<base*(void*)>             convert_to_base;
  f<base const*(void const*)> convert_to_const_base;
  f<void(void*,void const*)>  copy_construct;
  f<void(void*)>              destroy;
  f<void(void*,void*)>        move_construct;
};
template<class T>
table const* get_table() {
  static table t = {
    // convert to base:
    [](void*p)->base*{
      T*t=static_cast<T*>(p);
      return t;
    },
    // convert to const base:
    [](void const*p)->base const*{
      T const*t=static_cast<T const*>(p);
      return t;
    },
    // etc
  };
  return &t;
}

now store get_table<T>() in your type-erased instance (it is basically a virtual function table, manually implemented), and write your wrapping regular class to use the functions from the table to manipulate the aligned_storage<?...>.

Now, this can be done easier by using boost::variant, or via something like my some type that acts like a any without using heap storage. The some link includes an implementation that compiles of the pseudo-virtual function table technique above. I probably used aligned storage wrong, however, so be careful.

like image 152
Yakk - Adam Nevraumont Avatar answered Sep 28 '22 07:09

Yakk - Adam Nevraumont


You could use std::aligned_storage to wrap your classes. Assuming that Derived2 is the largest:

class Storage
{
public:
  Storage(int data, int data2)
  {
    new (&data) Derived1(data, data2);
  }
  Storage(int data, float data2)
  {
    new (&data) Derived2(data, data2);
  }
  Base* getBase()
  {
    return reinterpret_cast<Base*>(&data);
  }
  ~Storage()
  {
    getBase()->Base::~Base();
  }
private:
  std::aligned_storage<sizeof(Derived2)> data;
};
like image 45
Nikerboker Avatar answered Sep 28 '22 09:09

Nikerboker