zip_iterator and lower_bound

Question

I can't figure out how to call lower_bound with a zip_iterator.

This won't compile:

#include <boost/iterator/zip_iterator.hpp>
#include <vector>
#include <algorithm>

void main()
{
    typedef int Key;
    typedef double Value;

    typedef boost::tuple<typename std::vector<Key>::iterator,
                         typename std::vector<Value>::iterator> the_iterator_tuple;
    typedef boost::zip_iterator<the_iterator_tuple> the_zip_iterator;

    std::vector<Key>   keys_;
    std::vector<Value> values_;

    // Add values to keys_ and values_...

    auto it = std::lower_bound(
        the_zip_iterator(the_iterator_tuple(keys_.begin(), values_.begin())),
        the_zip_iterator(the_iterator_tuple(keys_.end(), values_.end())),
        123,
        [](const the_iterator_tuple & it, const int v) -> bool { return *boost::get<0>(it) < v; }
    );

    // Use "it"...
}

VS2010 says it "cannot convert parameter 1 from 'int' to 'const std::_Vector_iterator<_Myvec> &'" (plus several dozen other things for the same error), but it has to do with an obscure boost::tuple constructor, not with the given lambda.

What am I doing wrong ?

Answer 1

This looks like a "concepts checking" bug in VS2010.

25.4.3.1 [lower.bound]/p1:

Requires:: The elements e of [first,last) shall be partitioned with respect to the expression e < value or comp(e, value).

I.e. only *it < v is required.

The upper_bound algorithm has the opposite requirement: v < *it. And equal_range requires both expressions to work.