# 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.

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.