Search structure with history (persistence)

Question

I need a map-like data structure (in C++) for storing pairs (Key,T) with the following functionality:

• You can insert new elements (Key,T) into the current structure
• You can search for elements based on Key in the current structure
• You can make a "snapshot" of the current version of the structure
• You can switch to one of the versions of the structures which you took the snapshot of and continue all operations from there
• Completely remove one of the versions

What I don't need

• Element removal from the structure
• Merging of different versions of the structure into one
• Iteration over all (or some of) elements currently stored in the structure

In other words, you have some search structure that you can build up, but at any point you can jump in history, and expand the earlier/different version of the structure in a different way. Later on you may jump between those different versions.

In my project, Key and T are likely to be integers or pointer values, but not strings.

The primary objective is to reduce the time complexity; space consumption is secondary (but should be reasonable as well). To clarify, for me log(N)+log(S) (where N-number of elements, S-number of snapshots) would be enough, although faster is better :)

I have some rough idea how to implement it --- for example: being the structure a binary search tree, the insertion of a new element can clone the path from the root to the insertion location, while keeping the rest of the tree intact. Switching tree versions would be equivalent to picking a different version of the root node, for which some changes are simply not visible.

However, to make this custom tree efficient (e.g. self-balancing) it will require some additional effort and careful coding. Of course I can do it myself but perhaps there are already existing libraries to do exactly that?

Also, there is probably a proper name for this kind of data structure that I simply don't know, making my Google searches (or SO searches) total failures...

Thank you for your help!

Answer 1

I think what you are looking for is an immutable map. Functional (or functionally inspired) programming languages (such as Haskell or Scala) have immutable versions of most of the containers you'd find in the STL. Operations such as insertion/removal etc. then return a copy of the map (preserving the original) with the copy containing your requested modification. A lot of work has gone into designing the datastructures so that the copies are able to point to as much of the original datastructure as possible to reduce time and memory complexity of each operation.

You can find a lot more details in a book such as this one: http://www.amazon.co.uk/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504.