iter (alpha)

Functional C++20 iterator library. Compiler explorer demo

Small, single header, feature-rich, functional C++20 iterator library that aims to be simple, composable, and easily extensible. Much of the simplicity in the design is owed to the extend library.

• Single header
• Simple implementation (~3000 source lines all-in)
• Minimal std library dependencies: <type_traits> <concepts> <functional> <limits> <memory> <utility>
• constexpr/consteval friendly
• Interoperable with range-based for loops
• Zero-overhead
• Auto vectorisable
• Seemless interop with std::vector, std::array, std::string
• Seemless interop with other std containers
• Predictible API: the function signatures align more-or-less with those of the rust iterator library, which itself follows a pretty standard functional nomenclature.
• Documentation (relies on previous experience with standard iterator libraries in other languages)
• Full unit test coverage. Only ~70% coverage. Use at your own risk!

Getting started

Single header

1. Copy singleheader/iter.hpp into your include directory
2. Enable C++20
3. #include "iter/iter.hpp"

Full

1. git clone https://github.com/NasalDaemon/iter.git --recurse-submodules
2. Add iter/include and iter/extern/extend/include to your include path
3. Enable C++20
4. #include "iter/adapters/zip.hpp" (include whichever headers you need: each iter function is in its own header). #include "iter/iter.hpp" to include all iter functionality

Compiler support

GCC 10+, Clang 12+, MSVC 19.27+.

Propaganda

Integrates non-intrusively with existing standard library containers and range-based for loops.

void multiply(std::vector<float> const& x, std::vector<float> const& y, std::vector<float>& z) {
  for (auto [a, b, c] : iter::zip(x, y, z)) {
    c = a * b;
  }
}

All iters can be used with the range-based for-loop syntax sugar, but they aren't standards conformant ranges that can be used with standard algorithms. To convert an iter to a proper input range that conforms to the std::ranges::range concept, use iter::to_input_range(it). That input range can be used with std::ranges adaptors and algorithms that support input iterators.

Supports UFCS-style syntax via the extend library.

Since people like to write functional algorithms in many different styles, functions in the iter namespace support a wide range of calling styles. In practice, you will use only a subset corresponding to your preferred style.

Calling style	Notes
iter::map(it, mapper)	Simple free function syntax
iter::wrap(it).map(mapper)	Wraps an iter::iterable it to enable method style calls. Since iter::map(it) returns an iter::iter, it is also wrapped.
it | iter::sum()	Unary call to iter::sum(it)
it | iter::map(_, mapper)	Calls iter::map(it, mapper)
mapper | iter::map(it, _)	Calls iter::map(it, mapper)
it | iter::map | mapper	Binary call to iter::map(it, mapper)
it | iter::sum | _	Unary call to iter::sum(like)
it $(iter::map) (mapper)	After including extend dollar macros header.
it $map (mapper)	After including iter dollar macros header.

void multiply(std::vector<float> const& a, std::vector<float> const& b, std::vector<float>& c) {
  a | iter::zip | b
    | iter::zip | c // for convenience -- equivalent to: a | iter::zip(_, b, c)
    | iter::foreach | [](auto& abc) {
        auto& [a, b, c] = abc;
        c = a * b; };
}

Functionality and nomenclature similar by existing functional iterator libraries in other languages, such as rust, python, scala.

foreach,map,flatmap,range,generator,compound,once,repeat,chain,enumerate,enumerate_map,zip,zip_map,unzip,fold,reduce,filter,take,take_while,skip,skip_while,inspect,collect,partition,sorted,last,min,max,find_linear,any,all,map_while,filter_map,chunks,window,split

float weighted_sum(std::vector<float> const& a) {
  return a
    | iter::enumerate()
    | iter::map | [](auto ai) {
        auto& [a, i] = ai;
        return a * i; }
    | iter::sum();
}

Extending existing classes with iter functionality

There are two fundamental concepts: iter::iter and iter::iterable.

An iter is anything that can be passed as the only argument to iter::traits::next(...), which should return either iter::item<T> for an optional value or iter::item<T&> for an optional reference. iter::item<T> is analagous to std::optional<T> and iter::item<T&> is analogous to T*, but with the same interface as iter::item<T>.

An iterable is anything that can be passed to iter::to_iter(...) and returns an iter. Anything that is an iter is also an iterable (since there is a default implementation of iter::to_iter for iter arguments which simply returns the argument back).

All adaptors, collectors, and consumers operate on iterable or iter.

Informally, an iter should be cheap to copy -- at least before any iteration has started. For example:

1. The iter for std::vector contains only a pointer to the source vector and the current position. This is always cheap to copy.
2. The iter adaptor for a flatmap callable returning a std::vector<std::string> by value stores a iter::item<std::vector<std::string>> of the latest vector returned by the callable. The item is only populated once iteration has started, making copying cheap until then.
3. All iter adaptors with callables are to be as cheap to copy as their respective callables are. It is up to the user code to ensure that the callables are cheap to copy if the iter is expected to be copied around.
4. There is an iter::owning_iter which owns a container, but disables copies and moves at runtime. This is enforced at the linker stage, so that if the compiler can optimise away all the copies/moves then the code is allowed to compile. This class can always be used in constexpr contexts, as any potential copies/moves are done only at compile-time.

To make any type an iter, you simply define the relevant iter::traits::next implementation for it using the helper macro ITER_IMPL_NEXT.

struct enumerate_until {
  int max;
  int i = 0;

  using this_t = enumerate_until;
  constexpr auto ITER_IMPL_NEXT (this_t& self) {
    return self.i < self.max ? iter::item(self.i++) : iter::noitem;
  }
};

To make any type an iterable, you simply define the relevant iter::to_iter implementation for it using the helper macro ITER_IMPL(to_iter).

// { global namespace }
// Makes all ints "iterable" via enumerate_until (probably not a good idea)
constexpr auto ITER_IMPL(to_iter) (int max) {
  return enumerate_until{max};
}

Is iter a drop-in replacement for std::ranges?

Not quite, and it doesn't aim to be. iter aims to do one thing, and one thing well: provide a simple functional interface to consume iterable things without adding run-time or compile-time overhead. It does this by avoiding the standard C++ iterator concept in favour of a simpler iter::iter concept. On the other hand, std::ranges builds on standard iterators while attempting to hide away their complexities, offering useful concepts and algorithms for existing standard containers and iterators. In other words, std::ranges offers a wider scope of functionality than iter. That wider scope necesarily comes at the cost of complexity, bloat and often poorer performance in the subset of things that iter does specialise in.

The extremely simple iter::iter concept, which iter builds upon, has only one requirement: iter::traits::next(it) optionally returns the next item of it. Items are consumed one after the other until no item is returned. This greatly simplifies the implementation of this library's many components, scales extremely well, and greatly helps the compiler to optimise things away -- but it also precludes implementing certain algorithms. For example, any algorithm that accesses items in non-sequential order cannot be expressed using this concept. This includes algorithms such as: quicksort, in-place partition.

Anything that can use iter should use iter rather than std::ranges: iter has lower compile-time overhead and is also more likely to be better optimised by the compiler. However, anything that can't be represented with the simple iter::iter concept is out of scope for this library, and std::ranges deals with it perfectly well. std::ranges::sort(container) is simple enough!