Re: [boost] Shared Map

From: Anthony Williams (anthony_w.geo_at_[hidden])
Date: 2007-08-07 02:43:40

"Jeremy Bruestle" <jeremy.bruestle_at_[hidden]> writes:

> I've recently implemented a new collection type for a project of mine.
>  It works identically to std::map, with the same algorithmic
> guarantees, but additionally can be 'copied' in constant time.  That
> is:
>
> shared_map<int, int> a;
> for(i = 0; i < 100; i++)
>    a[i] = i*i;   // Each insert in log(n) of the map size
> shared_map<int, int> b = a;   // This is constant time (not linear as
> in a std::map)
> b[1] = 7;  // Still log(n) of course
> b[2] = 3;
>
> assert(a[2] == 4 && b[2] == 3 && a[6] == 36 && b[6] == 36);
>
> The trick is simple: the map is a red-black tree, but we get rid of
> the explicit parent pointer for each red-black node.  This complicates
> the code, but is algorithmically uninteresting since we always descend
> from the root anyway and just need to track the parent as we go,
> either in an explicit stack or through recursion (my current
> implementation).  The key point however is that the lack of an
> explicit parent allows us to use reference counting, and share
> children.  Thus the copy from a to b simply copies the root node, and
> adds an additional reference count.  All future changes do copy on
> write for shared nodes (any with a ref count of 2 or more).

How does this work with iterators? On a normal map you can get an iterator to
an entry and it remains valid until that entry is deleted. Can you do this
with your shared map? I'm inclined to think that any modification to the map
would have to result in all iterators being invalidated, as they may now
potentially refer to the wrong copy of a node.

Anthony
-- 
Anthony Williams
Just Software Solutions Ltd - http://www.justsoftwaresolutions.co.uk
Registered in England, Company Number 5478976.
Registered Office: 15 Carrallack Mews, St Just, Cornwall, TR19 7UL