Algorithms

This module provides overloads of standard algorithms that leverage the internal structure of the immutable containers to provide faster iteration. These are drop-in replacements of the respective STL algorithms that can be a few times faster when applied on immutable sequences.

For further convenience they can be passed in just a container where the standard library algorithms require being passed in two iterators.

Note

They are a similar idea to structure-aware iterators but implemented using higher order functions in order to support structures of any depth. The downside is that this sometimes causes the compiler to generate bigger executable files.

---

AddedFn immer::differ::added

RemovedFn immer::differ::removed

ChangedFn immer::differ::changed

template <typename Range, typename Fn>

void immer::for_each_chunk(const Range &r, Fn &&fn)

Apply operation fn for every contiguous chunk of data in the range sequentially. Each time, Fn is passed two value_type pointers describing a range over a part of the vector. This allows iterating over the elements in the most efficient way.

Tip

This is a low level method. Most of the time, other wrapper algorithms should be used instead.

template <typename Iterator, typename Fn>

void immer::for_each_chunk(const Iterator &first, const Iterator &last, Fn &&fn)

template <typename T, typename Fn>

void immer::for_each_chunk(const T *first, const T *last, Fn &&fn)

template <typename Range, typename Fn>

bool immer::for_each_chunk_p(const Range &r, Fn &&fn)

Apply operation fn for every contiguous chunk of data in the range sequentially, until fn returns false. Each time, Fn is passed two value_type pointers describing a range over a part of the vector. This allows iterating over the elements in the most efficient way.

Tip

This is a low level method. Most of the time, other wrapper algorithms should be used instead.

template <typename Iterator, typename Fn>

bool immer::for_each_chunk_p(const Iterator &first, const Iterator &last, Fn &&fn)

template <typename T, typename Fn>

bool immer::for_each_chunk_p(const T *first, const T *last, Fn &&fn)

template <class Iter, class T>

T immer::detail::accumulate_move(Iter first, Iter last, T init)

template <class Iter, class T, class Fn>

T immer::detail::accumulate_move(Iter first, Iter last, T init, Fn op)

template <typename Range, typename T>

T immer::accumulate(Range &&r, T init)

Equivalent of std::accumulate applied to the range r.

template <typename Range, typename T, typename Fn>

T immer::accumulate(Range &&r, T init, Fn fn)

template <typename Iterator, typename T>

T immer::accumulate(Iterator first, Iterator last, T init)

Equivalent of std::accumulate applied to the range \( [first, last) \).

template <typename Iterator, typename T, typename Fn>

T immer::accumulate(Iterator first, Iterator last, T init, Fn fn)

template <typename Range, typename Fn>

Fn &&immer::for_each(Range &&r, Fn &&fn)

Equivalent of std::for_each applied to the range r.

template <typename Iterator, typename Fn>

Fn &&immer::for_each(Iterator first, Iterator last, Fn &&fn)

Equivalent of std::for_each applied to the range \( [first, last) \).

template <typename Range, typename OutIter>

OutIter immer::copy(Range &&r, OutIter out)

Equivalent of std::copy applied to the range r.

template <typename InIter, typename OutIter>

OutIter immer::copy(InIter first, InIter last, OutIter out)

Equivalent of std::copy applied to the range \( [first, last) \).

template <typename Range, typename Pred>

bool immer::all_of(Range &&r, Pred p)

Equivalent of std::all_of applied to the range r.

template <typename Iter, typename Pred>

bool immer::all_of(Iter first, Iter last, Pred p)

Equivalent of std::all_of applied to the range \( [first, last) \).

template <class AddedFn, class RemovedFn, class ChangedFn>

auto immer::make_differ(AddedFn &&added, RemovedFn &&removed, ChangedFn &&changed)

Produces a differ object with added, removed and changed functions.

template <class AddedFn, class RemovedFn>

auto immer::make_differ(AddedFn &&added, RemovedFn &&removed)

Produces a differ object with added and removed functions and no changed function.

template <typename T, typename Differ>

void immer::diff(const T &a, const T &b, Differ &&differ)

Compute the differences between a and b.

Changes detected are notified via the differ object, which should support the following expressions:

• differ.added(x), invoked when element x is found in b but not in a.
• differ.removed(x), invoked when element x is found in a but not in b.
• differ.changed(x, y), invoked when element x and y from a and b share the same key but map to a different value.

This method leverages structural sharing to offer a complexity \( O(|diff|) \) when b is derived from a by performing \( |diff| \) updates. This is, this function can detect changes in effectively constant time per update, as oposed to the \( O(|a|+|b|) \) complexity of a trivial implementation.

Note

This method is only implemented for map and set. When sets are diffed, the changed function is never called.

template <typename T, typename… Fns>

void immer::diff(const T &a, const T &b, Fns&&... fns)

Compute the differences between a and b using the callbacks in fns as differ. Equivalent to diff(a, b, make_differ(fns)...).

template <class AddedFn, class RemovedFn, class ChangedFn>

struct immer::differ

#include <algorithm.hpp>

Object that can be used to process changes as computed by the diff algorithm.

Template Parameters

• AddedFn: Unary function that is be called whenever an added element is found. It is called with the added element as argument.
• RemovedFn: Unary function that is called whenever a removed element is found. It is called with the removed element as argument.
• ChangedFn: Unary function that is called whenever a changed element is found. It is called with the changed element as argument.