Dereference template class

Usually, C++ standard library algorithms have two versions, e.g.:

template
void sort( RandomIt first, RandomIt last );

template
void sort( RandomIt first, RandomIt last, Compare comp );

Where one version is default in some sense and the second one is customized.

When I write my own algorithms, I use the following approach:

Let us suppose that I want to write a flexible algorithm that computes the average value. The standard C++ approach would be to write 2 algorithms:

template
double average( RandomIt first, RandomIt last );

template
double average( RandomIt first, RandomIt last, TGetValue getValue );

where getValue is something that obtains the value to be averaged from the object pointed to by the iterator.

But what if we have an iterator that loses some information when dereferenced? For example, let us consider std::map::iterator. This iterator results in a reference to a std::pair, but some iterators such as QMap::iterator return a reference to TValue. That is, after we dereference QMap::iterator, we lose the ability to examine the TKey. Here some flexibility is lost:

QMap map;
...
double averageOfKeys = average(map.begin(), map.end(), ???);

It is impossible to compute the average of keys using this interface, since the getValue object expects the thing pointed to by the iterator, which has the type of the second template parameter. There is no way we can get the key, which is of type int, from the value, which is of type double.

But the iterator itself can be used to get both the key and the value, using the iterator::key() and iterator::value() member functions. All we need to do is to change the interpretation of the getValue functor to expect an iterator instead of a thing pointed to by the iterator:

QMap map;
...
using iterator = QMap::const_iterator;
double averageOfKeys = average(map.begin(), map.end(), 
                               [](iterator it){return it.key();});

So I made thi

That's definitely an interesting approach. However, I would say that this interface is trying to accomplish too much. That is, average should just be responsible for calculating the average value over some range [first, last) and not worry about any indirection. E.g., only provide the signature

template
double average( InputIterator first, InputIterator last );

Note that I've changed your RandomIt to an InputIterator since I think this is a better choice.

Any indirection should instead be handled with iterator transformation. I.e., an adapter which wraps the raw QMap::iterator and overrides operator *() to either return the key or the value. Boost has the boost::transform_iterator which does exactly that. Even more concretely, there is also the boost::indirect_iterator which is very similar to your Dereference class.

Again, the motivation is to divide up the responsibility into separate classes so that each such class is as simple as possible. Complex tasks are then accomplished by combining these separate classes.

All that being said, let me review the code that you already have written. Because, like I said, it is still an interesting approach!

-
Use InputIterator instead of RandomIterator as the template parameter for average. InputIterator is more generic and is all you need to compute the average value of a range. When C++ gets ConceptsLite, this will make even more sense.

-
average always returns double. What about float ranges? Use a trailing return type together with iterator_traits to get the value type of the iterator instead. E.g.,

template
auto average( InputIterator first, InputIterator last )
    -> typename iterator_traits::value_type;

In C++14 this is even simpler as you can simply drop the trailing return type.

-
Prefer using over typedef. They accomplish the same thing but using is more powerful.

Besides that, the code looks fine to me. Good job! Please also consider the alternative I wrote in the first part of this post.

Edit: I recently read D4128: Ranges for the Standard Library: Revision 1 by Eric Niebler which proposes to overload all algorithms with Projection callables exactly as you did. Note that the very same proposal also includes Range Transform View which is an analogue to the iterator transforms I mentioned. That is, Projections and Range Transform Views coexist and serve slightly different purposes. You can read the proposal to get all the details.

In short, a future C++ standard may include a feature which is very similar to your suggestion. It may even come sooner than C++17 in the shape of a TS.

StackExchange Code Review Q#68726, answer score: 7