Object storing a non-owning reference that must be informed before the reference is destructed

Question

I have a class following this pattern:

class Foo
{
public:
    // Create a Foo whose value is absolute
    Foo(int x) : other_(0), a_(x)  {}

    // Create a Foo whose value is relative to another Foo
    Foo(Foo * other, int dx) : other_(other), a_(dx) {}

    // Get the value
    double x() const
    {
        if(other_)
            return other_->x() + a_;
        else
            return a_;
    }

private:
    Foo * other_;
    int a_;
};

The Foo objects are all owned by a Bar:

class Bar
{
public:
    ~Bar() { for(int i=0; i<foos_.size(); i++) delete foos_[i]; }

private:
    vector<Foo*> foos_;
};

Of course, this is a simplified example to get the idea. I have a guarantee that there are no loop of Foos, and that linked Foos all belong to the same instance of Bar. So far, so good. To do things the C++11 way, I would use vector< unique_ptr<Foo> > foos_; in Bar, and pass foos_[i].get() as potential argument of a Foo constructor.

There is the deal:

This a GUI application, and the user can interactively delete some Foo at will. The expected behaviour is that if foo1 is deleted, and foo2 is relative to foo1, then foo2 becomes now "absolute":

void Foo::convertToAbsolute() { a_ += other_->x(); other_ = 0; }

void usageScenario()
{
    Foo * foo1 = new Foo(42);      
    Foo * foo2 = new Foo(foo1, 42);
    // Here, foo1->x() = 42 and foo2->x() = 84

    foo1->setX(10);
    // Here, foo1->x() = 10 and foo2->x() = 52

    delete foo1;
    // Here, foo2->x() = 52
}

I know it is possible to do it using raw pointers, by using a a DAG structure with back-pointers, so the Foo are aware of who "depends on them", and can inform them before deletion (possible solutions detailed here and here ).

My question is: Would you handle it the same way? Is there a way using standard C++11 smart pointers to avoid having the explicit back-pointers, and then avoid explicitely calling areRelativeToMe_[i]->convertToAbsolute(); in the destructor of Foo? I was thinking about weak_ptr, something in the spirit of:

class Foo { /* ... */ weak_ptr<Foo> other_; };

double Foo::x() const
{
    if(other_.isExpired())
        convertToAbsolute();

    // ...
}

But the issue is that convertToAbsolute() needs the relative Foo to still exist. So I need a non-owning smart-pointer that can tell "this reference is logically expired", but actually extends the lifetime of the referenced object, until it is not needed.

It could be seen either like a weak_ptr extending the lifetime until it is not shared with any other weak_ptr:

class Foo { /* ... */ extended_weak_ptr<Foo> other_; };

double Foo::x() const
{
    if(other_.isExpired())
    {
        convertToAbsolute();
        other_.reset(); // now the object is destructed,  unless other
                          // foos still have to release it
    }

    // ...
}

Or like a shared_ptr with different level of ownership:

class Bar { /* ... */ vector< multilevel_shared_ptr<Foo> foos_; };

class Foo { /* ... */ multilevel_shared_ptr<Foo> other_; };

void Bar::createFoos()
{ 
    // Bar owns the Foo* with the highest level of ownership "Level1"

    // Creating an absolute Foo
    foos_.push_back( multilevel_unique_ptr<Foo>(new Foo(42), Level1) );

    // Creating a relative Foo 
    foos_.push_back( multilevel_unique_ptr<Foo>(new Foo(foos_[0],7), Level1) );
}

Foo::Foo(const multilevel_unique_ptr<Foo> & other, int dx) :
    other_( other, Level2 ),
   // Foo owns the Foo* with the lowest level of ownership "Level2"
    a_(dx) 
{
}

double Foo::x() const
{
    if(other_.noLevel1Owner()) // returns true if not shared 
                               // with any Level1 owner
    {
        convertToAbsolute();
        other_.reset(); // now the object is destructed, unless 
                        // shared with other Level2 owners
    }
    // ...
}

Any thoughts?

Answer 1

All Foo are owned by Bar. Therefore all deletions of Foo happen in Bar methods. So I might implement this logic inside Bar:

