Home | Libraries | People | FAQ | More |

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

The **implementation** of the **itl'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 `itl::set`

and `itl::map`

are wrapper classes of `std::set`

and `std::map`

. Interval containers are then using
`itl::sets`

of intervals or `itl::maps`

of interval value pairs as implementing
containers. So all the * complexity characteristics*
of itl containers are based on and limited by the

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 interval_set<int> mono; mono += interval<int>(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 itl. So for complexity statements
throughout the itl'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.