Concepts¶
The following definitions use the expositiononly alias:
template <typename Seq>
using Traits = sequence_traits<std::remove_cvref_t<Seq>>; // expositiononly
Type aliases¶
cursor_t
¶
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&, thenrvalue_element_t<Seq>
is T&&.Otherwise,
rvalue_element_t<Seq>
is the same aselement_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 modelstd::common_reference_with
.
value_t
¶

template<typename Seq>
using value_t¶ The type alias
value_t
isTraits<Seq>::value_type
if that is wellformed and names a typeOtherwise,
std::remove_cvref_t<Seq>::value_type
if that is wellformed and names a typeOtherwise,
std::remove_cvref_t<element_t<Seq>>
if that is wellformedOtherwise,
value_t<Seq>
is not defined
The value type of a sequence is that type that is used to “save” an element for later reuse. 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 readonly 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 itselement_t
andconst_element_t
are the same type.Note
const_element_t<Seq>
may differ fromelement_t<Seq const>
when Seq has referencelike 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 64bit machine orint32_t
on a 32bit machine. It can optionally be configured to be a larger signed integer type.
bounds_t
¶
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, moveconstructible, moveassignable 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, copyconstructible, copyassignable and equalitycomparable. 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 withdisable_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 stateis_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 singlepass, 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) } > /*canreference*/; } && 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 nonmultipass sequence, also known as a singlepass sequence.By default, Flux assumes that a sequence is multipass if its cursor satisfies
regular_cursor
(that is, it is defaultconstructible, copyable and equalitycomparable). It is recommended that singlepass sequences make their cursors moveonly.Sometimes a sequence’s cursor type may satisfy regular_cursor, even though the sequence itself is semantically only singlepass. In this case, the sequence can explicitly optout 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 randomaccess sequence is a bidirectional sequence which allows cursors to be incremented and decremented an arbitrary number of places in constant time. Additionally, randomaccess sequences support a
distance()
operation which returns the signed offset between two cursor positions in constant time.The cursor type for a randomaccess 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 pasttheend 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 aninfinite_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, randomaccess sequence we can always calculate the size in constant time by taking the distance between the first and last cursor positions; therefore all bounded, randomaccess 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, randomaccess sequence whose elements are stored contiguously in memory. Some algorithms are able to use lowlevel 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 returnsfalse
.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 thebounded_sequence
concept says that iteration will terminate at thelast()
position after a finite number of steps. Sequences which are neither infinite nor bounded provide no compiletime 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 readonly 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 constiterable if we can also use Seq const as a sequence with the expected semantics. That is,Seq
andSeq const
must use the same cursor type, model the same set of sequence concepts, and return the same elements when iterated over (except thatSeq const
may strengthen the constqualification 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 constqualified sequence whose elements are mutable, or a nonconst 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
Singlepass sequences are typically not constiterable. Multipass and higher sequences which cache elements for performance or correctness reasons are not constiterable.
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 readonly, Seq const must be readonly as well (!read_only_sequence<Seq>  read_only_sequence<Seq const>);
writable_sequence_of
¶

template<typename Seq, typename T>
concept writable_sequence_of¶