Dereference template class
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&lt; class InputIterator &gt;
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&lt; class InputIterator&gt;
auto average( InputIterator first, InputIterator last )
    -&gt; typename iterator_traits&lt;InputIterator&gt;::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.