Hi !
Today I am not going to talk about rendering. This article will deal with expressiveness in C++. Expressiveness? Yes, but about containers, range, and iterators.
If you want to know more about writing expressive code in C++, I advise you to go on fluentcpp.
If you want to know more about range, I advise you to take a look at the Range V3 written by Eric Niebler.
The code you will see may not be the most optimized, but it gives one idea behind what ranges are and how to implement it.
Introduction
How could we define a Range ?
The objective
Prior to defining what a Range is, we are going to see what Range let us do.
int main()
{
std::list<int> list;
std::vector<float> vector = {5.0, 4.0, 3.0, 2.0, 1.0, 0.0};
list << 10 << 9 << 8 << 7 << 6 << vector;
// list = 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
auto listFiltered = list | superiorThan(4) | multiplyBy(3);
// type of listFiltered = Range<You do not want to know lol>
// listFiltered = [10, 9, 8, 7, 6, 5] -> 30, 27, 24, 21, 18, 15
auto listSorted = Range::sort(listFiltered | superiorThan(23));
// type of listSorted is vector, else use Range::sort<std::list>
// listSorted = [30, 27, 24] -> 24, 27, 30
std::cout << list << listFiltered << listSorted;
return 0;
}
Isn’t it amazing to write things like that? Okay for direct operation inside the container, it could be better in two ways:
- It is not “easy” to read if you want to compose operation : (unique(sort(range)) is less readable than range | sort | unique in my opinion. But it is juste one “optimisation” to do :).
- It may be not optimized since sort returns a Container : here a vector, and build also.
The overloading of operator<< is quite easy though:
// writing
template<template<typename, typename...> class Container, typename T, typename ...A>
std::ostream &operator<<(std::ostream &stream, Container<T, A...> const &c) {
for(auto const &e : c)
stream << e << " ";
stream << std::endl;
return stream;
}
// Appending
template<template<typename, typename...> class Container, typename T, typename ...A>
Container<T, A...> &operator<<(Container<T, A...> &c, T const &v) {
c.emplace_back(v);
return c;
}
// Output must not be an ostream
template<template<typename, typename> class Output, template<typename, typename> class Input,
typename T1, typename A1, typename T2, typename A2>
std::enable_if_t<!std::is_base_of<std::ostream, Output<T1, A1>>::value, Output<T1, A1>&>
operator<<(Output<T1, A1> &o, Input<T2, A2> const &i) {
std::copy(i.begin(), i.end(), std::back_inserter(o));
return o;
}
template<template<typename, typename> class Output, template<typename> class Range,
typename T1, typename A1, typename Iterator>
std::enable_if_t<!std::is_base_of<std::ostream, Output<T1, A1>>::value, Output<T1, A1>&>
operator<<(Output<T1, A1> &o, Range<Iterator> const &i) {
std::copy(i.begin(), i.end(), std::back_inserter(o));
return o;
}
Okay, there are a lot of templates. I hope you will not get an allergy to them. All the lines that follow will use and abuse of templates and SFINAE.
The definition of a Range
A range is a way to traverse a container. They are at one abstraction above of iterators. To be simple, a Range own the first iterator, and the final one. It comes with a begin and one end function.
template<typename Iterator>
class _Range {
public:
using __IS_RANGE = void; // helper To know if the type is a range or not
public:
using const_iterator = Iterator;
using value_type = typename const_iterator::value_type;
explicit _Range(const_iterator begin, const_iterator end) : mBegin(begin), mEnd(end){}
const_iterator begin() const {return mBegin;}
const_iterator end() const {return mEnd;}
private:
const_iterator mBegin;
const_iterator mEnd;
};
template<typename T, typename = void>
struct is_range : std::false_type{};
template<typename T>
struct is_range<T, typename T::__IS_RANGE> : std::true_type{};
template<typename Iterator>
auto Range(Iterator begin, Iterator end) {
return _Range<Iterator>(begin, end);
}
template<typename Container>
auto Range(Container const &c) {
return Range(c.begin(), c.end());
}
Smart (Or proxy) iterator
Okay, now things are becoming tricky. I hope that I lost no one.
What exactly is an iterator ?
To be simple, an iterator is an abstraction of a pointer.
It exists several catetegories of iterators, to be simple, here is the list:
- input : They can be compared, incremented, and dereferenced as rvalue (output ones can be dereferenced as lvalue).
- Forward : not a lot of difference with the prior.
- Bidirectional: They can be decremented.
- Random Access : They support arithmetic operators + and -, inequality comparisons.
Smart Iterator in details
Lazy Initialization
This statement tells us “If the result of the operation is not needed right now, there is no need to compute it”. To be simple, the operation will be done when we will need to get the result. With iterator, it could be done when you dereference it for instance.
Different types of smart iterator
Filter iterator
This iterator will jump a lot of values that do not respect a predicate. For example, if you want only the odd values of your container, when you increment the iterator, it will advance until the next odd value and will skip all the even ones.
Transform iterator
This iterator will dereference the iterator, apply a function to the dereferenced value and returns the result.
Implementation
Basics
Here we are going to implement our own iterator class. This class must be templated twice times.
The first template argument is the iterator we want to iterate on. The second template argument is a tag that we use to perform a kind of tag dispatching.
Moreover, this iterator must behave as … an iterator !
So, we begin to write :
template<class Iterator, class RangeIteratorTagStructure>
class RangeIterator {
Iterator mIt;
RangeIteratorTagStructure mTag;
public:
using iterator_category = typename Iterator::iterator_category;
using value_type = typename Iterator::value_type;
using difference_type = typename Iterator::difference_type;
using pointer = typename Iterator::pointer;
using reference = typename Iterator::reference;
One of above typename will fail if Iterator does not behave like one iterator.
The Tag has a constructor and can own several data (function / functor / lambda), other iterators(the end of the range?) or other things like that.
The iterator must respect the Open Closed Principle. That is why you must not implement the methods inside the class but outside (in a namespace detail for instance). We are going to see these methods later. To begin, we are going to stay focused on the RangeIterator class.
Constructors
We need 3 constructors.
1. Default constructor
2. Variadic templated constructor that build the tag
3. Copy constructor
And we need as well an assignment operator.
RangeIterator() = default;
template<typename ...Args>
RangeIterator(Iterator begin, Args &&...tagArguments) :
mIt(begin),
mTag(std::forward<Args>(tagArguments)...) {
detail::RangeIterator::construct(mIt, mTag);
}
RangeIterator(RangeIterator const &i) :
mIt(i.mIt), mTag(i.mTag){}
RangeIterator &operator=(RangeIterator f) {
using std::swap;
swap(f.mIt, this->mIt);
swap(f.mTag, this->mTag);
return *this;
}
There are no difficulties here.
They also need comparison operators !
And they are quite easy !
bool operator !=(RangeIterator const &r) {
return mIt != r.mIt;
}
bool operator ==(RangeIterator const &r) {
return mIt == r.mIt;
}
Reference or value_type dereferencement
I hesitate a lot between return either a reference or a copy. To make transform iterator easier, I make the return by copy.
It means that you cannot dereference them as a lvalue :
*it = something; // Does not work.
The code is a bit tricky now because the dereferencement could not be the value you are waiting for. See the std::back_insert_iterator for instance.
decltype(detail::RangeIterator::dereference(std::declval<Iterator>(), std::declval<RangeIteratorTagStructure>())) operator*() {
return detail::RangeIterator::dereference(mIt, mTag);
}
decltype(detail::RangeIterator::dereference(std::declval<Iterator>(), std::declval<RangeIteratorTagStructure>())) operator->() {
return detail::RangeIterator::dereference(mIt, mTag);
}
Forward iterator to go farther !
Again, simple code !
RangeIterator &operator++() {
detail::RangeIterator::increment(mIt, mTag);
return *this;
}
Backward iterator, to send you in hell !
Okay, now as promised, we are going to see how beautiful C++ templates are. If you don’t want to be driven crazy, I advise you to stop to read here.
So, we saw that not all iterators have the “backward” range. The idea is to enable this feature ONLY if the iterator (the first template argument) supports it also.
It is the moment to reuse SFINAE (the first time was for the “is_range” structure we saw above).
We are going to use the type_trait std::enable_if<Expr, type>.
How to do that?
template<class tag = iterator_category>
std::enable_if_t<std::is_base_of<std::bidirectional_iterator_tag, tag>::value,
RangeIterator>
&operator--() {
detail::RangeIterator::decrement(mIt, mTag);
return *this;
}
You MUST template this function, else the compiler can not delete it !!!
FYI : If you have C++17 enabled, you can use concepts (at least for GCC).
Random iterator
Now you can do it by yourself.
But here some code to help you (because I am a nice guy :p)
template<class tag = iterator_category>
std::enable_if_t<std::is_base_of<std::random_access_iterator_tag, tag>::value, RangeIterator>
&operator+=(std::size_t n) {
detail::RangeIterator::plusN(mIt, n, mTag);
return *this;
}
template<class tag = iterator_category>
std::enable_if_t<std::is_base_of<std::random_access_iterator_tag, tag>::value, RangeIterator>
operator+(std::size_t n) {
auto tmp(*this);
tmp += n;
return tmp;
}
template<class tag = iterator_category>
std::enable_if_t<std::is_base_of<std::random_access_iterator_tag, tag>::value, difference_type>
operator-(RangeIterator const &it) {
return detail::RangeIterator::minusIterator(mIt, it.mIt, mTag);
}
template<class tag = iterator_category>
std::enable_if_t<std::is_base_of<std::random_access_iterator_tag, tag>::value, bool>
operator<(RangeIterator const &f) {
return mIt < f.mIt;
}
// Operator a + iterator
template<template<typename, typename> class RIterator, typename iterator, typename tag, typename N>
std::enable_if_t<std::is_base_of<std::random_access_iterator_tag, typename iterator::iterator_category>::value,
RIterator<iterator, tag>> operator+(N n, RIterator<iterator, tag> const &it) {
auto tmp(it);
tmp += n;
return tmp;
}
Details
Okay, now we are going to see what is hiden by detail::RangeIterator.
Normal iterators
In this namespace, you MUST put the tag and the function on it.
Here are the functions for normal iterator.
/*********** NORMAL ************/
template<typename Iterator, typename Tag>
inline void construct(Iterator , Tag) {
}
template<typename Iterator, typename Tag>
inline typename Iterator::value_type dereference(Iterator it, Tag) {
return *it;
}
template<typename Iterator, typename Tag>
inline void increment(Iterator &it, Tag) {
++it;
}
template<typename Iterator, typename Tag>
inline void decrement(Iterator &it, Tag) {
--it;
}
template<typename Iterator, typename Tag>
inline void plusN(Iterator &it, std::size_t n, Tag) {
it += n;
}
template<typename Iterator, typename Tag>
inline void minusN(Iterator &it, std::size_t n, Tag) {
it -= n;
}
template<typename Iterator, typename Tag>
inline typename Iterator::difference_type minusIterator(Iterator i1, Iterator const &i2, Tag) {
return i1 - i2;
}
It is simple, if it is a normal iterator, it behaves like a normal one.
Transform iterator
I will not talk about the filter iterator since it is not complicated to make it once we understand the ideas. Just be careful about the construct function…
The tag
So, what is a Transform iterator? It is simply one iterator that dereference the value, and apply a function to it.
Here is the Tag structure.
template<typename Iterator, typename Functor>
struct Transform final {
Transform() = default;
Transform(Functor f) : f(f){}
Transform(Transform const &f) : f(f.f){}
std::function<typename Iterator::value_type(typename Iterator::value_type)> f;
};
It owns one std::function and that’s it.
The usefulness of the transform iterator is when you dereference it. So you need to reimplement only the dereference function.
template<typename Iterator, typename Functor>
inline typename Iterator::value_type dereference(Iterator it, Transform<Iterator, Functor> f) {
return f.f(*it);
}
Thanks to overloading via tag dispatching this function should (must??) be called without any issues (actually you hope :p).
However, if you want to use several files (thing that I only can to advise you), you cannot do it by this way but specialize your templates. But you cannot partially specialize template function. The idea is to use functor!
Here is a little example using dereference function.
decltype(std::declval<detail::RangeIterator::dereference<Iterator, Tag>>()(std::declval<Iterator>(), std::declval<Tag>())) operator*() {
return detail::RangeIterator::dereference<Iterator, Tag>()(mIt, mTag);
}
// Normal iterator
template<typename Iterator, typename Tag>
struct dereference {
inline typename Iterator::value_type operator()(Iterator it, Tag) const {
return *it;
}
};
// Transform iterator
template<typename Iterator, typename Functor>
struct dereference<Iterator, Transform<Iterator, Functor>> {
inline typename Iterator::value_type operator()(Iterator it, Transform<Iterator, Functor> f) {
return f.f(*it);
}
};
The builder : pipe operator (|)
Okay, you have the iterator, you have the range class, you have your function, but now, how to gather them?
What you want to write is something like that:
auto range = vector | [](int v){return v * 2;};
First, you need a function that Create one range that own two iterators.
One that begins the set, and the other one that ends it.
template<typename Container, typename Functor>
auto buildTransformRange(Container const &c, Functor f) {
using Iterator = RangeIterator<typename Container::const_iterator,
detail::RangeIterator::Transform<typename Container::const_iterator, Functor>>;
Iterator begin(c.begin(), f);
Iterator end(c.end(), f);
return Range(begin, end);
}
Once you have that, you want to overload the pipe operator that makes it simple :
template<typename R, typename Functor>
auto operator|(R const &r, Functor f) -> std::enable_if_t<std::is_same<std::result_of_t<Functor(typename R::value_type)>, typename R::value_type>::value, decltype(Range::buildTransformRange(r, f))> {
return Range::buildTransformRange(r, f);
}
Warning : Don’t forget to take care about rvalue references to be easy to use !
Conclusion
So this article presents a new way to deal with containers. It allows more readable code and take a functional approach. There is a lot of things to learn about it, so don’t stop your learning here. Try to use one of the library below, try to develop yours. Try to learn a functional language and … Have fun !!!!
I hope that you liked this article. It is my first article that discuss only C++. It may contains a lot of errors, if you find one or have any problems, do not forget to tell me!
Reference
Range V3 by Eric Niebler : His range library is really powerfull and I advice you to use it (and I hope that it will be a part of the C++20).
Ranges: The STL to the Next Level : because of (thanks to?) him, I am doing a lot of modifications in all my projects… x).
Range Library by me : I will do a lot of modifications : Performance, conveniance and others.
Leave a Reply