Можно ли использовать std:: upper_bound без базового контейнера?

У меня есть ряд целых чисел [start, end] и неубывающая монотонная функция f(i). Итак, концептуально, у меня есть неубывающая последовательность [f(start), f(start + 1), .. , f(end)]. Могу ли я использовать std::upper_bound в этой последовательности, чтобы найти первый элемент i в диапазоне, который содержит f(i) > some_value?

Концептуально, мне бы хотелось что-то вроде этого:

std::upper_bound(start, end + 1, some_value, [&](int lhs, int rhs) { 
    return f(lhs) < f(rhs);
});

Но это не скомпилируется, потому что start и end + 1 не соответствуют требованиям итераторов вперед.

Ответ 1

Короткий ответ - да, поскольку std::upper_bound работает с итераторами, а не с контейнерами. Но сами итераторы являются экземплярами соответствующего класса (например, std::vector<int>::iterator или whatnot).

Если вы создадите какой-то конкретный класс, который будет соответствовать требованиям ForwardIterator, которые не привязаны к какому-либо контейнеру, но все еще что-то означает (например, если вы хотите сгенерировать свою последовательность процедурно), он должен работать только хорошо.

Обратите внимание, что простое целое не будет делать трюк. С другой стороны, класс, объекты которого хранят значение вашей функции для определенного значения аргумента (с некоторыми дополнительными батареями), будет.

Ответ 2

В основном есть два ответа:
Будет ли он работать по стандарту или будет работать со всеми практическими реализациями STL?

По стандарту, как T.C. указали уже, существуют некоторые строгие требования к итераторам, тем более что *it должен вернуть ссылку (возможно, const) на value_type (которую мы будем удовлетворять, возвращая ссылку на член итератора), но нам также нужно, чтобы для it1 == it2, *it1 и *it2 были привязаны ссылки к одному и тому же объекту, что возможно только в том случае, если мы имеем отдельный объект для каждого числа в диапазоне.

Если вы хотите использовать эту идею на практике, я не верю, что реализация std::upper_bound или подобных методов фактически основывается на этом ссылочном равенстве, поэтому вы можете просто использовать класс, который инкапсулирует целое число как итератор, перегружая необходимые методы. Насколько я могу судить, boost::irange выполняет эти требования

Как вы можете видеть, это не строго стандартно, но я не вижу причин, почему любая реализация бинарного поиска должна полагаться на такие сильные требования для итератора, если базовое "хранилище" равно const.

Ответ 3

Нет, не практически, но да на практике, но нет, если вы хотите быть практичным.

Нет

upper_bound требует ForwardIterator. ForwardIterator требует, чтобы * возвращал фактическую ссылку и что, если два итератора равны, они ссылаются на один и тот же объект.

Не практически

Для итератора без контейнера для этого требуется безумно сложный итератор, который кэширует значения, возвращаемые им в общей глобальной карте. Чтобы сделать это практически практичным, обратите внимание, что требования итератора очень мало говорят о времени жизни упомянутой ссылки; поэтому вы хотите ссылаться на count и уничтожать упомянутые значения, поскольку итераторы, о которых идет речь, перестают существовать.

Такое решение требует синхронизации, глобального состояния и значительно дороже и сложнее, чем что-то вроде boost::integer_range. Ни один здравомыслящий человек не напишет об этом, кроме как упражнение, демонстрирующее, почему стандарт должен быть исправлен.

Но да на практике

Никакая разумная реализация upper_bound на самом деле не требует, чтобы рассматриваемые итераторы были полномасштабными итераторами вперед, за исключением тех, которые выполняют полные концептуальные проверки для проверки на соответствие стандарту (а не на то, что нужно фактическому алгоритму). Итераторы ввода со стабильностью возвращаемых значений почти наверняка это делают. В стандарте С++ такой концепции нет, а итератор пересылки - самая слабая категория итератора в стандарте, который его удовлетворяет.

Эта проблема, требующая надежных итераторов, подкрепляется контейнерами, по моему мнению, является недостатком стандарта. Бескамерные итераторы являются мощными и полезными, за исключением того, что они редко технически работают в стандартных контейнерах.

Добавление новых категорий итераторов оказалось проблематичным, потому что есть небольшой способ сделать это, не нарушая существующий код. Они заглядывали в него для непрерывных итераторов и записывали их как непрактичные (я не знаю всех подробностей того, что они пытались).

Добавление новых концепций итератора, которые не поддерживаются тегами, более вероятно, но, вероятно, придется ждать, пока понятия не станут частью языка С++, а не только стандартом; то экспериментирование с добавлением новых понятий становится чем-то, что вы можете указать в С++ вместо стандартного, что значительно упрощает.

Но нет, если вы хотите быть практичным

Это, однако, приводит к плохо сформированной программе, не требующей диагностики. Поэтому подумайте, стоит ли это; на самом деле может быть проще переопределить upper_bound, чем поддерживать программу, каждое из которых - это поведение undefined, и каждая компиляция во власти обновления компилятора.