QList of a polymorphic class with copy-on-write?

Question

I am trying to create a QList of a polymorphic type that still uses Qt's implicit sharing.

My specific use case is passing items held in a QList to QtConcurrent::mapped. The items all descend from a base class which defines a virtual function that QtConcurrent::mapped will call. The majority of the stored data will be child class specific. These items may be edited after the threading begins, leaving me with two main options, locks or copy the data. I do not want to stick locks in, because that would eliminate most of the purpose of using extra threads. Also making full copies of my data also seems quite undesirable. Instead I would like use Qt's implicit sharing to only make copies of the data items that I change, however I can't seem to make a QList of a polymorphic type that still uses implicit sharing.

QList by default uses implicit sharing, so at first glance it would seem that we are already done.

QList<Base> list;
Derived derived_obj;
list.append(derived_obj); // this fails

However appending a child class to a QList of the parent class will not work and the standard answer is to instead use a QList of QSharedPointers to the base class, which will accept appending a pointer to the child class.

QList<QSharedPointer<Base> > pointer_list;
QSharedPointer<Derived> derived_pointer;
pointer_list.append(derived_pointer); // this works but there is no copy-on-write

If I use a QList of QSharedPointers, it is the QSharedPointer that will be be copied rather than my polymorphic class, meaning that I have lost the copy-on-write functionality that I would like.

I have also looked at using a QList of QSharedDataPointers.

QList<QSharedDataPointer<Base> > data_pointer_list;
QSharedDataPointer<Derived> derived_data_pointer;
list.append(derived_data_pointer); // this fails

However like QList itself, QSharedDataPointers do not seem to accept polymorphic types.

Answer 1

This fails:

QList<QSharedDataPointer<Base>> list;
QSharedDataPointer<Derived> derived(new Derived);
list.append(derived);

