An Inverse Index for Iterators and Circulators

Definition

The class Inverse_index<IC> constructs an inverse index for a given range [$$i,j) of two iterators or circulators of type IC. The first element $$I in the range [$$i,j) has the index 0. Consecutive elements are numbered incrementally. The inverse index provides a query for a given iterator or circulator $$k to retrieve its index number. Precondition: The iterator or circulator must be either of the random access category or the dereference operator must return stable and distinguishable addresses for the values, e.g. proxies or non-modifiable iterator with opaque values will not work.

#include <CGAL/Inverse_index.h>

Creation

Inverse_index<IC> inverse;
	invalid index.
Inverse_index<IC> inverse ( IC i);
	empty inverse index initialized to start at $$i.
Inverse_index<IC> inverse ( IC i, IC j);
	inverse index initialized with range [$$i,j).

Operations

std::size_t	inverse [ IC k]	returns inverse index of $$k. Precondition: $$k has been stored in the inverse index.
void	inverse.push_back ( IC k)
		adds $$k at the end of the indices.

Implementation

For random access iterators or circulators, it is done in constant time by subtracting $$i. For other iterator categories, an STL map is used, which results in a $$log$$j-i query time. The comparisons are done using the operator operator< on pointers.

See Also

Random_access_adaptor and Random_access_value_adaptor.