Algorithms

all

template<sequence Seq, predicate_for<Seq> Pred>
auto all(Seq &&seq, Pred pred) -> bool;

Takes a sequence and a predicate and returns true if every element of the sequence satisfies the predicate. This algorithm is short-circuiting: it will stop iterating (returning false) as soon as it finds an element which does not satisfy the predicate.

Returns true for an empty sequence.

Equivalent to is_last(seq, find_if_not(seq, pred)).

Parameters:

• seq – A sequence

• pred – A callable which accepts a single argument of seq’s element type and returns bool

Returns:

true if pred returns true for every element of seq.

Example:

auto is_small = [](int i) { return i < 10; };

std::vector<int> vec{1, 2, 3, 4, 5};

// Check whether every element is small
bool all_small = flux::all(vec, is_small);
assert(all_small);

See also:

• std::ranges::all_of()

• flux::any()

• flux::none()

• flux::find_if()

any

template<sequence Seq, predicate_for<Seq> Pred>
auto any(Seq &&seq, Pred pred) -> bool;

Takes a sequence and a predicate and returns true if any element in the sequence satisfies the predicate. This algorithm is short-circuiting: it will stop iterating (returning true) as soon as it has found a satisfactory element.

Returns false for an empty sequence.

Equivalent to !is_last(seq, find_if(seq, pred)).

Parameters:

• seq – A sequence.

• pred – A callable which accepts a single argument of seq’s element type and returns bool

Returns:

true if pred returns true for any element of seq.

Example:

auto is_even = [](int i) { return i % 2 == 0; };

std::vector<int> vec{1, 3, 4, 5, 7, 9};

bool b = flux::any(vec, is_even);
assert(b == true); // There is an even element

See also:

• std::ranges::any_of()

• flux::all()

• flux::none()

• flux::find_if()

compare

template<sequence Seq1, sequence Seq2, typename Cmp = std::compare_three_way>
requires see_below
auto compare(Seq1 &&seq1, Seq2 &&seq2, Cmp cmp = {});

Performs a lexicographical three-way comparison between the elements of seq1 and seq2.

This function iterates over both sequences in lock-step, and compares each respective pair of elements using cmp. If the elements are not equivalent, then the result of the comparison is returned. Otherwise, the next pair of elements is compared, and so on.

Note

If you just want to know whether the two sequences contain the same elements, you should prefer equal().

If the end of one of the sequences is reached, then:

• less is returned if the first sequence had fewer elements (was “less than”) the second

• greater is returned if the second sequence had fewer elements (so the first sequence was “greater”)

• Otherwise, all elements of both sequences were equivalent and so equivalent is returned

Requires:

The comparator cmp must return a value of one of the standard comparison categories, that is

• std::strong_ordering, or

• std::weak_ordering, or

• std::partial_ordering

Parameters:

• seq1 – The first sequence to compare

• seq2 – The second sequence to compare

• cmp – A callable accepting two parameters of the respective element types of seq1 and seq2, and returning a value of one of the standard comparison categories

Returns:

A value of the same comparison category as returned by cmp, indicating whether the first sequence is lexicographically less than, greater than or equivalent to the first, or if they are unordered.

Example:

std::vector<int> v1{1, 2, 3, 4, 5};

std::vector<int> v2{1, 4, 9, 16, 25};

// Result is std::strong_ordering because ints have a total order,
// and less because 2 < 4
assert(flux::compare(v1, v2) == std::strong_ordering::less);

// v1 compares equal to v1
assert(std::is_eq(flux::compare(v1, v1)));

std::vector<int> v3{1, 2, 3, 4, 5};
std::vector<int> v4{1, 2, 3};

// All elements compare equal, but v3 has more elements and so
// is greater than v4
assert(flux::compare(v3, v4) == std::strong_ordering::greater);

