...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Since element containers std::set
and icl::map
are only
extensions of stl::set and stl::map, their complexity characteristics are
accordingly. So their major operations insertion (addition), deletion and
search are all using logarithmic time.
The operations on interval containers behave differently due to the fact that intervals unlike elements can overlap any number of other intervals in a container. As long as intervals are relatively small or just singleton, interval containers behave like containers of elements. For large intervals however time consumption of operations on interval containers may be worse, because most or all intervals of a container may have to be visited. As an example, time complexity of Addition on interval containers is briefly discussed.
More information on complexity characteristics of icl's functions is contained in section Function Reference
The next table gives the time complexities for the overloaded operator +=
on interval containers. The instance types of T
are given as column headers. Instances of type parameter P
are denoted in the second column. The third column contains the specific
kind of complexity statement. If column three is empty worst case complexity is given in the related
row.
Table 1.15. Time Complexity of Addition:
|
interval |
separate |
split |
interval |
split |
||
---|---|---|---|---|---|---|---|
|
|
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
|
|
best case |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
|
worst case |
O(n) |
O(n) |
O(n) |
O(n) |
O(n) |
||
amortized |
O(log n) |
O(log n) |
|||||
|
O(m log(n+m)) |
O(m log(n+m)) |
O(m log(n+m)) |
||||
|
O(m log(n+m)) |
O(m log(n+m)) |
Adding an element or element value pair is always done in logarithmic time, where n is the number of intervals in the interval container. The same row of complexities applies to the insertion of a segment (an interval or an interval value pair) in the best case, where the inserted segment does overlap with only a small number of intervals in the container.
In the worst case, where the inserted segment overlaps with all intervals in the container, the algorithms iterate over all the overlapped segments. Using inplace manipulations of segments and hinted inserts, it is possible to perform all necessary operations on each iteration step in constant time. This results in linear worst case time complexity for segment addition for all interval containers.
After performing a worst case addition for an interval_set
or a separate_interval_sets
adding an interval that overlaps n intervals, we need
n non overlapping additions of logarithmic
time before we can launch another O(n) worst
case addition. So we have only a logarithmic
amortized time for the addition of an interval or interval
value pair.
For the addition of interval containers
complexity is O(m log(n+m)). So for the worst case, where the container sizes
n and m are equal and both containers
cover the same ranges, the complexity of container addition is loglinear. For other cases, that occur
frequently in real world applications performance can be much better. If
the added container operand
is much smaller than object
and the intervals in operand
are relatively small, performance can be logarithmic.
If m is small compared with n and
intervals in operand
are
large, performance tends to be linear.