On Tue, 7 Aug 2007, Anthony Williams wrote:
"Jeremy Bruestle" <jeremy.bruestle@gmail.com> 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. [snip] 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