// Note that sequences containing NaNs are unordered with the default comparator
std::vector<double> v5{1.0, 2.0, 3.0, 4.0, 5.0};
std::vector<double> v6{1.0, 2.0, NAN, 4.0, 5.0};
assert(flux::compare(v5, v6) == std::partial_ordering::unordered);

// On most systems we can use std::strong_order as a custom comparator
// to get a total order for IEEE floats
if constexpr (std::numeric_limits<double>::is_iec559) {
    assert(flux::compare(v5, v6, std::strong_order) ==
             std::strong_ordering::less);
}

See also:

• std::lexicographical_compare_three_way()

• flux::equal()

contains

template<sequence Seq, typename Value>
requires std::equality_comparable_with<element_t<Seq>, Value const&>
auto contains(Seq &&seq, Value const &value) -> bool;

Returns true if any element in seq compares equal to value. This algorithm is short-circuiting: it will stop iterating as soon as it has found an equal element.

Equivalent to !is_last(seq, find(seq, value))

Parameters:

• seq – A sequence

• value – A value to search for

Returns:

true if any element of seq compares equal to value.

Example:

std::vector<std::string> const simpsons{
    "Homer", "Marge", "Bart", "Lisa", "Maggie"
};

// Bart is a Simpson
assert(flux::contains(simpsons, "Bart"));

// Mr Burns is not a Simpson
assert(not flux::contains(simpsons, "Mr Burns"));

See also:

• std::ranges::contains()

• flux::find()

count

auto count(sequence auto &&seq) -> distance_t;

Returns the number of elements in the sequence.

If seq is a sized_sequence then this is equivalent to flux::size(). Otherwise, count() will iterate over the sequence, “using up” single-pass sequences.

Equivalent to:

if constexpr (sized_sequence<decltype(seq)>) {
    return size(seq);
} else {
    return count_if(seq, pred::true_);
}

Parameters:

seq – A sequence

Returns:

The number of elements in seq

Example:

std::vector<int> vec{1, 2, 3};

// std::vector is a sized_sequence, so this call is
// equivalent to `flux::size(vec)` (and so constant time)
assert(flux::count(vec) == 3);

// A filtered sequence is never sized, so this call will
// iterate over each element
auto filtered = flux::filter(std::move(vec), flux::pred::odd);
assert(flux::count(filtered) == 2);

// An istream sequence is single-pass and not sized, so counting
// the elements will "use up" the sequence
std::istringstream iss("1 2 3");
auto seq = flux::from_istream<int>(iss);
assert(flux::count(seq) == 3);
assert(flux::is_last(seq, flux::first(seq))); // No more elements!

See also:

• std::ranges::distance()

• flux::count_eq()

• flux::count_if()

count_eq

template<sequence Seq, typename Value>
requires std::equality_comparable_with<element_t<Seq>, Value const&>
auto count_eq(Seq &&seq, Value const &value) -> distance_t;

Iterates over seq and returns the number of elements which compare equal to value.

Equivalent to count_if(seq, pred::eq(value)), but does not take a copy of value.

Parameters:

• seq – A sequence

• value – A value which is equality comparable with seq’s element type

Returns:

The number of elements of seq which compared sequence to value.

Example:

See also:

• std::ranges::count()

• flux::count()

• flux::count_if()

count_if

template<typename Seq, typename Pred>
requires std::predicate<Pred&, element_t<Seq>>
auto count_if(Seq &&seq, Pred pred) -> distance_t;

Returns the number of elements in the sequence for which the predicate returned true.

Equivalent to:

fold(seq, [&pred](distance_t count, auto&& elem) {
    if (std::invoke(pred, std::forward(elem))) {
        ++count;
    }
    return count;
}, distance_t{0})

Parameters:

• seq – A sequence

• pred – A unary predicate accepting seq’s element type, indicating whether the element should be counted

Returns:

The number of elements for which pred returned true.

Example:

See also:

• std::ranges::count_if()

• count()

• count_eq()

• fold()

