Concepts¶

The following definitions use the exposition-only alias:

template <typename Seq>
using Traits = sequence_traits<std::remove_cvref_t<Seq>>; // exposition-only

Type aliases¶

`cursor_t`¶

template<typename Seq> using cursor_t = decltype(Traits<Seq>::first(std::declval<Seq&>()));¶

The sequence’s associated cursor type, used for iteration and element access.

Note that if Seq and Seq const are both iterable, then they must have the same cursor type.

`element_t`¶

template<typename Seq> using element_t = decltype(Traits<Seq>::read_at(std::declval<Seq&>(), std::declval<cursor_t<Seq> const&>()));¶: The element type of the sequence. This must be “referenceable”, i.e. not void, but otherwise may be a reference type or an object type. The element types of Seq and Seq const will often differ.

`rvalue_element_t`¶

template<typename Seq> using rvalue_element_t¶

If a sequence provides a custom implementation of move_at(), then its rvalue element type is the return type of move_at().
Otherwise, if element_t<Seq> names an lvalue reference type T&, then rvalue_element_t<Seq> is T&&.
Otherwise, rvalue_element_t<Seq> is the same as element_t<Seq>

The rvalue element type of a sequence is the type that is used when we want to move an element out of the sequence. Sequence implementations can customise this providing their own move_at() specialisation; otherwise, the default is equivalent to std::move(read_at(seq, cur)).

The sequence concept requires that a sequence’s element type and rvalue element type model std::common_reference_with.

`value_t`¶

template<typename Seq> using value_t¶

The type alias value_t is

Traits<Seq>::value_type if that is well-formed and names a type
Otherwise, std::remove_cvref_t<Seq>::value_type if that is well-formed and names a type
Otherwise, std::remove_cvref_t<element_t<Seq>> if that is well-formed
Otherwise, value_t<Seq> is not defined

The value type of a sequence is that type that is used to “save” an element for later re-use. For example, if a sequence has element type int const&, then its corresponding value type would normally be int. The value type should be an object type, not a reference.

Flux provides the ability to customise the value type, but this is normally only needed for specialised adaptors like zip(). Most sequence implementations do not need to provide this themselves.

`const_element_t`¶

template<typename Seq> using const_element_t = std::common_reference_t<value_t<Seq> const&&, element_t<Seq>>;¶

The const element type of a sequence is the element type which is yielded when requesting read-only access to the sequence. For example, if the element type of a sequence is int&, its corresponding const_element_t will usually be int const&.

A sequence models read_only_sequence if its element_t and const_element_t are the same type.

Note

const_element_t<Seq> may differ from element_t<Seq const> when Seq has reference-like semantics, for example flux::array_ptr<T> or std::reference_wrapper<Seq>.

`distance_t`¶

using distance_t = config::int_type;¶: Flux uses a single signed integer type, aliased as distance_t, to represent all distances, sizes, offsets and so on in the library. This will usually be machine word sized i.e. int64_t on a 64-bit machine or int32_t on a 32-bit machine. It can optionally be configured to be a larger signed integer type.

`bounds_t`¶

template<cursor Cur> struct bounds¶

template<sequence Seq> using bounds_t = bounds<cursor_t<Seq>>;¶

Concepts¶

`cursor`¶

template<typename C> concept cursor = std::movable<C>;¶: In Flux, a cursor is an object that represents a position of an element in a sequence (or, more precisely, a position between two elements in a sequence, or at the beginning or end). Flux requires only that basic cursors are movable (that is, move-constructible, move-assignable and destructible), but it is assumed that these operations are “cheap”.

`regular_cursor`¶

template<typename C> concept regular_cursor = cursor<C> && std::regular<C>;¶

A regular cursor is a cursor that is additionally a regular type – that is, it is default constructible, copy-constructible, copy-assignable and equality-comparable. Regular cursors may be copied within algorithm implementations, so copying should be “cheap”.

The equality operator for regular_cursor s belonging to the same sequence should return true if the cursors represent the same position, and false otherwise.

A sequence whose cursor type satisfies regular_cursor is assumed to be a multipass sequence unless specifically disabled with disable_multipass.

`ordered_cursor`¶

template<typename C> concept ordered_cursor = regular_cursor<C> && std::three_way_comparable<C, std::strong_ordering>;¶

An ordered cursor is a regular cursor which is additionally totally ordered and may be compared using the “spaceship” operator <=>.

For two ordered_cursor s a and b belonging to the same sequence, a <=> b should return std::strong_ordering::less if a represents a position earlier in the sequence, greater if b represents a position earlier in the sequence, and equal otherwise.

`sequence`¶

template<typename S> concept sequence¶

A Flux sequence is a homogeneous collection of elements which we can iterate over. Sequences provide the following four operations:

