...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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.
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.
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.