Определено ли это, чтобы предоставить пустой диапазон стандартным алгоритмам C ++?

Question

Исходя из моего предыдущего вопроса , можем ли мы доказать , что стандарт позволяет передавать пустой диапазон стандартному алгоритму?

Пункт 24.1 / 7 определяет «пустой диапазон» как диапазон [i,i) (где i действителен), и i может показаться «достижимым» от самого себя, но я не уверен, что это соответствуеткак доказательство.

В частности, мы сталкиваемся с проблемами при просмотре функций сортировки.Например, std::sort:

Сложность: O(N log(N)) (где N == last - first) сравнений

С log(0)обычно считается неопределенным, и я не знаю, что такое 0*undefined, может быть здесь проблема?

---

^{(Да, хорошо, я немного педантиченКонечно, ни одна уважающая себя реализация stdlib не вызовет практической проблемы с пустым диапазоном, переданным в std::sort. Но мне интересно, есть ли здесь потенциальная дыра в стандартной формулировке.)}

Answer 1

Обозначение Big-O определяется в терминах предела функции. Алгоритм с фактическим временем работы g(N) равен O(f(N)) тогда и только тогда, когда lim N→∞ g(N)/f(N) является неотрицательным действительным числом g(N)/f(N) меньше некоторого положительного действительного числа C для всех значений N больше некоторой константы k (точные значения C и k несущественны; вам просто нужно найти любой C и k, что делает это правдой). (спасибо за исправление, Джесси!)

Вы заметите, что фактическое количество элементов не имеет отношения к анализу big-O. Анализ Big-O ничего не говорит о поведении алгоритма для небольшого числа элементов; следовательно, не имеет значения, если f(N) определено в N=0. Что еще более важно, фактическое поведение во время выполнения управляется другой функцией g(N), которая вполне может быть определена в N=0, даже если f(0) не определено.

Answer 2

Мне не кажется, много места для вопроса. В § 24.1 / 6 нам говорят:

Итератор j называется достижимым из итератора i тогда и только тогда, когда существует конечная последовательность применений выражения ++ i, которая делает i == j.

и в $ 24,1 / 7:

Диапазон [i, j) действителен тогда и только тогда, когда j достижим из i.

Поскольку 0 конечно, [i, i) является допустимым диапазоном. § 24.1 / 7 продолжает:

Результат применения функций в библиотеке к недопустимым диапазонам: не определено.

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

Answer 3

Помимо соответствующего ответа, данного @bdonlan, обратите внимание также, что f(n) = n * log(n) имеет четко определенный предел, когда n стремится к нулю, а именно 0. Это связано с тем, что логарифм расходится медленнее, чем любой многочлен, в частности медленнее, чем n. Так что все хорошо: -)