An object that stores a link that is not related to the owner, which must be informed before the link is destroyed

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_; }; 

All Foo objects are owned by 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 an idea. I have a guarantee that there is no loop from Foo s, and that the linked Foo all belongs to one instance of Bar . So far, so good. To do something in C ++ 11, I would use vector< unique_ptr<Foo> > foos_; to Bar and passed foos_[i].get() as a potential argument to the Foo constructor.

There is a deal:

This is a GUI application, and the user can interactively remove some Foo as desired. The expected behavior is that if foo1 is deleted, and foo2 refers to foo1 , then foo2 is 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 that this can be done using source pointers, using the aa DAG structure with back pointers, so Foo knows who “depends on them” and can report it before deleting (possible solutions are described in detail here and here ).

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

 class Foo { /* ... */ weak_ptr<Foo> other_; }; double Foo::x() const { if(other_.isExpired()) convertToAbsolute(); // ... } 

But the problem is that convertToAbsolute() needs a relative Foo that still exists. Therefore, I need a non-owning smart pointer that can say that "this link has logically expired", but actually extends the life of the object it refers to until it is needed.

This can be seen either as weak_ptr , which extends the lifetime, until it is shared with another 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 a 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 owned by Bar . Therefore, all Foo deletes occur in Bar methods. Therefore, I could 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 ensures that the expiring Foo still exists when convertToAbsolute is called on its dependents.

The choice of method for calculating children up to you. I will probably have each Foo keep track of its own children (non-owner cyclic pointers), but you can also track it inside Bar or search for foos_ on demand to double-check it when necessary.

Answer 2

You can use the double link method even with several other dependent objects. You only need to link 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 other objects without having to unravel reciprocal links (which can be expensive).

Answer 3

An interesting problem. I think you understand that you can add a pointer to a "child" object. I'm not sure if smart pointers help. I tried to implement the code below using std::weak_ptr<Foo> , but you can only use it for other_ , not for the listener.

Another thought I had was to leave responsibility for a higher power. The problem is that you want to make an update when the destructor is called. Perhaps the best approach is to call convertToAbsolute() from another place. For example, if you save Foos in a vector and the user clicks on delete in the user interface, you need the index of the object to delete it, so it can also update the adjacent element to an absolute value.

Below is a solution that uses 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 good place to disconnect. For example, using the Qt libraries, these classes may look like this:

 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 perhaps the easiest way to achieve your goal with the help of reverse pointers. You can use the necessary container depending on complexity requirements (e.g. set, hash table, vector, linked list, etc.). A more attractive but more effective approach suggested 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; } };