Which type of pointer to use to implement shared access to elements of a set?

Question

In order to make the discussion clear, I'm going to describe the problem in a very general manner, i.e. I will neither provide names of real classes nor will I describe the domain/context (however, I might if it turns out to be urgent).

Imagine class A. Let this class have 2 immutable fields, for instance x and y (please, notice, that these could be potentially big objects, i.e. inefficient to copy). Additionally, let these x and y be primary fields, i.e. only they are used in the implementation of ==/!= operators as well as hash-computing function.

Since A is immutable in terms of x and y, the idea is to let multiple instances of A (say a1 and a2) which have a1.x == a2.x a1.y == a2.y (i.e. a1 == a2) to implicitly have shared access to those x and y, so that there is no unnecessary duplication.

Moreover, now imagine that there is another field in A: z, which is secondary and mutable, and serves as a sort of behavior tweak for A. By design, it is desired to make this field shared among equal instances of A too. So, if I invoke a1.setZ(...) this change will also affect a2 because their access to z is shared.

As a result, we end up with a class A which has pure value semantics, but shares its members implicitly across equal instances. AFAIK such pattern is called Flyweight or aliasing.

One more detail before we move to the question. Most classes in the project are implemented using Pimpl idiom:

private:
  class Private;

  Private* p;

and class A is not an exclusion. That's why the proposed idea of implementing the scheme described above is as follows.

1. Use shared pointer to A::Private instead of raw one in Pimpl idiom;
2. Have global set of shared pointers to A::Private;
3. In constructor of A to check whether a shared pointer to suitable A::Private already exists in the set (utilizing x and y of course), and if yes, then simply set p to it, otherwise create new instance of A::Private and store shared pointer to it in this set, and similarly set p to it;
4. A::Private's destructor should remove shared pointer to this from the set.

This looks like the most straightforward and intuitive implementation. However, the problem is that since this global set holds a shared pointer to A::Private, it means that even when all instances of corresponding A are destroyed, the reference counter will stay on 1, i.e. it will never reach 0, and thus the memory is never freed.

I thought it would be good if some shared pointers would offer a method to set lower bound for the reference counter. In this case, for example, I would simply set it to 1 which would mean that when it reaches 1 it frees the memory. Unfortunately, I haven't found any implementation of such behavior in popular libraries (Boost, Qt, Poco, etc.). Of course, I could do manual reference counting for my problem, but that just doesn't feel right and smells like reinventing the wheel.

Probably, there are other ways to solve this problem. Looking forward for your suggestions.

NOTE: I would like to immediately intercept any advising to transform the problem to pointer semantics which I am well aware of. I need the solution exactly for the scheme described above.

Answer 1

If I understood correctly what your design issue is, then I would let the global set contain weak, non-owning pointers (e.g. weak_ptr<>) which are able to check if they are dangling, yet they do not increase the reference count.

std::vector<std::weak_ptr<Private>> _objects;

Therefore, when all owning shared pointers to an object are destroyed, the object will be destroyed as well**.

Now your global set will be left with a dangling weak_ptr<>, but the nice thing is that you can check whether that pointer points to an object which is alive or not (use the lock() member function to obtain a possibly null shared_ptr<>. And if it doesn't, you won't dereference it:

// A simple, hypothetical loop through the collection of objects
// which does something, but checks whether the pointers are
// dangling before doing that something on a possibly dead object
// that would be Undefined Behavior)
std::for_each(_objects.begin(), _objecs.end(), [] (std::weak_ptr<Private> p) 
{
    std::shared_ptr<Private> sp = p.lock();
    if (sp != nullptr)
    {
        sp->callMember(); // For instance...
    }
});

If you also want to remove the corresponding weak_ptr<> to an object from the collection once the object gets destroyed, then you could use a custom deleter routine. Your routine will be invoked when the object is destroyed and will be passed the pointer to that object: at this point, before deallocating, you can erase the corresponding element from the set.

For example, a function that instantiates new objects of type A and returns a shared_ptr to it could look this way:

static std::shared_ptr<object> make_A()
{
    std::shared_ptr<Private> sp(
        new Private(),   // Instantiate the object
        [] (Private* p)  // Set up the custom deleter...
        {
            // Remove the corresponding element from the vector...
            _objects.erase(
                // ...so let's find that element!
                std::find_if( 
                    _objects.begin(),
                    _objects.end(),
                    [p] (std::weak_ptr<priv> wp)
                    {
                        // lock() will return a null pointer if wp is dangling
                        std::shared_ptr<priv> sp = wp.lock();

                        // In case wp is not dangling, return true if and only
                        // if it points to the object we're about to delete
                        return ((sp != nullptr) && (sp.get() == p));
                    })
                );
        });
}

Here I assumed C++11, you could easily do the same in C++03 by replacing std::shared_ptr<> with boost::shared_ptr<>, std::weak_ptr<> with boost::weak_ptr<>, and lambdas with properly-defined functors.

Hope this helps.