Friday 28 June 2013

The joy of type deduction

I've been following Alexander Stepanov's A9 lectures. It has been a good way to work on some fundamental algorithms (and it's also a great reminder that fundamental != basic).

I'm on lecture 5, and I had just designed my own algorithm for minmax_element(...), and wanted to measure it against the lecture's algorithm. So, I fired Qt Creator, created a new project, added the lecture files, built and... Boom!

c:\dev\qt\qt5.0.1\tools\mingw\bin\../lib/gcc/i686-w64-mingw32/4.7.2/include/c++/bits/stl_pair.h:180:4: error: no match for 'operator=' in '((std::pair<__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int, std::allocator<long long unsigned int> > >, __gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int, std::allocator<long long unsigned int> > > >*)this)->std::pair<__gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int, std::allocator<long long unsigned int> > >, __gnu_cxx::__normal_iterator<long long unsigned int*, std::vector<long long unsigned int, std::allocator<long long unsigned int> > > >::first = std::forward<long long unsigned int*>((* & __p.std::pair<long long unsigned int*, long long unsigned int*>::first))'

As is often the case with C++, depending on what compiler/compiler version you're using, attempting to compile the same code may lead to strange and wondrous results. In order to get another point of view, I attempted to build the same code on VC11 (VS2012); and, lo and behold... I got the same result. Although, the error message was, to put it mildly, ever so slightly saner:

1>c:\program files (x86)\microsoft visual studio 11.0\vc\include\utility(190): error C2679: binary '=' : no operator found which takes a right-hand operand of type 'unsigned __int64 *' (or there is no acceptable conversion)

Ah, here we have two C++ compilers that are complaining about the exact same thing (albeit with differing levels of whinin... er, I mean, verbosity). So much for my "The world's an oyster filled with mismatched pearls" chaos theory.

Anyway, let's follow the invocations, shall we? It all starts here:

std::pair<double, double> result = 
    minmax_times(buffer.begin(), buffer.end(), n / i);


Which calls a function with this definition:

template <typename I> 
std::pair<double, double> minmax_times(I first, I last, size_t iterations)

So, I is a vector iterator. Then, we get this:

std::pair<I, I> m0, m1;
...
m0 = minmax_element_simple((&*seq.begin()) + i * n, 
(&*seq.begin()) + (i + 1) * n, std::less<T>());
...
m1 = course::minmax_element((&*seq.begin()) + i * n,  
    (&*seq.begin()) + (i + 1) * n, std::less<T>());
 

BTW, the course:: qualifier on minmax_element(...) was something I had to add, because both compilers (again, conspiring to destroy my chaotic view of the world) complained about ambiguity between course::minmax_element(...) and std::minmax_element(...).

Here's the declaration of minmax_element_simple(...):

template <typename I, typename Compare>
inline
std::pair<I, I> minmax_element_simple(I first, I last, Compare comp)

And here's the declaration of course::minmax_element(...):

template <typename I, typename Compare>
std::pair<I, I> minmax_element(I first, I last, Compare cmp)

This means, on the one hand, we have a simple iterator expression; on the other hand we have a more complex expression, where we're taking the address of a dereferenced iterator. I then changed it to this:

//std::pair<I, I> m0, m1;
...
auto m0 = minmax_element_simple((&*seq.begin()) + i * n, 
(&*seq.begin()) + (i + 1) * n, std::less<T>());
...
auto m1 = course::minmax_element((&*seq.begin()) + i * n,  
    (&*seq.begin()) + (i + 1) * n, std::less<T>());
...
//if (m0 != m1) std::cout << "Failed: different mins or maxs\n";

And it built.

Next, I did what I often do in cases like this, where I'm not completely grasping what's going on - I followed a hunch. The reasoning behind it was as follows:
  • The template functions weren't being called with explicit template arguments, so the compiler was doing type deduction.
  • This deduction was leading to different types on each side of the assignment, and that was causing the error. This was confirmed when I changed the definition from std::pair<I,I> to auto, thus allowing the compiler to apply the same type deduction to both sides of the assignment.
  • I couldn't easily change the expression in the invocation to minmax_element(...) and minmax_element_simple(...), but I could change the expression in the invocation to minmax_times(...).
So, I removed the autos, put everything back the way it was, and changed this, instead:

std::pair<double, double> result = 
minmax_times((&*buffer.begin()) + 0, (&*buffer.end()) + 0, n / i);


And, again, it built.

Next step: Figuring out what are the types of these different expressions.

I wish there was some tool to output what the compiler's doing when it's "hiding" all the complexity from the developer. It could even be a different - and slower - version of the compiler, with code included via optional compilation (thus keeping the normal compiler as fast as possible, which is what we all want, naturally). As someone whose large part of his day-to-day work is acting when things go wrong, I know the value of having information that allows us to quickly review the succession of events that led to a failure, rather than having to recreate those events based on incomplete information.

Of course, I can also accept the fact that I have to know these rules, in order to work with C++. That's my next step, as I want to know what's going here, and that's what I've been constantly doing - learning.

But these are not exclusive options. Actually, a tool like the one I mentioned above would improve such knowledge, by making it more easily available.

No comments:

Post a Comment