From: François Duranleau (duranlef_at_[hidden])
Date: 2007-08-07 11:37:06
On Tue, 7 Aug 2007, Anthony Williams wrote:
> "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.
>> 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.
I also wonder how he implements iterators without a pointer to the parent.
AFAIK, that is one way to allow stepping from one element to the next (or
the previous) from any node, with no knowledge of how we accessed that
node. Without a parent pointer, aside from using threaded trees (which
would created cycles of shared pointers), I don't know how to do it
efficiently (keeping a stack inside the iterator would make them costly to
copy, and would require O(log N) memory).
Another thing, could this shared_map be implemented in terms of
Boost.Intrusive (IIRC, it has been accepted, though I didn't follow the
review process very much)?
-- FranÃ§ois Duranleau LIGUM, UniversitÃ© de MontrÃ©al
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk