"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. 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