first(seq), which returns a cursor representing the iteration state
is_last(seq, cur) which returns a boolean indicating whether iteration is complete
read_at(seq, cur) which accesses the sequence element corresponding to the given cursor position
inc(seq, cur) which takes the cursor by reference and advances it so that it refers to the next sequence element

A sequence may be single-pass, meaning we can only visit each position once, or may be multipass, indicating that we can revisit cursor positions multiple times.

The sequence concept is defined as:

template <typename Seq> sequence =
    requires (Seq& seq) {
        { Traits<Seq>::first(seq) } -> cursor;
    } &&
    requires (Seq& seq, cursor_t<Seq> const& cur) {
        { Traits<Seq>::is_last(seq, cur) } -> std::same_as<bool>;
        { Traits<Seq>::read_at(seq, cur) } -> /*can-reference*/;
    } &&
    requires (Seq& seq, cursor_t<Seq>& cur) {
        { Traits<Seq>::inc(seq, cur) }
    };

`multipass_sequence`¶

template<typename Seq> concept multipass_sequence = sequence<Seq> && regular_cursor<cursor_t<Seq>> && !disable_multipass<Seq>;¶

A multipass sequence is a sequence which supports separate iteration by two or more cursors independently. A container is typically a multipass sequence; a std::istream is a non-multipass sequence, also known as a single-pass sequence.

By default, Flux assumes that a sequence is multipass if its cursor satisfies regular_cursor (that is, it is default-constructible, copyable and equality-comparable). It is recommended that single-pass sequences make their cursors move-only.

Sometimes a sequence’s cursor type may satisfy regular_cursor, even though the sequence itself is semantically only single-pass. In this case, the sequence can explicitly opt-out of multipass behaviour either by

providing a variable template specialisation:

template <>
inline constexpr bool flux::disable_multipass<SeqType> = true;

or, providing a static constexpr bool member variable Traits<Seq>::disable_multipass = true.

`bidirectional_sequence`¶

template<typename Seq> concept bidirectional_sequence¶

A bidirectional sequence is a multipass sequence which additionally allows cursors to be decremented as well as incremented – that is, one which allows backwards iteration.

The bidirectional_sequence concept is defined as:

template <typename Seq>
bidirectional_sequence =
    multipass_sequence<Seq> &&
    requires (Seq& seq, cursor_t<Seq>& cur) {
        { Traits<Seq>::dec(seq, cur); }
    };

`random_access_sequence`¶

template<typename S> concept random_access_sequence¶

A random-access sequence is a bidirectional sequence which allows cursors to be incremented and decremented an arbitrary number of places in constant time. Additionally, random-access sequences support a distance() operation which returns the signed offset between two cursor positions in constant time.

The cursor type for a random-access sequence must model ordered_cursor, meaning we can compare cursor positions to know whether one position is earlier or later in the sequence than the other.

The random_access_sequence concept is defined as:

template <typename Seq>
concept random_access_sequence =
    bidirectional_sequence<Seq> && ordered_cursor<cursor_t<Seq>> &&
    requires (Seq& seq, cursor_t<Seq>& cur, distance_t offset) {
        { Traits::inc(seq, cur, offset) };
    } &&
    requires (Seq& seq, cursor_t<Seq> const& cur) {
        { Traits::distance(seq, cur, cur) } -> std::convertible_to<distance_t>;
    };

`bounded_sequence`¶

template<typename Seq> concept bounded_sequence¶

A bounded sequence is one which can provide a past-the-end cursor in constant time. Iterating over a sequence in reverse requires a sequence that is both bounded and bidirectional, because we need to be able to find the end and move backwards from there.

Iterating over a bounded always terminates, so a sequence cannot be both a bounded_sequence and an infinite_sequence.

The bounded_sequence concept is defined as:

template <typename Seq>
concept bounded_sequence =
    sequence<Seq> &&
    requires (Seq& seq) {
        { Traits::last(seq) } -> std::same_as<cursor_t<Seq>>;
    };

`sized_sequence`¶

template<typename Seq> concept sized_sequence¶

A sized sequence is a sequence that knows the number of elements it contains in constant time.

For a bounded, random-access sequence we can always calculate the size in constant time by taking the distance between the first and last cursor positions; therefore all bounded, random-access sequences automatically satisfy sized_sequence.

The sized_sequence concept is defined as:

template <typename Seq>
concept sized_sequence =
    sequence<Seq> &&
    (requires (Seq& seq) {
        { Traits::size(seq) } -> std::convertible_to<distance_t>;
    } || (
        random_access_sequence<Seq> && bounded_sequence<Seq>
    ));

`contiguous_sequence`¶

template<typename Seq> concept contiguous_sequence¶

A contiguous sequence is a bounded, random-access sequence whose elements are stored contiguously in memory. Some algorithms are able to use low-level operations such as memcpy() when operating on contiguous sequences of trivial types.

