Implementing a map_keys_iterator by derivation: a single compiler error

Question

Hi everyone.

I was working again with C++ during the weekend and came to notice something that I'm not sure where does it come from.

Following the advice in this thread, I decided to implement a map_keys_iterator and map_values_iterator. I took the -- I think -- recommended-against approach of deriving a class from std::map<K,V>::iterator and implementing it as such:

template <typename K, typename V>
struct map_values_iterator:
public std::map<K,V>::iterator {
  // explicitly call base's constructor
  typedef typename std::map<K,V>::iterator mIterator;
  map_values_iterator (const mIterator& mi) : 
  mIterator(mi) {};

  const V& operator* () const { return (*this)->second; }
};

So far, so good, and the following code works (nvm the Unicode, I default to work with i18n-capable terminals):

typedef std::map<double,string> Map;
Map constants;
constants[M_PI] = "π";
constants[(1+sqrt(5))/2] = "φ";
constants[exp(M_PI)-M_PI] = "fake_20";
// ... fill map with more constants!
map_values_iterator<double, std::string> vs(constants.begin());
for (; vs != m.end(); ++vs) { 
    cout<< (vs != m.begin() ? ", " : "")<< *vs;
    }
cout<< endl;

This code prints the expected result, something like (because a Map's elements are ordered):

..., φ, ..., π, ...., fake_20, ....

So I'd guess a map_keys_iterator would work in a similar way as well. I took the care that a Map's value_type is actually pair<const K, V> so the keys version will return a value.

However, it is unwieldly to have to declare the iterator's type so I wanted to create a caller with the classical make_pair-like idiom. And this is where trouble begins:

template <typename K, typename V>
map_values_iterator<K,V> map_values(const typename std::map<K,V>::iterator &i) {
    return lpp::map_values_iterator<K,V> (i);
}

template <typename K, typename V>
map_values_iterator<K,V> map_values(const typename std::map<K,V>::const_iterator &i) {
    return lpp::map_values_iterator<K,V> (i);
}

I'm relatively sure this function has the right signature and constructor invocation. However if I attempt to call the function from code:

auto vs= map_values(constants.begin());

I get a single STL compiler error of the form:

error: no matching function for call to ‘map_values(std::_Rb_tree_iterator<std::pair<const double, std::basic_string<char, std::char_traits<char>, std::allocator<char> > > >)’

I'm assuming here that in this particular case the whole _Rb_tree_iterator is actually the correct iterator for which map::iterator is typedefed; I'm not completely sure however. I've tried to provide more overloads to see if one of them matches (drop the reference, drop the const, use only non-const_iterator variants, etc) but so far nothing allows the signature I'm interested in.

If I store the base iterator in a variable before calling the function (as in auto begin= constans.begin(); auto vs= map_values(begin);) I get the exact same base error, only the description of the unmatched call is obviously different (in that it is a "const blah&").

My first attempt at implementing this sort of iterator was by creating a base class that aggregated map::iterator instead of inheriting, and deriving two classes, each with the adequate operator*, but that version ran into many more problems than the above and still forced me to replicate too much of the interface. So I tried this option for code-expedition.

I've tried to look for answers to this issue but my Google-fu isn't very strong today. Maybe I am missing something obvious, maybe I forgot something with the derivation (although I'm almost sure I didn't -- iterators are unlike containers), maybe I am actually required to specify all the template parameters for the map, or maybe my compiler is broken, but whatever it is I can't find it and I am having real trouble understanding what is the actual thing the compiler is complaining about here. In my previous experience, if you are doing something wrong with the STL you are supposed to see a diarrhoea of errors, not only one (which isn't STL to boot).

So... any (well-encapsulated) pointers would be appreciated.

Answer 1

The reason is that your K and V type parameters are in a non-deducible context, so your function template is never even instantiated during overload resolution.

Look at it again:

template <typename K, typename V>
map_keys_iterator<K,V> map_keys(const typename std::map<K,V>::iterator &i)

For this to work, the C++ compiler would somehow have to walk from a specific iterator class to its "parent container" type - map in this case - to get its K and V. In general, this is impossible - after all, a particular iterator might be a typedef for some other class, and the actual type of argument in the call is that other class; there's no way the compiler can "retrace" it. So, per C++ standard, it doesn't even try in this case - and, more generally, in any case where you have typename SomeType<T>::OtherType, and T is a type parameter.

What you can do is make the entire parameter type a template type parameter. This requires some trickery to derive K and V, though.

template <typename Iterator>
map_keys_iterator<
     typename std::iterator_traits<Iterator>::value_type::first_type,
     typename std::iterator_traits<Iterator>::value_type::second_type
> map_keys(Iterator i)

Unfortunately, you'll have to repeat those two in the body of the function as well, when invoking the constructor of your type.

As a side note, iterators are generally passed by value (they're meant to be lightweight).