Dereference template class

Question

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

template< class RandomIt >
void sort( RandomIt first, RandomIt last );
template< class RandomIt, class Compare >
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< class RandomIt >
double average( RandomIt first, RandomIt last );
template< class RandomIt, class TGetValue >
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<TKey, TValue>::iterator. This iterator results in a reference to a std::pair<TKey, TValue>, 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<int, double> 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<int, double> map;
...
using iterator = QMap<int, double>::const_iterator;
double averageOfKeys = average(map.begin(), map.end(), 
 [](iterator it){return it.key();});

So I made this template class:

template <class T>
class Dereference
{
public:
 typedef decltype(*std::declval<T>()) TReference;
 typedef typename std::remove_reference<TReference>::type TValue;
 typedef typename std::remove_cv<TValue>::type TNonConstValue;
 TReference operator()(const T& t) const {return *t;}
};

To serve as a default argument in my algorithms. So for example for the average example, my algorithms would be:

template< typename RandomIt, typename TGetValue = Dereference<RandomIt> >
double average( RandomIt first, 
 RandomIt last, 
 TGetValue getValue = Dereference<RandomIt>() );

This increases the flexibility of the algorithm and reduces the need to have two overloads thanks to the default parameter.

Since I am new to programming in general and especially to C++11, I would like to ask:

1. If this is intuitive and usable.
2. If this can backfire in the future in some unexpected way.
3. If this approach can be improved somehow.

• Loki Astari: The Q document states for QMap::begin() That Returns an STL-style iterator pointing to the first item in the map. SO why is it non standard.
• mattnewport: I had the same question as Loki. I was going to say from your description that the QMap iterators are just incompatible with normal C++ iterator usage if they give you no way to access the key but my reading of the documentation is the same as Loki's - dereferencing the iterators gives you a pair of the key and value exactly as you'd expect with a regular std::map.
• Martin Drozdik: @LokiAstari Yes, that was a mistake. I edited my question to correct this.
• Martin Drozdik: @mattnewport I edited my question to remove the reference to the standard. Nevertheless, the iterator does not return a pair when dereferenced.
• Frederik Aalund: @MartinDrozdik, I've made an edit to my answer that you might find interesting.

Answer 1

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< class InputIterator >
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< class InputIterator>
  auto average( InputIterator first, InputIterator last )
   -> typename iterator_traits<InputIterator>::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.