An Alternative Design to Iterators and Ranges, Using std::optional
Today’s guest post is written by Vincent Zalzal. Vincent is a software developer working in the computer vision industry for the last 13 years. He appreciates all the levels of complexity involved in software development, from how to optimize memory cache accesses to devising algorithms and heuristics to solve complex applications, all the way to developing stable and user-friendly frameworks. You can find him online on Twitter or LinkedIn.
In a previous post, Jonathan presented what he calls the Terrible Problem Of Incrementing A Smart Iterator, or the TPOIASI. The problem occurs when an iterator that embeds logic in its operator++ is composed with another iterator that performs some computation in its operator*. The TPOIASI is prevalent in code using the new C++ Ranges or ranges-v3.
I was intrigued by the problem, and decided to try solving it. While Jonathan decided to move the logic to smart output iterators to solve the problem, I decided to change the definition of range altogether.
Motivating example
Here is an example of the problem, using ranges-v3:
#include <iostream>
#include <vector>
#include <range/v3/all.hpp>
int times2(int n) {
std::cout << "transform " << n << '\n';
return n * 2;
}
bool isMultipleOf4(int n) {
return n % 4 == 0;
}
int main() {
std::vector<int> numbers = { 1, 2, 3, 4, 5 };
std::vector<int> results; // output
ranges::push_back(results,
numbers | ranges::view::transform(times2)
| ranges::view::filter(isMultipleOf4));
for (auto result : results)
std::cout << result << ' ';
}
And here is the output:
transform 1 transform 2 transform 2 // transform called twice on 2 transform 3 transform 4 transform 4 // transform called twice on 4 transform 5 4 8
You can refer to Jonathan’s article for a detailed explanation of what’s going on. In summary, filter has to call both operator++ and operator* of the underlying iterator in its own operator++ to know when to stop, causing transform to apply its function (its operator*) twice per valid element: once in filter‘s operator++ and once in filter‘s operator*.
auto FilterIterator::operator++() {
do {
++curIt;
} while (curIt != endIt && !pred(*curIt));
return *this;
}
Suppose you are iterating over the filtered range like this:
for (auto it = filteredRange.begin(); it != filteredRange.end(); ++it) {
auto value = *it;
// use value
}
The transform function is first called while performing ++it to stop when the predicate is true, then it is called again right on the next line, in *it. Wouldn’t it be nice if we could reuse the function evaluation in ++it instead of calling *it?
Insight
Is it really necessary to have separate operations for advancing the iterator and evaluating its element?
If those two operations were to be merged into a single one, the spurious calls to the transform function would be avoided. Jonathan’s solution using smart output iterators is actually doing all the work in the output iterator’s operator=.
What if we could reinvent ranges from scratch without the need for low-level iterators? Could we leverage modern C++ features to iterate an input range with a single operation instead of two?
A Solution using std::optional
A solution is to represent an input range as a mutable view, i.e. a mutable structure that contains both the current position and the sentinel (the value returned by std::end). This way, we could define a single operation, let’s call it next, that would return either the next element, or std::nullopt if the end of the range is reached.
// Non-owning input view based on STL iterators
template <typename InputIt, typename Sentinel>
struct InputRange {
InputIt current;
Sentinel end;
using value_type = typename std::iterator_traits<InputIt>::value_type;
std::optional<value_type> next() {
if (current != end)
return *current++;
else
return std::nullopt;
}
};
I made the following design decisions to simplify the implementation:
- I only consider single-pass input ranges.
next()return copies of the values, because optional references are not allowed… yet.
The downside of such a range is its size: it is twice the size of an STL iterator. This is only important if you are storing iterators in memory, though, which, in my opinion, is often not the best design anyway.
The filtered range is as easy to define as for standard ranges, maybe even easier, and it solves the problem presented in the motivating example.
// Range which filters elements of another range, based on a predicate
template <typename Range, typename Pred>
struct FilteredRange {
Range range;
Pred pred;
using value_type = typename Range::value_type;
std::optional<value_type> next() {
while (const auto value = range.next())
if (pred(*value))
return value;
return std::nullopt;
}
};
Because next is performing both iteration and element evaluation, each element is evaluated exactly once.
The transformed range is even easier to define:
// Range which applies a transform to another range
template <typename Range, typename Func>
struct TransformedRange {
Range range;
Func func;
using value_type = decltype(func(*range.next()));
std::optional<value_type> next() {
if (const auto value = range.next())
return func(*value);
else
return std::nullopt;
}
};
With appropriate deduction guides, these structs are enough to implement the motivating example.
void withStructsOnly() {
std::vector<int> numbers = { 1, 2, 3, 4, 5 };
std::vector<int> results; // output
auto filteredRange = FilteredRange{
TransformedRange{
InputRange{numbers.begin(), numbers.end()},
times2
},
isMultipleOf4
};
while (const auto value = filteredRange.next())
results.push_back(*value);
for (const auto value : results)
std::cout << value << ' ';
}
No TPOIASI, success!
transform 1 transform 2 transform 3 transform 4 transform 5 4 8
Pipe syntax
I was happy with the result, but unsatisfied with the syntax. Under the encouragement of Jonathan, I implemented a basic mechanism to achieve a pipe syntax similar to the one in ranges-v3.
We would like to be able to replace this:
TransformedRange{SomeRange, times2}
by this:
SomeRange | transform(times2)
To achieve this, we must overload operator| to take any range as left-hand side operand, and an object returned by transform as right-hand side operand, that object temporarily holding the function to apply. Here is what it looks like, including the deduction guide for TransformedRange:
template <typename Range, typename Func>
TransformedRange(Range, Func) -> TransformedRange<Range, Func>;
template <typename Func>
struct TransformProxy {
Func func;
};
template <typename Func>
auto transform(Func&& func) {
return TransformProxy<Func>{std::forward<Func>(func)};
}
template <typename Range, typename Func>
auto operator|(Range&& range, TransformProxy<Func> proxy) {
return TransformedRange{std::forward<Range>(range), std::move(proxy.func)};
}
By doing the same thing for the filter function and adding a factory function to create the input range, we get this much nicer-looking code:
auto filteredRange = make_range(numbers) | transform(times2) | filter(isMultipleOf4);
Here is the full code listing. You can see it in action on Coliru.
#include <iterator> // for iterator_traits, begin, end
#include <optional>
#include <utility> // for forward, move
// Non-owning input view based on STL iterators
template <typename InputIt, typename Sentinel>
struct InputRange {
InputIt current;
Sentinel end;
using value_type = typename std::iterator_traits<InputIt>::value_type;
std::optional<value_type> next() {
if (current != end)
return *current++;
else
return std::nullopt;
}
};
template <typename InputIt, typename Sentinel>
InputRange(InputIt, Sentinel) -> InputRange<InputIt, Sentinel>;
// Factory function taking anything with begin/end support and returning a mutable view
template <typename T>
auto make_range(T&& c) {
return InputRange{std::begin(c), std::end(c)};
}
// Range which filters elements of another range, based on a predicate
template <typename Range, typename Pred>
struct FilteredRange {
Range range;
Pred pred;
using value_type = typename Range::value_type;
std::optional<value_type> next() {
while (const auto value = range.next())
if (pred(*value))
return value;
return std::nullopt;
}
};
template <typename Range, typename Pred>
FilteredRange(Range, Pred) -> FilteredRange<Range, Pred>;
// Range which applies a transform to another range
template <typename Range, typename Func>
struct TransformedRange {
Range range;
Func func;
using value_type = decltype(func(*range.next()));
std::optional<value_type> next() {
if (const auto value = range.next())
return func(*value);
else
return std::nullopt;
}
};
template <typename Range, typename Func>
TransformedRange(Range, Func) -> TransformedRange<Range, Func>;
// Pipe-syntax enabler structs and operator overloads
template <typename Func>
struct TransformProxy {
Func func;
};
template <typename Func>
auto transform(Func&& func) {
return TransformProxy<Func>{std::forward<Func>(func)};
}
template <typename Range, typename Func>
auto operator|(Range&& range, TransformProxy<Func> proxy) {
return TransformedRange{std::forward<Range>(range), std::move(proxy.func)};
}
template <typename Pred>
struct FilterProxy {
Pred pred;
};
template <typename Pred>
auto filter(Pred&& pred) {
return FilterProxy<Pred>{std::forward<Pred>(pred)};
}
template <typename Range, typename Pred>
auto operator|(Range&& range, FilterProxy<Pred> proxy) {
return FilteredRange{std::forward<Range>(range), std::move(proxy.pred)};
}
// Motivating example
#include <iostream>
#include <vector>
int times2(int n) {
std::cout << "transform " << n << '\n';
return n * 2;
}
bool isMultipleOf4(int n) {
return n % 4 == 0;
}
void withStructsOnly() {
std::vector<int> numbers = { 1, 2, 3, 4, 5 };
std::vector<int> results; // output
auto filteredRange = FilteredRange{
TransformedRange{
InputRange{numbers.begin(), numbers.end()},
times2
},
isMultipleOf4
};
while (const auto value = filteredRange.next())
results.push_back(*value);
for (const auto value : results)
std::cout << value << ' ';
}
void withPipeSyntax() {
std::vector<int> numbers = { 1, 2, 3, 4, 5 };
std::vector<int> results; // output
auto filteredRange = make_range(numbers) | transform(times2) | filter(isMultipleOf4);
while (const auto value = filteredRange.next())
results.push_back(*value);
for (const auto value : results)
std::cout << value << ' ';
}
int main() {
std::cout << "With structs only:\n";
withStructsOnly();
std::cout << "\nWith pipe syntax:\n";
withPipeSyntax();
}
STL algorithms and range-based for loop
You might wonder why I am not using std::copy to push back elements into the output vector, or why I create a temporary variable to hold the range. This is because InputRange, FilteredRange and TransformedRange do not play nicely with existing C++ features and libraries. The range-based for statement:
for (for-range-declaration : for-range-initializer) statement
is currently equivalent to:
{
auto &&__range = for-range-initializer ;
auto __begin = begin-expr ;
auto __end = end-expr ;
for ( ; __begin != __end; ++__begin ) {
for-range-declaration = *__begin;
statement
}
}
Let’s imagine an alternate universe where the range-based for loop would instead be based on next:
{
auto &&__range = for-range-initializer ;
while (auto __value = std::next(__range)) { // same as __range.next()
for-range-declaration = *__value;
statement
}
}
In this C++ fantasy land, STL algorithms would also have overloads taking such a range as first argument. Then, we would finally get this coveted version of the motivating example:
// Fantasy, this does not compile.
int main() {
std::vector<int> numbers = { 1, 2, 3, 4, 5 };
std::vector<int> results; // output
std::copy(make_range(numbers) | transform(times2) | filter(isMultipleOf4),
std::back_inserter(results));
for (const auto value : results)
std::cout << value << ' ';
// Or, without even using a temporary output vector:
for (const auto value : make_range(numbers)
| transform(times2)
| filter(isMultipleOf4))
std::cout << value << ' ';
}
Performance
You wouldn’t be a real C++ programmer if you weren’t caring about performance, would you? You will be happy to know that most recent compilers see through all the abstraction layers of proxy objects and std::optionals. gcc-trunk in particular generates almost the exact same code as a handwritten loop doing all computations inline, as can be seen on Compiler Explorer. Very impressive!
Note that, at the time of writing, gcc-trunk seems to be the only version of x86-64 gcc on Compiler Explorer to generate that code, so your mileage may vary.
Conclusion
In the book From Mathematics to Generic Programming, Alexander Stepanov and Daniel Rose describe the Law of Useful Return:
If you’ve already done the work to get some useful result, don’t throw it away. Return it to the caller. This may allow the caller to get some extra work done “for free”.
For example, since C++11, std::rotate returns an iterator to the new position of the previously-last iterator. Maybe it won’t be used, but it was already computed anyway.
In this article, I applied this programming principle to operator++ for filter iterators. When incrementing the iterator, its current value must be evaluated to determine if it satisfies the predicate or not. That evaluated value should be returned instead of being discarded.
By combining both operator++ and operator* into a single function, it is possible to both increment the iterator and return the evaluated value, thus avoiding the Terrible Problem Of Incrementing A Smart Iterator: evaluating the value twice. Moreover, I think any programmer that once implemented an iterator class will agree that it is not a trivial task, and implementing FilteredRange and TransformedRange above required quite less boilerplate code.
Thinking out of the box when solving toy problems may sometimes lead to interesting insights. I hope you had as much fun reading this article as I had fun writing it. Thanks to Tim van Deurzen for providing constructive feedback, and thanks to Jonathan for giving me the opportunity again of writing a guest post on his blog. Happy coding!
You will also like
- The Terrible Problem Of Incrementing A Smart Iterator
- Getting the Benefits of Strong Typing in C++ at a Fraction of the Cost
- How Smart Output Iterators Avoid the TPOIASI
- Smart Output Iterators: A Symmetrical Approach to Range Adaptors
Share this post!
