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

std::lower_bound(it, end, v) needs to be able to do both *it < v and v < *it. Your function object supports only one of these.

Since there is a comment on this, leaving the above statement: This isn't the case. As Howard pointed out, the comparison is required to use comp(*it, v), i.e., there is no need for this operation to be symmetric.

However, looking at the documentation of boost::zip_iterator<It0, It1> it seems that *it yields a boost::tuple<typename It0::reference, typename It1::reference>. Thus, adding the typedef

typedef boost::tuple<typename std::vector<Key>::reference,
                     typename std::vector<Value>::reference> the_reference_tuple;

... and changing the lambda to become

[](the_reference_tuple const& it, int v) { return it.get<0>() < v; }

solves the compilation issues using gcc and clang.

Answer 2

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.