...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
Containedness |
intervals |
interval |
interval |
element |
element |
---|---|---|---|---|---|
|
|
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
|
This group of functions refers to containedness
which should be fundamental to containers.
The function contains
is
overloaded. It covers different kinds of containedness: Containedness of
elements, segments, and sub containers.
Containedness |
O(...) |
Description |
---|---|---|
|
O(1) |
Returns |
|
Returns |
|
|
where |
n |
|
|
m |
// overload tables for bool contains(const T& super, const P& sub) bool within(const P& sub, const T& super) element containers: interval containers: T\P| e b s m T\P| e i b p S M --------+--- --------+------- s | 1 1 S | 1 1 1 m | 1 1 1 1 M | 1 1 1 1 1 1
The overloads of bool contains(const T& super, const P& sup)
cover various kinds of containedness. We
can group them into a part (1) that checks if an element, a segment or a
container of same kinds is contained in an element or
interval container
// (1) containedness of elements, segments or containers of same kind T\P| e b s m T\P| e i b p S M ---+-------- ---+------------ s | 1 1 S | 1 1 1 m | 1 1 M | 1 1 1
and another part (2) that checks the containedness of key objects, which can be elements an intervals or a sets.
// (2) containedness of key objects. T\P| e b s m T\P| e i b p S M ---+-------- ---+------------ s | 1 1 S | 1 1 1 m | 1 1 M | 1 1 1
For type m = icl::map
,
a key element (m::domain_type
) and an std::set
(m::set_type
) can be a key object.
For an interval map type M, a key element
(M::domain_type
), an interval (M::interval_type
)
and an interval set,
can be key objects.
Complexity characteristics for function bool
contains(const T& super, const P& sub)const
are
given by the next tables where
n = iterative_size(super); m = iterative_size(sub); //if P is a container type
Table 1.20. Time Complexity for functions contains and within on interval containers
|
|
domain |
interval |
domain |
interval |
interval |
interval |
---|---|---|---|---|---|---|---|
interval_sets |
O(log n) |
O(log n) |
|
|
O(m log n) |
|
|
|
O(log n) |
O(n) |
|
|
O(m log n) |
|
|
interval_maps |
O(log n) |
O(log n) |
O(log n) |
O(log n) |
O(m log n) |
O(m log n) |
|
|
O(log n) |
O(n) |
O(log n) |
O(n) |
O(m log n) |
O(m log n) |
All overloads of containedness of containers in containers
bool contains(const T& super, const P& sub) bool within(const P& sub, const T& super)
are of loglinear time: O(m log n). If both containers have same iterative_sizes so that m = n we have the worst case ( O(n log n) ). There is an alternative implementation that has a linear complexity of O(n+m). The loglinear implementation has been chosen, because it can be faster, if the container argument is small. In this case the loglinear implementation approaches logarithmic behavior, whereas the linear implementation stays linear.
Back to section . . .