zip_iterator и lower_bound

Question

zip_iterator и lower_bound

Я не могу понять, как позвонить lower_bound с zip_iterator,

Это не скомпилируется:

#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 говорит, что «не может преобразовать параметр 1 из int в const std :: _ Vector_iterator<_Myvec> &'»(плюс несколько десятков других вещей для той же ошибки), но это связано с неясным конструктором boost :: tuple, а не с данной лямбда-выражением.

Что я делаю неправильно ?

3

boost c++iterator lower-bound

Решение

Другие решения

Это похоже на «проверку концепции» в VS2010.

25.4.3.1 [lower.bound] / p1:

Требуется :: Элементы e из [first,last) должен быть разделен с
уважение к выражению e < value или же comp(e, value),

То есть только *it < v необходимо.

upper_bound Алгоритм имеет противоположное требование: v < *it, А также equal_range требует, чтобы оба выражения работали.

3

Источник

Accepted Answer

std::lower_bound(it, end, v) должен быть в состоянии сделать оба *it < v а также v < *it, Ваш функциональный объект поддерживает только один из них.

Так как есть комментарий к этому, оставляя вышеприведенное утверждение: это не так. Как отметил Говард, для использования требуется сравнение comp(*it, v)то есть нет необходимости, чтобы эта операция была симметричной.

Тем не менее, глядя на документацию boost::zip_iterator<It0, It1> Кажется, что *it дает boost::tuple<typename It0::reference, typename It1::reference>, Таким образом, добавляя typedef

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

… и изменяя лямбду, чтобы стать

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

решает проблемы компиляции, используя gcc и clang.

2