C ++ - map-like data structure with structural separation / immutability

Question

Functional programming languages ​​often work on immutable data structures, but remain effective due to structural separation. For instance. you are working on any information map, if you insert an element, you will not modify the existing map, but create a new updated version. To avoid mass copying and memory usage, the card will share (as much as possible) immutable data between both instances.

I would be wondering if there is any template library providing a map such as a data structure for C ++. I searched a bit and found nothing but inner classes in LLVM.

Answer 1

A Copy on Recording b + tree sounds like you're looking. It basically creates a new snapshot of itself every time it is modified, but it shares unmodified leaf nodes between versions. Most of the implementations that I have seen tend to be baked to add only database log files. CouchDB has a very good record on them. However, they are “relatively lightweight,” as regards map data structures, for implementation.

Answer 2

You can use a regular map, but marking each element with a time stamp or “map version number”. If you want to delete items, use two labels. If you can reinsert deleted items, you will need a list of values ​​and label pairs per item.

For example, you search for the key “foo” and you find that it had a value of 5 in versions 0 to 3 (enabled), then it was “deleted”, and then it had a value of -8 in versions 9 to current.

It is of much use to memory and time.