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 red-black
tree implementation of the underlying std::AssociativeContainers.
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>(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.