Detailed Description

This concept checks if an iterator type models pseudo random access.

A pseudo random access iterator refines the std::forward_iterator and fulfils in addition all syntactic requirements of a regular std::random_access_iterator except that iterator category is weaker than std::random_access_iterator_tag. These iterators do allow jumping within the associated range or accessing an arbitrary element but cannot guarantee constant time for these operations. Yet, the performance is sub-linear. Typical examples are range adaptors that store additional information on the original sequence within a tree like data structure. Accessing a specific position can be then achieved in sub-linear time. However, since pseudo-random access iterators can't guarantee constant time for random access, the rule in the c++ standard is to mark them as bidirectional iterators. This in turn has implications on some functions that operate on iterators. An example would be std::distance that needs linear time for non-random access iterators (e.g. bidirectional iterators and accordingly pseudo random access iterators), and constant time otherwise, although it could be computed in sub-linear time when using the pseudo randomness. The seqan3::views::enforce_random_access adaptor can redeclare a pseudo random access iterator as a random access iterator (while preserving the caveat of needing more than constant time for random access). A rule-of-thumb is that all operations are at least as fast as when using the non-redeclared random access iterators, but be aware that runtime guarantees of some algorithms are higher than advertised due to the non-constant access time.

Concepts and doxygen

Types that model this concept are shown as "implementing this interface".

This entity is not part of the SeqAn API. Do not rely on it in your applications. Exposition only.

The documentation for this interface was generated from the following file:

utility/range/concept.hpp