Search structure with history (persistence)

Question

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

• You can insert new elements (Key, T) into the current structure
• You can search for items based on the key in the current structure
• You can take a snapshot of the current version of the structure.
• You can switch to one of the versions of the structures that you took the picture and continue all operations there
• Uninstall one version completely

What i don't need

• Removing Elements from a Structure
• Combining different versions of the structure into one
• Iterate over all (or some) of the elements that are currently stored in the structure

In other words, you have a search structure that you can create, but at any time you can go to history and deploy an earlier / different version of the structure in a different way. You can later jump between these different versions.

In my project, Key and T can be integer or pointer values, but not strings.

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

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

However, to make this custom tree efficient (such as self-balancing), additional effort and careful coding are required. Of course, I can do it myself, but maybe there are already existing libraries to do just that?

Also, there is probably the right name for a data structure that I just don’t know, as a result of which my search queries (or SO search queries) are completely distorted ...

Thank you for your help!

Answer 1

I think you are looking for an immutable map. Functional (or functionally inspired) programming languages ​​(such as Haskell or Scala) have unchanged versions of most containers that you will find in the STL. Operations such as insertion / deletion, etc., then return a copy of the card (keeping the original) with a copy containing the requested modification. Much work has been devoted to designing data structures so that copies can point to as much of the original data structure as possible in order to reduce the time and memory complexity for each operation.

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

Answer 2

While searching for some persistent search tree libraries, I came across this:

http://cg.scs.carleton.ca/~dana/pbst/

Despite not having the same functionality as required, it seems pretty close to it. I will explore.

(posting here as someone might also find it useful)