Confluent Sets and Maps

Confluent sets and maps are sorted associative containers written in C++11.
Containers can be merged at optimal cost in time and memory both when one of the input containers is small and when the symmetric difference is small.
Sets of the same type share equal nodes. Maps share key nodes with sets of compaitble type and value nodes with other maps of the same type.
Inserted elements must be comparable, hashable and copyconstructible.
You find the current source code on github.
You find the current API documentation and code examples here.
The used merge algorithms are documented here.
(1) Constructing the sets A and B from ranges is O(n) if input is sorted, otherwise O(n*log n).
(2) Constructing the set C as a copy of another set is constant in time and memory.
(3) Constructing the sets D, E, F and G by merging two sets is O(v*log(u/v)).
(4) Constructing the set H as a slice of another set is O(log(n)).
(5) Inserting or erasing individual keys is O(log n).
(6) Testing if two sets contain the same elements or accessing the combined hash value of all elements in a set is contant in time.
(7) Iterating all elements in a set is O(n) amortized time.
(1) Constructing the maps A and B from ranges is O(n) if input is sorted, otherwise O(n*log n).
(2) Constructing the map C as a copy of another map is constant in time and memory.
(3) Constructing the map D containing the keys in a map is constant in time and memory.
(4) Constructing the maps E, F and G by merging two maps is O(v*log(u/v)).
(5) Constructing the maps H and I by merging a map and a set is is O(w*log(u/w)).
(6) Constructing the map J as a slice of another map is O(log(n)).
(7) Inserting or erasing individual keys or values is O(log n).
(8) Testing if two maps contain the same elements or accessing the combined hash value of all elements in a map is contant in time.
(9) Iterating all elements in a map is O(n) amortized time.
Confluent sets and maps are powerful alternatives to the standard counterparts in applications that work with many containers of the same type, in particular when containers of different size and/or containing overlapping content have to be merged.
Confluent sets and maps are backed by immutable trees and keeping copies of previous versions when containers are modified adds no extra cost in time.
Confluent sets and maps can be copied, hashed and tested for equality in constant time and can therefore be used as key types in generic hash tables such as std::unordered_set and std::unordered_map.
Confluent maps can be used to implement efficient threewaymerge of dictionaries based on simple set operations, eleminating the need for complicated code and suplementary structures often used to keep track of changes.
A threewaymerge is an operation that merges the changes in two braches created from a common ancestor, like push and pull operations in git.
Provided a common ancestor A and two branches B and C, if the branches contain no conflicts, the following function will produce a new container that applies the changes in both branches:
Let n be the total number of elements and let m be the number of changes in the branches.
The cost of the merge is O(m*log(n/m)), which is optimal for a sorted index structure.
The merge can easily be extended to also handle conflicts, which is demonstrated with complete code in the example program PhoneNumbers.cc.