The contiguous_sequence concept is defined as:

template <typename Seq>
concept contiguous_sequence =
    random_access_sequence<Seq> &&
    bounded_sequence<Seq> &&
    std::is_lvalue_reference_v<element_t<Seq>> &&
    std::same_as<value_t<Seq>, std::remove_cvref_t<element_t<Seq>>> &&
    requires (Seq& seq) {
        { Traits::data(seq) } -> std::same_as<std::add_pointer_t<element_t<Seq>>>;
    };

`infinite_sequence`¶

template<typename Seq> concept infinite_sequence¶

An infinite sequence is one which is known statically never to terminate: that is, its is_last() implementation always returns false.

A sequence which is bounded or sized cannot also be an infinite_sequence.

Note

The infinite_sequence concept says that iteration will never terminate, and the bounded_sequence concept says that iteration will terminate at the last() position after a finite number of steps. Sequences which are neither infinite nor bounded provide no compile-time information either way.

A sequence implementation may indicate that is is infinite by setting:

static constexpr bool is_infinite = true;

in its sequence_traits.

`read_only_sequence`¶

template<typename Seq> concept read_only_sequence = sequence<Seq> && std::same_as<element_t<Seq>, const_element_t<Seq>>;¶: A read-only sequence is one which does not allow modification of its elements via the sequence interface – that is, its read_at() method returns either a const reference or a prvalue.

`const_iterable_sequence`¶

template<typename Seq> concept const_iterable_sequence¶

A sequence Seq is const-iterable if we can also use Seq const as a sequence with the expected semantics. That is, Seq and Seq const must use the same cursor type, model the same set of sequence concepts, and return the same elements when iterated over (except that Seq const may strengthen the const-qualification of the elements).

Important

The immutability of a sequence object is not necessarily related to the immutability of its elements. For example, it’s possible to have a const-qualified sequence whose elements are mutable, or a non-const sequence whose elements are immutable.

Given a sequence S:

use const_iterable_sequence<S> if you need to know whether you can iterate over S const
use read_only_sequence<S> if you need to know whether you can mutate the elements of S via the sequence API

Single-pass sequences are typically not const-iterable. Multipass and higher sequences which cache elements for performance or correctness reasons are not const-iterable.

The const_iterable_sequence concept is defined as:

template <typename Seq>
concept const_iterable_sequence =
    // Seq and Seq const must both be sequences
    sequence<Seq> && sequence<Seq const> &&
    // Seq and Seq const must have the same cursor and value types
    std::same_as<cursor_t<Seq>, cursor_t<Seq const>> &&
    std::same_as<value_t<Seq>, value_t<Seq const>> &&
    // Seq and Seq const must have the same const_element type
    std::same_as<const_element_t<Seq>, const_element_t<Seq const>> &&
    // Seq and Seq const must model the same extended sequence concepts
    (multipass_sequence<Seq> == multipass_sequence<Seq const>) &&
    (bidirectional_sequence<Seq> == bidirectional_sequence<Seq const>) &&
    (random_access_sequence<Seq> == random_access_sequence<Seq const>) &&
    (contiguous_sequence<Seq> == contiguous_sequence<Seq const>) &&
    (bounded_sequence<Seq> == bounded_sequence<Seq const>) &&
    (sized_sequence<Seq> == sized_sequence<Seq const>) &&
    (infinite_sequence<Seq> == infinite_sequence<Seq const>) &&
    // If Seq is read-only, Seq const must be read-only as well
    (!read_only_sequence<Seq> || read_only_sequence<Seq const>);

`writable_sequence_of`¶

template<typename Seq, typename T> concept writable_sequence_of¶

Concepts¶

Type aliases¶

cursor_t¶

element_t¶

rvalue_element_t¶

value_t¶

const_element_t¶

distance_t¶

bounds_t¶

Concepts¶

cursor¶

regular_cursor¶

ordered_cursor¶

sequence¶

multipass_sequence¶

bidirectional_sequence¶

random_access_sequence¶

bounded_sequence¶

sized_sequence¶

contiguous_sequence¶

infinite_sequence¶

read_only_sequence¶

const_iterable_sequence¶

writable_sequence_of¶

`cursor_t`¶

`element_t`¶

`rvalue_element_t`¶

`value_t`¶

`const_element_t`¶

`distance_t`¶

`bounds_t`¶

`cursor`¶

`regular_cursor`¶

`ordered_cursor`¶

`sequence`¶

`multipass_sequence`¶

`bidirectional_sequence`¶

`random_access_sequence`¶

`bounded_sequence`¶

`sized_sequence`¶

`contiguous_sequence`¶

`infinite_sequence`¶

`read_only_sequence`¶

`const_iterable_sequence`¶

`writable_sequence_of`¶