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

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:

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

A sequence Seq models writable_sequence_t<Seq, T> for a type T if element_t<Seq> is assignable from an object of type T.

The writable_sequence_of concept is defined as:

template <typename Seq, typename T>
concept writable_sequence_of =
    sequence<Seq> &&
    requires (element_t<Seq> e, T&& item) {
        { e = std::forward<T>(item) } -> std::same_as<element_t<Seq>&>;
    };

element_swappable_with

template<typename Seq1, typename Seq2>
concept element_swappable_with

A pair of sequences Seq1 and Seq2 model element_swappable_with if their respective elements can be swapped, that is, we can assign to an element of Seq1 from an rvalue element of Seq2 and vice-versa.

Formally, the element_swappable_with concept is defined as:

template <typename Seq1, typename Seq2>
concept element_swappable_with =
    std::constructible_from<value_t<Seq1>, rvalue_element_t<Seq1>> &&
    std::constructible_from<value_t<Seq2>, rvalue_element_t<Seq2>> &&
    writable_sequence_of<Seq1, rvalue_element_t<Seq2>> &&
    writable_sequence_of<Seq1, value_t<Seq2>&&> &&
    writable_sequence_of<Seq2, rvalue_element_t<Seq1>> &&
    writable_sequence_of<Seq2, value_t<Seq1>&&>;

ordering_invocable

template<typename Fn, typename T, typename U, typename Cat = std::partial_ordering>
concept ordering_invocable

The concept ordering_invocable signifies that the binary invocable Fn return a value of one of the standard comparison categories, convertible to Cat, for all combinations of arguments of types T and U

Semantic requirements:

  • Let r1 = fn(a, b) and r2 = fn(b, c). If r1 == r2 and r1 != std::partial_ordering::unordered, then fn(a, c) == r1.

  • fn(a, b) == std::partial_ordering::less if and only if fn(b, a) == std::partial_ordering::greater

The ordering_invocable concept is defined as:

template <typename Fn, typename T, typename U, typename Cat>
concept ordering_invocable_ = // exposition-only
    std::regular_invocable<Fn, T, U> &&
    std::same_as<
        std::common_comparison_category_t<std::decay_t<std::invoke_result_t<Fn, T, U>>>,
                                          Cat>,
        Cat>;

template <typename Fn, typename T, typename U, typename Cat = std::partial_ordering>
concept ordering_invocable =
    ordering_invocable_<Fn, T, U, Cat> &&
    ordering_invocable_<Fn, U, T, Cat> &&
    ordering_invocable_<Fn, T, T, Cat> &&
    ordering_invocable_<Fn, U, U, Cat>;

weak_ordering_for

template<typename Fn, typename Seq1, typename Seq2 = Seq1>
concept weak_ordering_for

Signifies that a binary callable Fn forms a strict weak order over the elements of sequences Seq1 and Seq2.

It is defined as:

template <typename Fn, typename Seq1, typename Seq2 = Seq1>
concept weak_ordering_for =
    sequence<Seq1> &&
    sequence<Seq2> &&
    ordering_invocable<Fn&, element_t<Seq1>, element_t<Seq2>, std::weak_ordering> &&
    ordering_invocable<Fn&, value_t<Seq1>&, element_t<Seq2>, std::weak_ordering> &&
    ordering_invocable<Fn&, element_t<Seq1>, value_t<Seq2>&, std::weak_ordering> &&
    ordering_invocable<Fn&, value_t<Seq1>&, value_t<Seq2>&, std::weak_ordering> &&
    ordering_invocable<Fn&, common_element_t<Seq1>, common_element_t<Seq2>, std::weak_ordering>;