Implementation

Iterative size
Complexity
Inplace and infix operators

The previous section gave an overview over the interface of the icl outlining class templates, associated types and polymorphic functions and operators. In preparation to the next section, that describes the icl's polymorphic functions in more detail together with complexity characteristics, this section summarizes some general information on implementation and performance.

STL based implementation

The implementation of the icl's containers is based on std::set and std::map. So the underlying data structure of interval containers is a red black tree of intervals or interval value pairs. The element containers std::set and icl::map are wrapper classes of std::set and std::map. Interval containers are then using std::sets of intervals or icl::maps of interval value pairs as implementing containers. So all the complexity characteristics of icl containers are based on and limited by the red-black tree implementation of the underlying std::AssociativeContainers.

Iterative size

Throughout the documentation on complexity, big O expressions like O(n) or O(m log n) refer to container sizes n and m. In this documentation these sizes do not denote to the familiar size function that returns the number of elements of a container. Because for an interval container

interval_set<int> mono;
mono += interval<int>::closed(1,5); // {[1 ... 5]}
mono.size()           == 5;         // true, 5 elements
mono.interval_count() == 1;         // true, only one interval

it's size and the number of contained intervals is usually different. To refer uniformly to a size that matters for iteration, which is the decisive kind of size concerning algorithmic behavior there is a function

bool T::iterative_size()const; // Number of entities that can be iterated over.

for all element and interval containers of the icl. So for complexity statements throughout the icl's documentation the sizes will be iterative_sizes and big O expressions like O(m log n) will refer to sizes

n = y.iterative_size();
m = x.iterative_size();

for containers y and x. Note that

iterative_size

refers to the primary entities, that we can iterate over. For interval containers these are intervals or segments.

Itervative_size

never refers to element iteration for interval containers.