`std::flip`

std::flip is a little-known utility from the C++ standard library header <functional>: it is a higher-order function that accepts a Callable and returns an equivalent Callable with the order of its parameters reversed (or “flipped”).

To understand how it can be useful, let’s start with a simple example. Consider the following tree node class:

Let’s write a function that takes two nodes, and returns whether the first node is a parent of the second one, at any level of ancestry:

This is basically walking up the tree from the child node as if it were a linked list. The reverse operation either implies walking through two children nodes, or simply flipping the order of parameters, which is where std::flip intervenes:

Origins

std::flip finds its roots in functional programming, a domain in which it is extremely prevalent:

• Haskell has flip in its Prelude module.
• PureScript has flip in its Prelude module.
• OCaml has flip in the Fun module of its standard library.
• Idris has flip in its Prelude module.
• Elm used to have flip in its Basics module. It got removed, but lots of polyfills still provide it.

The LISP family of languages generally does not provide such a function by default, but the need is common enough that I have seen programmers online wonder how often it gets reimplemented manually.

Functional programming libraries in lots of other programming languages also generally oblige:

• Boost.Hana has boost::hana::flip.
• The C++ library FunctionalPlus provides a fplus::fwd::flip namespace.
• The Python library Toolz has toolz.functoolz.flip.
• The JavaScript library Ramda has flip.
• The TypeScript library fp-ts has flip in its function.ts module.
• The C# framework LanguageExt has flip in its Prelude class.

Interestingly enough, most of these implementations only flip the first two parameters of whichever function they are passed, though it seems to be because most of them are based on the Haskell prelude, and handling arbitrary arity can be tricky in that language. The existence of a module such as Data.Function.Flippers, which provides flip3, flip4, etc. functions up to nine parameters, without providing a generic “flip all” function only makes that argument stronger.

Closer to C++, D has std.functional.reverseArgs which reverses all parameters of the passed function.

Predicates

The most common use case for std::flip is certainly to flip the two arguments passed to a predicate, similar to what we did in the introduction example. As a matter of fact, it fits right with the standard library’s ordering predicates, allowing higher-order function transforms which mirror the tricks that have been used for decades to implement all relational operators on top of operator<:

Note: std::not_fn is another higher-order function from the <functional> header with a very similar design philosophy. It accepts a Callable and returns a new Callable that performs the negation of the wrapped one when called.

Use case: simple generic algorithms

Perhaps the simplest example of what std::flip brings to the table is the classic problem of sorting a collection in descending order according to a predicate:

Another fairly straightforward example is using it to reimplement std::upper_bound on top of std::lower_bound:

Interestingly enough, this implementation was not allowed in the original version of C++98 because Compare was required to satisfy the named requirement Compare, and T was required to satisfy LessThanComparable. Both of those require that the comparison models a strict weak ordering, which the piece of code above cannot satisfy because it breaks the asymmetry property:

• Asymmetry states that if compare(a, b) is true, then compare(b, a) is false.
• Assuming that compare satisfies this axiom, we can still have not compare(b, a) is true and not compare(a, b) is true when a == b.

The strict weak ordering requirement was lifted by LWG270, a defect report retroactively applied to C++98, making the implementation above legal now that the two algorithms only require that the collection be partitioned according to the predicate. However std::ranges::lower_bound and std::ranges::upper_bound reintroduced a strict weak ordering requirement via the std::indirect_strict_weak_order concept, rendering them unable to use the same implementation trick.

Use case: longest subsequences

A more involved example where std::flip and std::not_fn make code reuse and composition shine is that of the longest increasing subsequence problem. Quoting Wikipedia:

In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence’s elements are sorted in an ascending order and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous or unique.

The original problem statement is about finding a subsequence of strictly increasing values, though there are use cases for finding sequences of non-decreasing values instead, or of decreasing values. Here are two examples I encountered while working on my cpp-sort library

• Rem is a measure of presortedness that corresponds to the minimum number of elements to remove from a sequence to make it sorted. It is equal to the size of the sequence minus the size of its longest non-decreasing subsequence.
• SUS is another measure of presortedness corresponding to the minimum number of non-decreasing subsequences into which a sequence can be partitioned. It happens to match the size of the longest decreasing subsequence.

The following snippet of code uses boost::algorithm::longest_increasing_subsequence to compute the longest increasing subsequence, a feature of Boost.Algorithm that only exists in a seemingly abandoned pull request, then builds other flavours of the algorithm on top of it:

Let’s consider the following sequence:

\[\langle 1, 10, 2, 9, 2, 8, 8, 3, 7, 4, 5, 6, 6, 7, 5, 5, 8, 4, 9, 3, 9, 2, 10, 1 \rangle\]

Using the functions above gives the following results (double-checking their correctness is left as an exercise to whoever has doubts):

• LIS: \(\langle 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \rangle\)
• LDS: \(\langle 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 \rangle\)
• LNDS: \(\langle 1, 2, 2, 3, 4, 5, 6, 6, 7, 8, 9, 9, 10 \rangle\)
• LNIS: \(\langle 10, 9, 8, 8, 7, 6, 6, 5, 5, 4, 3, 2, 1 \rangle\)

This demonstrates that a combination of std::flip and std::not_fn constitutes a simple yet powerful tool to solve common computer science problems.

Use case: folds

Predicates might be the most obvious use case for std::flip, but its applicability goes well beyond those: it notably integrates nicely with folds, another staple of functional programming.

Let’s create a small collection of strings, and concatenate it with std::ranges::fold_left over std::plus:

We obtain the following sentence:

Using std::ranges::fold_left(vec, std::flip(std::plus{})), we can concatenate all elements in reverse order:

We can technically obtain the same results by left-folding std::plus over vec | std::views::reverse with no additional cost. However this reverse-based alternative stops working with containers such as std::forward_list, or with input ranges, the like of which are increasingly common with streaming interfaces.

Interestingly enough, std::flip and std::views::reverse also compose, and can even be used together to reimplement std::ranges::fold_right on top of std::ranges::fold_left:

Use case: inconsistent APIs

A more down-to-earth use case of std::flip is using it to glue together APIs that expose the same information in different orders. A classic example of such an inconsistency is geodetic systems:

• Some standards such as ISO 6709 (Standard representation of geographic point location by coordinates) describe points as (latitude, longitude).
• Others such as RFC 7946 (GeoJSON) describes points as (longitude, latitude).

Both are industry standards at this point, which means that any API that deals with coordinates follows either one or the other. The result is an ecosystem split between both orders. Libraries often provide Point abstractions, but functions accepting raw coordinate pairs are still prevalent.

It wouldn’t be surprising to find a map widget signaling the coordinates of a click through one of those systems, then having to bind that signal to a function from another library, expecting coordinates in the opposite order. In such a case, std::flip acts as simple glue:

Afterword

The more astute among you probably always went to cppreference to double-check what is, indeed, a lie: std::flip does not exist, making this whole article a mere piece of fiction. I hope you enjoyed the ride either way, and leanrt to appreciate the power of simple functional features if it wasn’t already the case.

Fortunately it is not just useless knowledge either: flip can be reified at will by copying the following C++17 implementation.

Note: the flip implementation above is provided under Creative Commons CC0 license.