ps_map is a persistent map from an ordered key PK to a value V. This map is generally well-behaved with respect to cumulative and average performance.
The keys and values are stored in arrays consisting of sorted sub-arrays, with sub-arrays corresponding to the 1-bits in the binary representation of the size.
This results in cumulative memory usage in O(size log² size), worst-case lookup time in O(log² size) and average addition time in O(1) and worst-case addition time in O(size log² size).
WARNING: Due to the high worst-case time for addition, this structure should not be used in situations when adding a single element repeatedly to the same instance of ps_map is performance critical. If the resulting map's size n is a power of 2, this will trigger the worst-case addition time resulting in O(m*n log² n) for adding an element m times.
This constructor is for internal use only, to create instance of ps_map, use ps_map PK V without arguments.
ps_map is a persistent map from an ordered key PK to a value V. This map is
generally well-behaved with respect to cumulative and average performance.
The keys and values are stored in arrays consisting of sorted sub-arrays,
with sub-arrays corresponding to the 1-bits in the binary representation
of the size.
This results in cumulative memory usage in O(size log² size), worst-case
lookup time in O(log² size) and average addition time in O(1) and worst-case
addition time in O(size log² size).
WARNING: Due to the high worst-case time for addition, this structure should
not be used in situations when adding a single element repeatedly to the same
instance of ps_map is performance critical. If the resulting map's size n is a
power of 2, this will trigger the worst-case addition time resulting in
O(m*n log² n) for adding an element m times.
This constructor is for internal use only, to create instance of ps_map, use
ps_map PK V without arguments.