Re: If GC is the solution, then what is the problem?
Andrei Alexandrescu (See Website For Email) wrote:
struct Node;
typedef SmartPtr<Node, SomePolicies> NodePtr;
struct Node {
// add to this node's right
virtual void AddToRight(NodePtr rhs) {
// just defer to the right-hand side
rhs->AddToLeft(this); // oopsies
}
virtual void AddToLeft(NodePtr lhs) {
prev_ = lhs;
}
...
private:
NodePtr prev_;
};
As the Node class knows its own methods it knows that AddToLeft takes
NodePtr not Node*. Why would any sensible programmer make this error?
Once the class knows about the use of a smart pointer of its own type,
you may as well use an intrusive type. Here this could be a
reference-link, but obviously the problem is that you'll get circular
references.
The sensible way then to handle a linked-list is to use raw-pointers
and to make all the nodes the ownership of the list that contains them.
(Similarly a tree structure). It makes sense because the user does not
call delete on the node, but instructs the container to erase the node.
The node class is also abstract to the user of the collection, the
implementation can use placement-new to allocate ahead a number of
nodes, and the collection user is responsible only for any pointers
that contain data supplied by the user.
I'm pretty certain that most STL implementations work something like
that anyway, no smart-pointers, no garbage collectors either.
struct Node {
// add to this node's right
static void AddToRight(NodePtr myself, NodePtr rhs) {
myself->AddToRightImpl(myself, rhs); // yuck
}
virtual void AddToLeft(NodePtr lhs) {
prev_ = lhs; // whew
}
private:
virtual void AddToRightImpl(NodePtr myself, NodePtr rhs) {
// just defer to the right-hand side
assert(myself == this); //yuck
rhs->AddToLeft(myself);
}
...
private:
NodePtr prev_;
};
This can work sometimes but once again, why not just use an intrusive
smart-pointer then? It inherits from some reference-counted base class
and can happily pass itself to other classes which can increase the
reference count because with an intrusive smart-pointer, the object
itself holds its reference count. Intrusive smart-pointers are useful
sometimes. Once the class knows about the existence of smart-pointers
to its own type in its interface it becomes intrusive anyway to some
degree. Although with my comments above, even intrusive is probably
wrong here.
{
NodePtr leftNode, rightNode;
Node::AddToRight(leftNode, rightNode);
} // alive, but not glorious
This whole problem would simply not exist in a GC system.
Nor would it if you applied the ownership to the right place, i.e. the
collection and not the individual nodes. Handing ownership to a 3rd
party garbage collector can work, but what is the big difference
between doing that and handing it to its real owner, who at least knows
what to do when the time comes?
Would garbage collection prevent iterators to a vector becoming
invalidated if the vector grows? No, I don't think so. Not if pointers
remain what they are now - a POD type referring to a location in memory
on which you can perform pointer arithmetic and pointer-arithmetic can
be fast because there is no spy watching over how many pointers you
have pointing to things.
What about pointing to the element one past the end of the collection?
How are you going to do that with strongly-typed gc? Allocate a dummy
element there anyway just because?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]