ends_with

template<sequence Seq1, sequence Seq2, typename Cmp = std::ranges::equal_to>
requires see_below
auto ends_with(Seq1 &&seq1, Seq2 &&seq2, Cmp cmp = {}) -> bool;

Returns true if seq2 is a suffix of seq1 according to the comparator cmp.

If Seq1 and Seq2 both satisfy sized_sequence and seq1 has fewer elements than seq2, starts_with() immediately returns false and no comparisons are performed.

Requires:

Both Seq1 and Seq2 must model either multipass_sequence or sized_sequence. Additionally, std::predicate<Cmp&, element_t<Seq1>, element_t<Seq2>> must be modelled.

Parameters:

• seq1 – The “haystack” sequence

• seq2 – The “needle” sequence

• cmp – Predicate used to compare sequence elements, defaulting to std::ranges::equal_to.

Returns:

true if seq1 has seq2 as its final subsequence.

Example:

std::string_view greeting = "Hello world";

// greeting has "world" as a suffix
assert(flux::ends_with(greeting, "world"sv));

std::vector numbers{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// numbers ends with [8, 9, 10]
assert(flux::ends_with(numbers, std::array{8, 9, 10}));

See also:

• std::ranges::ends_with() (C++23)

• flux::starts_with()

• flux::equal()

equal

template<sequence Seq1, sequence Seq2, typename Cmp = std::equal_to<>>
requires std::predicate<Cmp&, element_t<Seq1>, element_t<Seq2>>
auto equal(Seq1 &&seq1, Seq2 &&seq2, Cmp cmp = {}) -> bool;

Returns true if seq1 and seq2 have the same number of elements and each corresponding pair of elements compares equal according to cmp.

If seq1 and seq2 both satisfy sized_sequence and their sizes differ, equal() immediately returns false and no comparisons are performed.

When using the default comparators, equal(seq1, seq2) returns the same answer as std::is_eq(compare(seq1, seq2)) but may be more efficient.

Parameters:

• seq1 – A sequence

• seq2 – Another sequence

• cmp – A binary predicate to use as a comparator, defaulting to std::equal_to<>.

Returns:

true if seq1 and seq2 have the same number of elements and each corresponding pair of elements compares equal.

Example:

See also:

• std::ranges::equal()

• flux::compare()

fill

template<sequence Seq, typename Value>
requires writeable_sequence_of<Seq, Value const&>
auto fill(Seq &&seq, Value const &value) -> void;

Assigns value to every element of seq.

Equivalent to:

for_each(seq, [&value](auto&& elem) {
    std::forward(elem) = value;
})

Parameters:

• seq – A mutable sequence whose element type is assignable from Value const&

• value – A value to assign to each element of seq.

Example:

See also:

• std::ranges::fill()

find

template<sequence Seq, typename Value>
requires std::equality_comparable_with<element_t<Seq>, Value const&>
auto find(Seq &&seq, Value const &value) -> cursor_t<Seq>;

find_if

template<sequence Seq, typename Pred>
requires std::predicate<Pred&, element_t<Seq>>
auto find_if(Seq &&seq, Pred pred) -> cursor_t<Seq>;

find_if_not

template<sequence Seq, typename Pred>
requires std::predicate<Pred&, element_t<Seq>>
auto find_if_not(Seq &&seq, Pred pred) -> cursor_t<Seq>;

find_max

template<multipass_sequence Seq, weak_ordering_for<Seq> Cmp = std::compare_three_way>
auto find_max(Seq &&seq, Cmp cmp = {}) -> cursor_t<Seq>;

Returns a cursor to the maximum element of seq, compared using cmp.

If several elements are equally maximal, find_max() returns a cursor to the last such element.

Note

This behaviour differs from std::max_element(), which returns an iterator to the first maximal element.

Parameters:

• seq – A multipass sequence

• cmp – A comparator to use to find the maximum element, defaulting to std::compare_three_way

Returns:

A cursor pointing to the maximum element of seq.

Example:

struct Person {
    std::string name;
    int age;
};

std::vector<Person> people{
    {"Alice", 44},
    {"Bob", 63},
    {"Chris", 29},
    {"Dani",  29},
    {"Eddy", 63}
};

// Get a cursor to the maximum of the people vector, according to age
auto max_cur = flux::find_max(people, flux::proj(flux::cmp::compare, &Person::age));

// The oldest person is 63
assert(flux::read_at(people, max_cur).age == 63);

// Note that (unlike std::max_element) find_max() return a cursor to the
// *last* of several equally-maximum elements
assert(flux::read_at(people, max_cur).name == "Eddy");

See also:

• std::ranges::max_element()

• flux::max()

• flux::find_minmax()

find_min

template<multipass_sequence Seq, weak_ordering_for<Seq> Cmp = std::compare_three_way>
auto find_min(Seq &&seq, Cmp cmp = {}) -> cursor_t<Seq>;

Returns a cursor to the minimum element of seq, compared using cmp.

If several elements are equally minimal, find_min() returns a cursor to the first such element.

Parameters:

• seq – A multipass sequence

• cmp – A comparator to use to find the minimum element, defaulting to std::compare_three_way

Returns:

A cursor pointing to the minimum element of seq.

Example:

struct Person {
    std::string name;
    int age;
};

std::vector<Person> people{
    {"Alice", 44},
    {"Bob", 63},
    {"Chris", 29},
    {"Dani",  29},
    {"Eddy", 63}
};

// Get a cursor to the maximum of the people vector, according to age
auto min_cur = flux::find_min(people, flux::proj(flux::cmp::compare, &Person::age));

// The youngest person is 29
assert(flux::read_at(people, min_cur).age == 29);

// Note that find_min() return a cursor to the first of several
// equally-minimum elements
assert(flux::read_at(people, min_cur).name == "Chris");

See also:

• std::ranges::min_element()

• flux::min()

• flux::minmax()

find_minmax

template<multipass_sequence Seq, weak_ordering_for<Seq> Cmp = std::compare_three_way>
auto find_minmax(Seq &&seq, Cmp cmp = {}) -> minmax_result<cursor_t<Seq>>;

Returns a pair of cursors to the minimum and maximum elements of seq, compared using cmp.

If several elements are equally minimal, find_minmax() returns a cursor to the first. If several elements are equally maximal, find_minmax() returns a cursor to the last.

Equivalent to:

minmax_element<cursor_t<Seq>>{.min = find_min(seq, cmp),
                              .max = find_max(seq, cmp)};

but only does a single pass over seq.

Parameters:

• seq – A multipass sequence

• cmp – A comparator to use to find the maximum element, defaulting to std::compare_three_way

Returns:

A cursor pointing to the maximum element of seq.

Example:

struct Person {
    std::string name;
    int age;
};

std::vector<Person> people{
    {"Alice", 44},
    {"Bob", 63},
    {"Chris", 29},
    {"Dani",  29},
    {"Eddy", 63}
};

// find_minmax() returns a pair of cursors which we can destructure
// Here we'll get the min and max of the people vector, according to age
auto [min, max] = flux::find_minmax(people, flux::proj(flux::cmp::compare, &Person::age));

// The "minimum" is Chris. Dani is the same age, but Chris appears earlier
// in the sequence
assert(flux::read_at(people, min).name == "Chris");

// The "maximum" is Eddy. Bob is the same age, but Eddy appears later in the
// sequence
assert(flux::read_at(people, max).name == "Eddy");

See also:

• std::ranges::minmax_element()

• flux::minmax()

fold

template<sequence Seq, typename Func, typename Init>
using fold_result_t = std::decay_t<std::invoke_result_t<Func&, Init, element_t<Seq>>>;

template<sequence Seq, typename Func, typename Init = value_t<Seq>>
requires see_below
auto fold(Seq &&seq, Func func, Init init = {}) -> fold_result_t<Seq, Func, Init>;

fold_first

template<typename Seq, typename Func>
requires see_below
auto fold_first(Seq &&seq, Func func) -> optional<value_t<Seq>>;

for_each

template<typename Seq, typename Func>
requires std::invocable<Func&, element_t<Seq>>
auto for_each(Seq &&seq, Func func) -> Func;

for_each_while

template<typename Seq, typename Func>
requires see_below
auto for_each_while(Seq &&seq, Func func) -> cursor_t<Seq>;

inplace_reverse

template<bidirectional_sequence Seq>
requires bounded_sequence<Seq> && element_swappable_with<Seq, Seq>
auto inplace_reverse(Seq &&seq) -> void;

max

template<sequence Seq, weak_ordering_for<Seq> Cmp = std::compare_three_way>
auto max(Seq &&seq, Cmp cmp = {}) -> optional<value_t<Seq>>;

min

template<sequence Seq, weak_ordering_for<Seq> Cmp = std::compare_three_way>
requires std::predicate<Cmp&, value_t<Seq>, element_t<Seq>>
auto min(Seq &&seq, Cmp cmp = {}) -> optional<value_t<Seq>>;

minmax

template<typename T>
struct minmax_result;

template<sequence Seq, weak_ordering_for<Seq> Cmp = std::compare_three_way>
requires std::predicate<Cmp&, value_t<Seq>, element_t<Seq>>
auto minmax(Seq &&seq, Cmp cmp = {}) -> optional<minmax_result<Seq>>;

none

template<sequence Seq, predicate_for<Seq> Pred>
auto none(Seq &&seq, Pred pred) -> bool;

output_to

template<sequence Seq, std::weakly_incrementable Iter>
requires std::indirectly_writable<Iter, element_t<Seq>>
auto output_to(Seq &&seq, Iter iter) -> Iter;

product

template<sequence Seq>
requires see_below
auto product(Seq &&seq) -> value_t<Seq>;

search

template<multipass_sequence Haystack, multipass_sequence Needle, typename Cmp = std::ranges::equal_to>
requires std::predicate<Cmp&, element_t<Haystack>, element_t<Needle>>
auto search(Haystack &&h, Needle &&n, Cmp cmp = {}) -> bounds_t<Haystack>;

sort

template<random_access_sequence Seq, typename Cmp = std::compare_three_way>
requires see_below
auto sort(Seq &&seq, Cmp cmp = {}) -> void;

starts_with

template<sequence Seq1, sequence Seq2, typename Cmp = std::ranges::equal_to>
requires std::predicate<Cmp&, element_t<Seq1>, element_t<Seq2>>
auto starts_with(Seq1 &&seq1, Seq2 &&seq2, Cmp cmp = {}) -> bool;

Returns true if seq2 is a prefix of seq1 according to the comparator cmp.

If Seq1 and Seq2 both satisfy sized_sequence and seq1 has fewer elements than seq2, starts_with() immediately returns false and no comparisons are performed.

Parameters:

• seq1 – The “haystack” sequence

• seq2 – The “needle” sequence

• cmp – Predicate used to compare sequence elements, defaulting to std::ranges::equal_to.

Returns:

true if seq1 has seq2 as its initial subsequence.

Example:

std::string_view greeting = "Hello world";

// greeting has "Hello" as a prefix
assert(flux::starts_with(greeting, "Hello"sv));

std::vector numbers{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// numbers begins with [1, 2, 3]
assert(flux::starts_with(numbers, std::array{1, 2, 3}));

See also:

• std::ranges::starts_with() (C++23)

• flux::ends_with()

• flux::equal()

sum

template<sequence Seq>
requires see_below
auto sum(Seq &&seq) -> value_t<Seq>;

swap_elements

template<sequence Seq1, sequence Seq2>
requires element_swappable_with<Seq1, Seq2>
auto swap_elements(Seq1 &&seq1, Seq2 &&seq2) -> void;

to

template<typename Container>
requires see_below
auto to(sequence auto &&seq, auto&&... args) -> Container;

template<template<typename...> typename Container>
requires see_below
auto to(sequence auto &&seq, auto&&... args);

Converts a Flux sequence to a container, for example a std::vector.

The first overload takes a “complete” container type name as its template argument, for example std::vector<int> or std::list<std::string>. The second overload takes a template name as its template argument, for example just std::vector or std::map, and will then use CTAD to deduce the appropriate template arguments.

The optional extra arguments provided to flux::to(), denoted args... above, will be forwarded to the selected container constructor as detailed below. The intention is to allow using (for example) custom allocator arguments.

Let C be the target container type (either explicitly specified for the first overload, or deduced via CTAD). If the sequence’s element type is convertible to C::value_type, then flux::to() will try to construct a C using the following methods, in order of priority:

• Direct sequence construction using C(std::forward(seq), std::forward(args)...)

  Note

  If C is the same type as seq, this allows it to be copy- or move-constructed

• Tagged sequence construction using C(flux::from_sequence, std::forward(seq), std::forward(args)...)

• (In C++23) Tagged range construction as if by:

  auto sub = std::ranges::subrange(begin(seq), end(seq));
  return C(std::from_range, sub, std::forward(args)...);
  

• C++17 iterator pair construction, as if by:

  auto view = std::ranges::subrange(begin(seq), end(seq)) | std::views::common;
  return C(view.begin(), view.end(), std::forward(args)...);
  

• Inserting elements as if by:

  auto container = C(std::forward(args)...);
  output_to(std::forward(seq), range_inserter);
  return container;
  

  where range_inserter is std::back_inserter(container) if the container has a compatible push_back() member function, or std::inserter(container, container.end()) otherwise. Will also attempt to call container.reserve() if possible to avoid reallocations during construction.

If the sequence’s element type is convertible to the container’s value type but none of the above methods work, compilation will fail.

If the sequence’s element type itself satisfies sequence, but is not convertible to the container value type, then flux::to<C>(seq, args...) is equivalent to:

flux::to<C>(flux::map(std::forward(seq), [](auto&& elem) {
    flux::to<typename C::value_type>(std::forward(elem));
}), std::forward(args)...);

That is, to() will attempt to first convert each inner sequence to the container value type before proceeding as above.

Template Parameters:

Container – A type name (for the first overload) or a template name (for the second overload) which names a compatible container type

Parameters:

• seq – A sequence to be converted to a container

• args – Optional extra arguments to be forwarded to the container constructor

Example:

See also:

write_to

auto write_to(sequence auto &&seq, std::ostream &os) -> std::ostream&;

zip_find_if

template<typename Pred, sequence... Seqs>
requires std::predicate<Pred&, element_t<Seqs>...>
auto zip_find_if(Pred pred, Seqs&&... seqs) -> std::tuple<cursor_t<Seqs>...>;

zip_fold

template<typename Func, typename Init, typename ...Seqs>
using zip_fold_result_t = std::decay_t<std::invoke_result_t<Func&, Init, element_t<Seqs>...>>;

template<typename Func, typename Init, sequence... Seqs>
requires see_below
auto zip_fold(Func func, Init init, Seqs&&... seqs) -> zip_fold_result_t<Func, Init, Seqs...>;

zip_for_each

template<typename Func, sequence... Seqs>
requires std::invocable<Func&, element_t<Seqs>...>
auto zip_for_each(Func func, Seqs&&... seqs) -> Func;

zip_for_each_while

template<typename Pred, sequence... Seqs>
requires see_below
auto zip_for_each_while(Pred pred, Seqs&&... seqs) -> std::tuple<cursor_t<Seqs>...>;