Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)

From: Peter Dimov (pdimov_at_[hidden])
Date: 2003-05-29 09:59:31

Chuck Messenger wrote:
> Schoenborn, Oliver wrote:
>
> Imagine that I'm supplying a network simulation library.  I have:
>
>      #include <iostream>
>      #include <set>
>      #include <boost/utility.hpp>
>      #include <boost/shared_ptr.hpp>
>
>      using namespace std;
>      using namespace boost;
>
>      struct Node;
>
>      struct NodeImpl : noncopyable {
>          NodeImpl(int id) : id_(id) { cout << id_ << " lives\n"; }
>          ~NodeImpl() { cout << id_ << " dies\n"; }
>      private:
>          set<Node> nodes_;
>          int id_;
>          friend struct Node;
>      };
>
>      struct Node {
>          Node(int id) : pimpl_(new NodeImpl(id)) { }
>          Node(const Node& n) : pimpl_(n.pimpl_) { }
>          void Connect(const Node& n) { pimpl_->nodes_.insert(n); }
>          void Disconnect(const Node& n) { pimpl_->nodes_.erase(n); }
>      private:
>          shared_ptr<NodeImpl> pimpl_;
>          friend bool operator<(const Node& n1, const Node& n2);
>      };
>
>      bool operator<(const Node& n1, const Node& n2) {
>          return n1.pimpl_ < n2.pimpl_;
>      }
>
>      int main() {
>          {
>              Node n1(1);
>
>              {
>                  Node n2(2), n3(3), n4(4);
>
>                  n1.Connect(n2);
>                  n2.Connect(n2);
>                  n3.Connect(n3);
>                  n4.Connect(n4);
>              }
>
>              cout << "n1 points to the cluster {n2, n3, n4}\n";
>          }
>
>          cout << "n2, n3, n4 remain alive.  That sucks.\n";
>      }

This is a graph. The classic "tree structure" combined with reference
counting can only represent (possibly multiply linked) DAGs, but not general
graphs.

One possible representation of a general graph is a vertex pool and a
separate edge pool. This avoids the ownership issues inherent in the tree
representation since now nodes don't own each other, the two pools are the
owners.

Perhaps the boost graph library can help here?