Сложность алгоритма std :: includes в c ++

Question

Алгоритм std::includes берет два отсортированных диапазона и проверяет, входит ли set2 в set1 (т. Е. Входит ли каждый элемент set2 в set1)?

Интересно, почему eel.is / c ++ draft говорит, что сложность этого алгоритма составляет не более 2·(N1+N2-1) сравнений?

То же самое указано в:
1. cppreference
2. cplusplus

Мне кажется, что это должно быть только самое большее 2·N1 сравнений, с наихудшим случаем, когда max(set2) >= max(set1).

Answer 1

Я согласен с вашим выводом.Пример с перемежением из Ответ Аки Суйхконена неверен, поскольку алгоритм выйдет рано, как только 2 < 3.

В примере реализации cppreference есть цикл, который увеличивает first1 на каждомитерация, возвращается, когда first1 == last1, выполняет не более 2 сравнений за итерацию и не содержит вложенных циклов.Я не понимаю, как это могло бы сделать больше чем 2xN1 сравнений.

Answer 2

Я создал выпуск на github стандарта C ++.Об этом идет небольшой разговор с Ричардом Смитом из комитета по стандартам ISO C ++.

С самого начала он отказался от вопроса о путанице в отношении намерения std::includes.Но в конце концов согласился, что сложность функции должна быть пересмотрена после уточнения ее спецификации:

Требования к сложности соответствуют текущему описанию и должны быть исправлены, если / когда описание исправлено, чтобы фактически описать, что такоеалгоритм "должен" делать. Похоже, что LWG уже работает. Я отвечу на этот поток lib, чтобы попросить пересмотреть сложность, когда спецификация будет исправлена.

Answer 3

Для чередующихся наборов, например, 1,3,5,7 ..., 2,4,6,8, ..., необходимо сравнить первый элемент каждого набора на равенство, а когда это не удается, можнопотреблять меньший элемент из отсортированной очереди.Другой способ - сначала сравнить a<b, затем b<a, предполагая, что доступен только оператор меньше.В любом случае это приводит к сложности 2 (N1 + N2 + c).

Этот анализ сложности может измениться с введением трехстороннего сравнения <=> с (N1 + N2-1).

РЕДАКТИРОВАТЬ: да, вы правы.Алгоритм продвигает первый указатель в каждой итерации и останавливается, когда первый указатель / итератор достигает конца.Таким образом, будет максимум N итераций.Это не зависит от шагов, необходимых для продвижения итератора2.Ошибка в примере алгоритма, который не обрабатывает случаи set1 = {1,2,3}, set2 = {3,3,3, X} с повторениями.