void Bar::remove(Foo* f)
{
    using namespace std::placeholders;
    assert(std::any_of(begin(foos_), end(foos_),
                       std::bind(std::equal_to<decltype(f)>(), f, _1));

    auto const& children = /* some code which determines which other Foo depend on f */;
    std::for_each(begin(children), end(children),
                  std::mem_fn(&Foo::convertToAbsolute));
    foos_.remove(f);

    delete f; // not needed if using smart ptrs
}

This would ensure that the expiring Foo still exists when convertToAbsolute is called on its dependents.

The choice of how to compute children is up to you. I would probably have each Foo keep track of its own children (cyclic non-owning pointers), but you could also keep track of it inside Bar, or search through foos_ on demand to recompute it when needed.

Answer 2

You can use the double link approach even with more than one other dependent object. You only have to link together the dependents of the same object:

class Foo {
public:
  explicit Foo(double x)
  : v(x), foot(nullptr), next(nullptr), dept(nullptr) {}

  // construct as relative object;  complexity O(1)
  Foo(Foo*f, double x)
  : v(x), foot(f), dept(nullptr)
  { foot->add_dept(this); }

  // destruct;  complexity  O(n_dept) + O(foot->n_dept)
  //                        O(1)  if !destroy_carefully
  ~Foo()
  {
    if(destroy_carefully) {
      for(Foo*p=dept; p;) {
        Foo*n=p->next;
        p->unroot();
        p=n;
      }
      if(foot) foot->remove_dept(this);
    }
  }

  double x() const
  { return foot? foot->x() + v : v; }

private:

  double v;   // my position relative to foot if non-null
  Foo*foot;   // my foot point
  Foo*next;   // next object with same foot point as me
  Foo*dept;   // first object with me as foot point

  // change to un-rooted;  complexity: O(1)
  void unroot()
  { v+=foot->x(); foot=nullptr; next=nullptr; }

  // add d to the linked list of dependents;  complexity O(1)
  void add_dept(const Foo*d)
  { d->next=dept; dept=d; }

  // remove d from the linked list of dependents ; complexity O(n_dept)
  void remove_dept(const Foo*d)
  {
    for(Foo*p=dept; p; p=p->next)
      if(p==d) { p=d->next; break; }
  }
  static bool destroy_carefully;

};
bool Foo::destroy_carefully = true;

Here, setting Foo::destroy_carefully=false allows you to delete all remaining objects without going through the untangling of mutual references (which can be expensive).

Answer 3

Interesting problem. I guess you figured that you can add a pointer to the 'child' object. I am not sure, whether smart pointers help here. I tried to implement the code below using std::weak_ptr<Foo> but you can only use it for other_ and not for the listener.

Another thought I had was to leave the responsibility to some higher power. The problem that you have is that you would like to do the update when the destructor is called. Perhaps better approach would be to call convertToAbsolute() from somewhere else. For example, if you are storing the Foos in a vector and the user clicks delete in the UI, you need the index of the object in order to delete so might as well update the adjacent item to absolute value.

Below is a solution that uses a Foo*.

#include <iostream>
#include <memory>
#include <vector>


class Foo
{
public:
    // Create a Foo whose value is absolute
    Foo(int x) : other_(nullptr), listener_(nullptr), a_(x)
    {}

    // Create a Foo whose value is relative to another Foo
    Foo(Foo* other, int dx) : 
    other_(other), listener_(nullptr), a_(dx) 
    {
        other->setListener(this);
    }

    ~Foo()
    {
        convertToAbsolute();
        if (listener_)
            listener_->other_ = nullptr;
    }

    // Get the value
    double x() const
    {
        if(other_)
            return other_->x() + a_;
        else
            return a_;
    }

    void setX(int i)
    {
        a_ = i;
    }

    void convertToAbsolute()
    {
        if (listener_)
            listener_->a_ += a_;
    }

    void setListener(Foo* listener)
    {
        listener_ = listener;
    }

private:
    Foo* other_;
    Foo* listener_;
    int a_;
};


void printFoos(const std::vector<std::shared_ptr<Foo>>& foos)
{
    std::cout << "Printing foos:\n";
    for(const auto& f : foos)
        std::cout << '\t' << f->x() << '\n';
}

int main(int argc, const char** argv)
{
    std::vector<std::shared_ptr<Foo>> foos;
    try
    {
        auto foo1 = std::make_shared<Foo>(42);
        auto foo2 = std::make_shared<Foo>(foo1.get(), 42);

        foos.emplace_back(foo1);
        foos.emplace_back(foo2);
    }
    catch (std::exception& e)
    {
        std::cerr << e.what() << '\n';
    }

    // Here, foo1->x() = 42 and foo2->x() = 84
    printFoos(foos);

    foos[0]->setX(10);
    // Here, foo1->x() = 10 and foo2->x() = 52
    printFoos(foos);

    foos.erase(foos.begin());
    // Here, foo2->x() = 52
    printFoos(foos);

    return 0;
}

Answer 4

If you have a Signal/Slot framework, that provides a nice place to do the unlinking. For example, using the Qt libraries these classes could look like:

class Foo : public QObject
{
Q_OBJECT
public:
    // Create a Foo whose value is absolute
    Foo(int x) : QObject(nullptr), other_(nullptr), a_(x) {}

    // Create a Foo whose value is relative to another Foo
    Foo(Foo * other, int dx) : QObject(nullptr) other_(other), a_(dx) {
        connect(other, SIGNAL(foo_dying()), this, SLOT(make_absolute()));
    }

    ~Foo() { emit foo_dying(); }

    // Get the value
    double x() const
    {
        if(other_)
            return other_->x() + a_;
        else
            return a_;
    }

signals:
    void foo_dying();

private slots:
    void make_absolute()
    {
        a_ += other_->x();
        other_ = nullptr;
    }

private:
    Foo * other_;
    int a_;
};

Answer 5

Here is probably the simplest way to achieve the goal using back-pointers. You can use the container you want depending on your complexity requirements (e.g., a set, hash table, vector, linked list, etc.). A more involved but more efficient approach is proposed by Walter.

class Foo
{
public:
    // Create a Foo whose value is absolute
    Foo(int x) : other_(0), a_(x)  {}

    // Create a Foo whose value is relative to another Foo
    Foo(Foo * other, int dx) : other_(other), a_(dx)
    {
        other->areRelativeToMe_.insert(this);
    }

    // Get the value
    double x() const
    {
        if(other_)
            return other_->x() + a_;
        else
            return a_;
    }

    // delete the Foo
    Foo::~Foo()
    {
        // Inform the one I depend on, if any, that I'm getting destroyed
        if(other_)
            other_->areRelativeToMe_.remove(this);

        // Inform people that depends on me that I'm getting destructed
        for(int i=0; i<areRelativeToMe_.size(); i++)
            areRelativeToMe_[i]->convertToAbsolute();
    }

private:
    Foo * other_;
    int a_;
    Container<Foo*> areRelativeToMe_; // must provide insert(Foo*) 
                                      //          and remove(Foo*)

    // Convert to absolute
    void convertToAbsolute()
    {
        a_ += other_->x(); 
        other_ = 0; 
    }
};