Как выполнить двоичный поиск в std::vector, НО, который возвращает RandomAccessIterator?
Я ищу log2(N) способ поиска std::vector и получения RandomAccessIterator. Я хочу, чтобы он работал точно так же, как std::lower_bound(), но возвращал RandomAccessIterator вместо ForwardIterator.
Мне нужен результат первого поиска std::vector, чтобы определить поддиапазон большего второго std::vector. Я хочу использовать индекс из первого поиска для описания поддиапазона во втором векторе.
Я вообще не хочу делать никаких медленных линейных манипуляций типа std::distance. Производительность имеет решающее значение.
Каков наилучший способ добиться этого?
заранее спасибо
std::lower_bound на std::vector вернет std::vector::iterator, то есть RandomAccessIterator...
Это похоже на то, что сказал @Yksisarvinen. ForwardIterator, который вы можете увидеть в разделе «Разное». документация просто означает, что это должен быть как минимум прямой итератор, передаваемый алгоритму. Алгоритм вернет итератор того же типа, который вы ему передаете.
Кроме того, std::distance не является линейным для vector::iterator. Вместо этого он использует оператор - итератора. Для вектора v.begin() + index является итератором элемента по этому индексу, а iter - v.begin() возвращает индекс.
@infinitezero Вы не можете выполнять двоичный поиск с чем-то другим, кроме RandomAccessIterstor.
Ответы 2
Как упоминалось в комментариях, вы можете просто использовать std::lower_bound с std::vector, чтобы получить RandomAccessIterator.
std::lower_bound вызывает свой параметр шаблона итератора ForwardIt, потому что итераторы first и last должны быть как минимум прямыми (и в этом случае возвращается прямой итератор).
Но тип возвращаемого итератора соответствует типу first и last (поскольку внутри это результат манипулирования ими для поиска в диапазоне).
Для std::vector они будут иметь тип std::vector::iterator, который является RandomAccessIterator, и возвращаемое значение тоже будет таким же.
И RandomAccessIterator, и ForwardIterator являются именованными требованиями, а не типами. RandomAccessIterator включает в себя ForwardIterator, т. е. он соответствует всем требованиям ForwardIterator, а также некоторым дополнительным.
По этой причине каждый тип, удовлетворяющий требованиям RandomAccessIterator, также удовлетворяет требованиям ForwardIterator.
std::lower_bound — шаблонная функция. Он принимает пару итераторов определенного типа и возвращает итератор того же типа. Требуется, чтобы тип итератора удовлетворял как минимум ForwardIterator. Стандарт называет параметр типа ForwardIterator, поскольку он определяет требования алгоритмов по именам параметров.
Если параметр шаблона алгоритма имеет имя
ForwardIterator,ForwardIterator1илиForwardIterator2, аргумент шаблона должен удовлетворять требованиям прямого итератора.
Тип итератора, который вы получаете из std::vector, std::vector::iterator, должен удовлетворять RandomAccessIterator, и, следовательно, он удовлетворяет ForwardIterator.
Таким образом, вы можете передать пару std::vector::iterator в std::lower_bound и получить в результате std::vector::iterator.
Н.б. std::distance не является линейной манипуляцией, когда вы передаете ему тип, удовлетворяющий RandomAccessIterator:
Эффекты: Если
InputIteratorсоответствует требованиям итератора произвольного доступа, возвращается(last - first); в противном случае возвращает количество приращений, необходимое для перехода отfirstкlast.
Каков наилучший способ добиться этого?
std::lower_bound. Технически стандарт не требует, чтобы реализации эффективно перемещались между элементами, но все основные из них требуют, чтобы им были присвоены RandomAccessIterators.
Я бы назвал их «именованными требованиями» или что-то в этом роде, чтобы избежать путаницы с реальными концепциями.
Это похоже на XY-проблему, зачем вам RandomAccessIterator?