Note An alternative approach to the below would be to merge the PolymorphicShared and PolymorphicSharedBase to add polymorphism support directly to QSharedDataPointer, without placing special requirements on the QSharedData-derived type (e.g. it wouldn't need to explicitly support clone). This requires a bit more work. The below is just one working approach.

QSharedDataPointer is indeed the answer you seek and can definitely hold polymorphic QSharedData. You need to separate the type into a hierarchy based on QSharedData, and another parallel hierarchy wrapping the QSharedDataPointer. The QSharedDataPointer is not usually meant to be used directly by the end user of a class. It's an implementation detail useful in implementing an implicitly shared class.

For efficiency's sake, a QSharedDataPointer is a small type that can be moved at the bit level. It's quite efficient when stored in containers of all sorts - especially in Qt containers that can utilize the type traits to be aware of this property. The size of a class using a QSharedDataPointer will usually double if we make it polymorphic itself, thus it helps not to do it. The pointed-to data type can be polymorphic, of course.

First, let's define a rather univeral base class PIMPL that you'll build the hierarchy on. The PIMPL class can be dumped into the debug stream, and cloned.

// https://github.com/KubaO/stackoverflown/tree/master/questions/implicit-list-44593216
#include <QtCore>
#include <type_traits>

class PolymorphicSharedData : public QSharedData {
public:
   virtual PolymorphicSharedData * clone() const = 0;
   virtual QDebug dump(QDebug) const = 0;
   virtual ~PolymorphicSharedData() {}
};

The xxxData types are PIMPLs and are not meant for use by the end-user. The user is meant to use the xxx type itself. This shared type then wraps the polymorphic PIMPL and uses the QSharedDataPointer for storage of the PIMPL. It exposes the methods of the PIMPL.

The type itself is not polymorphic, to save on the size of the virtual table pointer. The as() function acts as dynamic_cast() would, by redirecting polymorphism to the PIMPL.

class PolymorphicShared {
protected:
   QSharedDataPointer<PolymorphicSharedData> d_ptr;
   PolymorphicShared(PolymorphicSharedData * d) : d_ptr(d) {}
public:
   PolymorphicShared() = default;
   PolymorphicShared(const PolymorphicShared & o) = default;
   PolymorphicShared & operator=(const PolymorphicShared &) = default;
   QDebug dump(QDebug dbg) const { return d_ptr->dump(dbg); }
   template <class T> typename
   std::enable_if<std::is_pointer<T>::value, typename
   std::enable_if<!std::is_const<typename std::remove_pointer<T>::type>::value, T>::type>
   ::type as() {
      if (dynamic_cast<typename std::remove_pointer<T>::type::PIMPL*>(d_ptr.data()))
         return static_cast<T>(this);
      return {};
   }
   template <class T> typename
   std::enable_if<std::is_pointer<T>::value, typename
   std::enable_if<std::is_const<typename std::remove_pointer<T>::type>::value, T>::type>
   ::type as() const {
      if (dynamic_cast<const typename std::remove_pointer<T>::type::PIMPL*>(d_ptr.data()))
         return static_cast<T>(this);
      return {};
   }
   template <class T> typename
   std::enable_if<std::is_reference<T>::value, typename
   std::enable_if<!std::is_const<typename std::remove_reference<T>::type>::value, T>::type>
   ::type as() {
      Q_UNUSED(dynamic_cast<typename std::remove_reference<T>::type::PIMPL&>(*d_ptr));
      return static_cast<T>(*this);
   }
   template <class T> typename
   std::enable_if<std::is_reference<T>::value, typename
   std::enable_if<std::is_const<typename std::remove_reference<T>::type>::value, T>::type>
   ::type as() const {
      Q_UNUSED(dynamic_cast<const typename std::remove_reference<T>::type::PIMPL&>(*d_ptr));
      return static_cast<T>(*this);
   }
   int ref() const { return d_ptr ? d_ptr->ref.load() : 0; }
};

QDebug operator<<(QDebug dbg, const PolymorphicShared & val) {
   return val.dump(dbg);
}

Q_DECLARE_TYPEINFO(PolymorphicShared, Q_MOVABLE_TYPE);

#define DECLARE_TYPEINFO(concreteType) Q_DECLARE_TYPEINFO(concreteType, Q_MOVABLE_TYPE)

template <> PolymorphicSharedData * QSharedDataPointer<PolymorphicSharedData>::clone() {
   return d->clone();
}

A helper to makes it easy to use the abstract base class with derived data types. It casts the d-ptr to a proper derived PIMPL type, and forwards the constructor arguments to the PIMPL's constructor.

template <class Data, class Base = PolymorphicShared> class PolymorphicSharedBase : public Base {
   friend class PolymorphicShared;
protected:
   using PIMPL = typename std::enable_if<std::is_base_of<PolymorphicSharedData, Data>::value, Data>::type;
   PIMPL * d() { return static_cast<PIMPL*>(&*this->d_ptr); }
   const PIMPL * d() const { return static_cast<const PIMPL*>(&*this->d_ptr); }
   PolymorphicSharedBase(PolymorphicSharedData * d) : Base(d) {}
   template <typename T> static typename std::enable_if<std::is_constructible<T>::value, T*>::type
   construct() { return new T(); }
   template <typename T> static typename std::enable_if<!std::is_constructible<T>::value, T*>::type
   construct() { return nullptr; }
public:
   using Base::Base;
   template<typename ...Args,
            typename = typename std::enable_if<std::is_constructible<Data, Args...>::value>::type
            > PolymorphicSharedBase(Args&&... args) :
      Base(static_cast<PolymorphicSharedData*>(new Data(std::forward<Args>(args)...))) {}
   PolymorphicSharedBase() : Base(construct<Data>()) {}
};

It's now a simple matter to have the parallel hierarchy of PIMPL types and their carriers. First, a basic abstract type in our hierarchy that adds two methods. Note how PolymorphicSharedBase adds the d() accessor of the correct type.

class MyAbstractTypeData : public PolymorphicSharedData {
public:
   virtual void gurgle() = 0;
   virtual int gargle() const = 0;
};

class MyAbstractType : public PolymorphicSharedBase<MyAbstractTypeData> {
public:
   using PolymorphicSharedBase::PolymorphicSharedBase;
   void gurgle() { d()->gurgle(); }
   int gargle() const { return d()->gargle(); }
};
DECLARE_TYPEINFO(MyAbstractType);

Then, a concrete type that adds no new methods:

class FooTypeData : public MyAbstractTypeData {
protected:
   int m_foo = 0;
public:
   FooTypeData() = default;
   FooTypeData(int data) : m_foo(data) {}
   void gurgle() override { m_foo++; }
   int gargle() const override { return m_foo; }
   MyAbstractTypeData * clone() const override { return new FooTypeData(*this); }
   QDebug dump(QDebug dbg) const override {
      return dbg << "FooType-" << ref << ":" << m_foo;
   }
};

using FooType = PolymorphicSharedBase<FooTypeData, MyAbstractType>;
DECLARE_TYPEINFO(FooType);

And another type that adds methods.

class BarTypeData : public FooTypeData {
protected:
   int m_bar = 0;
public:
   BarTypeData() = default;
   BarTypeData(int data) : m_bar(data) {}
   MyAbstractTypeData * clone() const override { return new BarTypeData(*this); }
   QDebug dump(QDebug dbg) const override {
      return dbg << "BarType-" << ref << ":" << m_foo << "," << m_bar;
   }
   virtual void murgle() { m_bar++; }
};

class BarType : public PolymorphicSharedBase<BarTypeData, FooType> {
public:
   using PolymorphicSharedBase::PolymorphicSharedBase;
   void murgle() { d()->murgle(); }
};
DECLARE_TYPEINFO(BarType);

We'll want to verify that the as() method throws as needed:

template <typename F> bool is_bad_cast(F && fun) {
   try { fun(); } catch (std::bad_cast) { return true; }
   return false;
}

The use of the implicitly shared types is no different than the use of Qt's own such types. We can also cast using as instead of dynamic_cast.

int main() {
   Q_ASSERT(sizeof(FooType) == sizeof(void*));
   MyAbstractType a;
   Q_ASSERT(!a.as<FooType*>());
   FooType foo;
   Q_ASSERT(foo.as<FooType*>());
   a = foo;
   Q_ASSERT(a.ref() == 2);
   Q_ASSERT(a.as<const FooType*>());
   Q_ASSERT(a.ref() == 2);
   Q_ASSERT(a.as<FooType*>());
   Q_ASSERT(a.ref() == 1);
   MyAbstractType a2(foo);
   Q_ASSERT(a2.ref() == 2);

   QList<MyAbstractType> list1{FooType(3), BarType(8)};
   auto list2 = list1;
   qDebug() << "After copy:         " << list1 << list2;
   list2.detach();
   qDebug() << "After detach:       " << list1 << list2;
   list1[0].gurgle();
   qDebug() << "After list1[0] mod: " << list1 << list2;

   Q_ASSERT(list2[1].as<BarType*>());
   list2[1].as<BarType&>().murgle();
   qDebug() << "After list2[1] mod: " << list1 << list2;

   Q_ASSERT(!list2[0].as<BarType*>());
   Q_ASSERT(is_bad_cast([&]{ list2[0].as<BarType&>(); }));

   auto const list3 = list1;
   Q_ASSERT(!list3[0].as<const BarType*>());
   Q_ASSERT(is_bad_cast([&]{ list3[0].as<const BarType&>(); }));
}

Output:

After copy:          (FooType-1:3, BarType-1:0,8) (FooType-1:3, BarType-1:0,8)
After detach:        (FooType-2:3, BarType-2:0,8) (FooType-2:3, BarType-2:0,8)
After list1[0] mod:  (FooType-1:4, BarType-2:0,8) (FooType-1:3, BarType-2:0,8)
After list2[1] mod:  (FooType-1:4, BarType-1:0,8) (FooType-1:3, BarType-1:0,9)

The list copy was shallow and the items themselves weren't copied: the reference counts are all 1. After the detach, all data items were copied but because they are implicitly shared, they only incremented their reference counts. Finally, after an item is was modified, it is automatically detached, and the reference counts drop back to 1.