flux icon indicating copy to clipboard operation
flux copied to clipboard

[OUTDATED] Add iterable concept

Open tcbrindle opened this issue 1 year ago • 1 comments

This PR adds a new iterable concept and updates various algorithms and adaptors to use it.

An iterable is, as the name suggests, something we can iterate over -- specifically, by using internal iteration. The required interface is:

struct sequence_traits<T> {
    auto element_type(T& iterable) -> E;

    template <typename T, typename Pred>
        requires std::predicate<Pred&, E>
    auto iterate(T& iterable, Pred&& pred) -> bool;
};

This is basically the existing for_each_while abstracted out into its own concept, returning a bool to indicate whether iteration was completed successfully rather than a cursor.

Once iterate() has returned, it is unspecified whether a second call to iterate() will start again from the beginning, carry on where it left off, do nothing, or do something else. Iterables are strictly weaker than sequences: that is, every sequence is an iterable, but not vice versa. Nonetheless, a large number of algorithms work on iterables (just about anything that can be written as a short-circuiting fold), and most of the existing sequence adaptors can work on iterables as well.

Since iterables only use internal iteration, there is no external state (i.e. a cursor) which could be invalidated. Not only does this make the iterable interface easier to implement for some types, but most importantly it means that we can provide a safe default implementation of the iterable protocol for all C++20 ranges.

This dramatically improves our interoperability with ranges, while the use of internal iteration means that converting ranges pipelines to the equivalent Flux code may yield some nice performance benefits.

tcbrindle avatar Nov 26 '24 17:11 tcbrindle