[Boost-users] Re: "smart list" container?

From: David Jones (djones_at_[hidden])
Date: 2004-10-13 11:31:52

"Caleb Epstein" <caleb.epstein_at_[hidden]> wrote in message
news:<989aceac041012063240b6aa3_at_[hidden]>...
> On Mon, 11 Oct 2004 10:19:54 -0600, David M. Jones
<djones_at_[hidden]> wrote:
> > - The container itself would act more or less identically to
std::list;
> > - The iterators on the container would act like boost::weak_ptr in
that they
> > would know that they are invalid when the list element that they
point to is
> > removed.
> 
> Can't you just do this with a std::list<boost::shared_ptr>?  You can
> convert the *iterators to weak_ptrs as needed.  Or am I missing
> something?

There are a couple of reasons that std::list<boost::shared_ptr> is less
than ideal.

First, using the algorithms becomes cumbersome/annoying. Instead of
being able to write
   std::list<boost::shared_ptr<int> > lst;
   // ... Populate the list
   int i;
   // ... Set the value of i
   std::list<boost::shared_ptr<int> >::iterator = std::find(lst.begin(),
lst.end(), i);
I instead need to create a function object to represent a
boost::shared_ptr<int> having the desired value and then use find_if().

Second, I would lose the ability to store iterators and then check them
later for validity. Suppose that I have a
   std::list<boost::shared_ptr<int> >
named lst and I have two std::list<boost::shared_ptr<int> >::iterator
objects it1 and it2 that happen to reference the same node in the list.
If I call
   lst.erase(it1)
then it2 also becomes invalid. If I call
   boost::weak_ptr<int>(*it2)
I get an error because I cannot dereference the iterator because it is
already invalid. This is how std::list objects are supposed to work but
what I want to be able to do is now call something like
   it2.expired()
to determine that the node being refered to by it2 is not
invalid/expired/removed. One way to get around this is to store
boost::weak_ptr objects derived from
std::list<boost::shared_ptr>::iterator objects instead of storing it1
and it2 directly. But then I lose the advantage of having stored
iterators: I cannot (after checking for expiration and being at the end
of the list) call operator++() to move the iterator forward.

Fundamentally, I don't want to be storing a "list of nodes of shared
pointers of objects" but a "list of nodes of objects whose pointers to
each other are shared pointers". And I want the iterators to be weak
pointers to the nodes. Potentially a way to do this would be to write a
custom allocator my_alloc that declares
   typedef boost::shared_ptr pointer;
and then create a
   std::list<T, my_alloc<T> >
This works because std::list uses the allocator rebinding mechanism to
call my_alloc<node<T> > rather than my_alloc<T>. (In fact, my_alloc<T>
is never used to allocate anything in std::list<T>!) However, there is a
problem because the interface (concept a la Austern) of
boost::shared_ptr is different than that of a regular pointer. So when
the std::list code tries to call
   _Myhead = 0;
I get a compiler error. (I am using MSVC 7.1: although this particular
error may be STL implementation dependent, I do believe that the problem
I am describing will occur with any STL implementation.) But I
digress... The question of why the boost::shared_ptr interface/concept
does not conform to that of a normal pointer is probably a topic for a
separate posting.