| Home | Libraries | People | FAQ | More

## Implementation

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.