Возвращает ли low_bound() один и тот же результат с обратными итераторами вектора в порядке возрастания и прямыми итераторами вектора в порядке убывания?
Если у меня есть 2 вектора, один в порядке возрастания, а другой в порядке убывания:
vector<int> inc{1,2,3,4,6,7}, dec{7,6,4,3,2,1};
Всегда ли следующие два выражения дают один и тот же результат? Или есть ли разница в их работе?
lower_bound(inc.rbegin(), inc.rend(), some_number, greater<int>()) // #1
lower_bound(dec.begin(), dec.end(), some_number, greater<int>()) // #2
Я чувствую, что они одинаковые, но во время недавнего конкурса на Codeforces один был принят, а другой нет.
@PepijnKramer Да, я это сделал... но, как я уже сказал, по моему мнению, они должны быть семантически эквивалентны, но во время недавнего контента на Codeforces один был принят, а другой нет. Пожалуйста, дайте мне знать, если я что-то упускаю. Спасибо!
Дайте определение понятию «эквивалент». По крайней мере, они дают результаты разных типов.
@IgorTandetnik Да, я понимаю, что он создает обратный итератор ... но кроме того, если я просто использую элемент, на который указывает этот возвращаемый указатель, всегда ли мы получаем один и тот же результат?
Честно говоря, я не ожидал разницы и не могу воспроизвести: onlinegdb.com/IT3xVq-5E (возможно, вам стоит показать больше кода, возможно, проблема где-то в другом месте)
Я вполне уверен, что (r1==inc.rend() && r2=dec.end) || *r1 == *r2 всегда должно быть четко определенным и истинным, если вы об этом.
Ответы 1
С точки зрения алгоритма, std::lower_bounds, нет никакой разницы, кроме типа итератора (один — обратный итератор, а другой — нет), но его это не волнует.
В обоих случаях он выполнит одни и те же алгоритмические шаги и вернет итератор, указывающий на элемент, который в обоих случаях несет одно и то же значение, или итератор end()/rend().
Единственное незначительное отличие может заключаться в скорости. Я ожидал, что версия, использующая обратные итераторы, будет немного медленнее, но я не измерял.
Таким образом, за исключением разницы в типе возвращаемого итератора и, возможно, одного из них медленнее другого, вы получите одинаковое значение из обеих версий.
Ради интереса, вот измерения быстрой скамьи для двух версий. Вы можете поиграть с диапазонами, чтобы увидеть, повлияет ли это на результат и если да, то каким образом. Чем ниже планка, тем быстрее. Синий цвет соответствует обратному итератору, а желтый — обычному итератору.
Вы намекаете на тот факт, что обратный итератор потребует некоторых дополнительных механизмов в коде (поэтому увеличение карт обратного итератора приведет к переходу назад по элементам вектора). При оптимизированной сборке я бы не ожидал какой-либо существенной разницы в производительности, и «не исключено», что производительность не будет иметь измеримой разницы.
@Питер Да, во всем этом. Неизвестно, пока не измеришь. Я добавил тест к ответу. В clang версия обратного итератора работает намного медленнее. В gcc не так сильно, но все же заметно.
Вы уже консультировались с cppreference? std::lower_bound и std::upper_bound. Если да, то что вам еще неясно? И каков результат вашего кода? Вы пробовали на своем компьютере?