Boost logo

Boost :

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: +41-41-4120911
P.O. Box 5106                       Fax: +41-41-4120912
CH-6000 Luzern 5 / Switzerland      eMail: dv_at_[hidden]

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk