Reference Manual: CGAL_Inverse

Navigation: Up, Table of Contents, Bibliography, Index, Title Page

An Inverse Index for Iterators and Circulators

Definition

The class CGAL_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

CGAL_Inverse_index<IC> inverse;
invalid index.

CGAL_Inverse_index<IC> inverse ( IC i);
empty inverse index initialized to start at $i$ .

CGAL_Inverse_index<IC> inverse ( IC i, IC j);
inverse index initialized with range [ $i,j$ ).

Operations

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.

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

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.

An Inverse Index for Iterators and Circulators

Definition

Creation

Operations

Implementation

See Also