[boost] Re: live_ptr => live_container / live_iterator

From: Detlef Vollmann (dv_at_[hidden])
Date: 1999-08-16 07:27:54

Andy Glew wrote:
> 
> Now, as I use it, I begin to see the need for
> "live containers" - containers of live_pointers
> that implicitly delete entries that are zero.
Correct me, but this looks like you want to write a
wrapper template around existing containers.

> Again, I ask the list before coding, in case anyone has done the
> like (as it appears folks had with live_ptrs/weak
> references/uncounted pointers).  If nothing else, y'all
> might have advice as to how to code it.
> 
> E.g. a live_map: a map from address to a cached object,
>     that automatically removes entries from the map when
>     they are removed from the cache.  Rather like an auxiliary
>     index to a cache, always kept consistent as objects are removed
>     from the cache.
I've had this type of applications several times.  But it never
occurred to me to use something like a live_container.
Interesting idea.

> "Automatic" removal of pointers to deallocated objects might be
> 
> a) instantaneous: the live_container might be registered
>     the same way a live_pointer is, and have a method called
>     on pointee deallocation
For this you would have a list of references to all live_containers
a pointer lives in inside the pointer.  This looks rather fat
for a pointer.

> b) deferred: the live_container might contain live_pointers.
>     When the live_container is queried, all entries containing 0
>     live pointers would be removed.
> 
>     Typically this would be done inside an iterator:
>             begin(), end(), ++, --, [], etc.
Let's look at an example:

        typedef live_multimap<key_type, object_type> lmm_t;
        lmm_t lmm;
        pair<lmm_t::iterator, lmm_t::iterator> found;
        found = lmm.equal_range(key);
        for ( ; found.first != found.second; ++found.first)
        {
                doSomething(*found.first);
        }

First idea: do everything in the iterator.
        operator++(): this is simple: forward the iterator until
                      the underlying object is a valid one.
                      But what if we end up beyond found.second?
                      How can we know how long we can go forward?

        operator*(): if the current position was reached by ++,
                     this position is a valid one.  But otherwise?

So, it seems that it cannot be done solely in the iterator.
All functions of the container that return iterators must
be re-implemented to ensure that they only return valid
positions (or end()).  But this looks like a lot of work...
But if you do this, then the iterators seem quite simple, you
just have to ensure that the iterator knows about end().

>     As usual, I am lazy, and would prefer not to have to code up all of
>     the iterator access methods - but I don't see anything like
>     "iterator hooks".
I don't see what you mean by "iterator hook"?  I've written quite
a few iterators, iterator adaptors and iterator handles by now,
but I don't find enough commonality among them to factor out
to an "iterator hook".
For your purpose, you might derive your iterator from the
original one and only redefine the moving operations (++, --)
and [].  All you need for this is to define a wrapper class
around plain old pointers, from which you can derive.  But
I'm quite sure that somebody already has done this.

>     Count queries would be problematic: probably the stale objects
>     should be removed from the container first.
> 
>     Overall, the complexity of this deferred implementation probably
>     means that the instantaneous, registered, implementation is cleaner,
>     even though the deferred implementation might be preferrable
>     for performance.
Probably that's true.

Detlef
-- 
Detlef Vollmann
vollmann engineering gmbh           Tel: [phone]
P.O. Box 5106                       Fax: [phone]
CH-6000 Luzern 5 / Switzerland      eMail: dv_at_[hidden]