Простой вариант использования: я хочу найти с помощью бинарного поиска минимальный индекс i, для которого f(i)>=t, где t - некоторый порог, а f - монотонно возрастающая функция над целочисленными значениями.
Простой способ go состоит в том, чтобы просто вызывать эту функцию для каждого возможного ввода, сохранять ее в контейнере и затем использовать lower_bound, это будет полезно в сценарии, где я хочу выполнить несколько поисков для одного и того же функция с различными пороговыми значениями.
Однако в моем сценарии оценки функций являются дорогостоящими, и у меня есть несколько различных функций / лямбд, для которых я выполняю только один двоичный поиск.
Так что я предполагаю, что мне нужно, это либо lower_bound функция, принимающая функцию и диапазон значений вместо начального и конечного итераторов, либо мне нужен механизм, чтобы скрыть вызовы функций внутри структуры итератора. Я знаю, что первое решение легко реализовать, но я надеялся, что это решение поможет избежать реализации бинарного поиска с нуля.
Мне показалось, что это общий случай использования, но почему-то я ничего не смог найти по этому вопросу. особая проблема в сети. Буду признателен за любые советы, хитрости и ссылки.
РЕДАКТИРОВАТЬ
Я нашел два первых представленных решения очень интригующим. Данное решение с использованием аргумента comp очень элегантно, однако я забыл упомянуть причину, по которой этот подход не работает для меня. В дополнение к длительному времени выполнения для оценки одной функции у меня также есть проблема с большим пространством поиска (например, более 1022 * целых чисел), что делает нецелесообразным выделение фиктивного вектора для этой цели. Я не знаю, как это будет работать с boost итераторами приращений, но мне все равно нужно что-то для работы только с std.
Хотя второе решение с использованием пользовательского итератора довольно многословно. Я проверил это с большим числом, которое я упомянул (и изменил int s на long long s), но это, кажется, также медленно. Кажется, что lower_bound на самом деле вызывает operator++ несколько раз go из одного местоположения в другое, поэтому реализация std::lower_bound уже может быть убийцей для моего подхода здесь (см. Ниже пример измененного кода и вывод ) и нет никакой возможности обойти пользовательскую реализацию (которая у меня уже есть, здесь нет необходимости).
Спасибо, однако, за понимание, оба ответа показали мне что-то новое. И, может быть, кто-то может пролить немного света на упомянутые выше моменты, поскольку я определенно не эксперт по итераторам или реализации lower_bound, возможно, я использовал это неправильно или что-то в примере кода, приведенном @idclev, делает его итерируйте это неэффективно через числа, которые я не узнал.
Пример модифицированного кода
#include <iostream>
#include <unordered_map>
#include <algorithm>
long long foo(long long i){ std::cout << "function evaluation:\t" << i << std::endl; return i;}
using function_type = long long(*)(long long);
template <function_type F>
struct fun_iterator {
using difference_type = size_t;
using value_type = long long;
using pointer = int*;
using reference = int&;
using iterator_category = std::forward_iterator_tag;
static std::unordered_map<long long,long long> m;
long long index;
fun_iterator(long long index) : index(index) {}
fun_iterator& operator++() {
std::cout << "operator++:\t" << index << std::endl;
++index;
return *this;
}
fun_iterator operator++(int x) {
fun_iterator it = *this;
++index;
return it;
}
int operator*() {
auto it = m.find(index);
if (it != m.end()) return it->second;
auto res = F(index);
m[index] = res;
return res;
}
bool operator!=(const fun_iterator& other){
return index != other.index;
}
bool operator==(const fun_iterator& other){
return index == other.index;
}
bool operator<(const fun_iterator& other){
return index < other.index;
}
};
template <function_type F>
std::unordered_map<long long,long long> fun_iterator<F>::m;
template <function_type F>
std::pair<fun_iterator<F>,fun_iterator<F>> make_begin_and_end(long long begin,long long end){
return {{begin},{end}};
}
int main() {
auto x = make_begin_and_end<foo>(0,10L);
auto it = std::lower_bound(x.first,x.second,4L);
// auto x = make_begin_and_end<foo>(0,1000000000000L);
// auto it = std::lower_bound(x.first,x.second,400000000000L);
std::cout << it.index << std::endl;
}
и вывод:
operator++: 0
operator++: 1
operator++: 2
operator++: 3
operator++: 4
operator++: 5
operator++: 6
operator++: 7
operator++: 8
operator++: 9
operator++: 0
operator++: 1
operator++: 2
operator++: 3
operator++: 4
function evaluation: 5
operator++: 0
operator++: 1
function evaluation: 2
operator++: 2
operator++: 3
function evaluation: 4
function evaluation: 3
operator++: 3
4