Поведение и работа алгоритма std::includes

149

22 июня 2019, 08:40

Недавно вопрос прозвучал про этот алгоритм. По стандарту он принимает отсортированные последовательности, но у меня всегда выдавал правильный результат и для неотсортированных множеств. Вот, например:

std::vector<int> a{1, 2, 5, 3, 11, 23, 12, 6};
std::vector<int> b{5, 3, 11};
if (std::includes(a.begin(), a.end(), b.begin(), b.end()))
    cout << b.back();  // вывод 11

И, на всякий случай, ссылка на стандарт: https://ru.cppreference.com/w/cpp/algorithm/includes Думаю, просто алгоритм быстрее работает для сортированных множеств, а не сортирует неотсортированные (или просто не требуется сортировка?). Пока не разобрался, хотелось бы получить от вас помощь(каков ваш ответ?...) Просто, чисто логично, сортировка тут не нужна вовсе...

Answer 1

У вас слишком хорошая последовательность выбрана... Попробуйте на

std::vector<int> a{1, 2, 5, 3, 23, 11, 12, 6};

Взгляните на примерную реализацию алгоритма по указанной вами ссылке, и все должно стать понятно, почему это так.

По законам логики из ложных посылок может вытекать как ложь, так и истина, так что верный результат еще не говорит о том, что он будет всегда :( А вот хоть один ложный показывает, что исходные посылки - ложны.

Answer 2

но у меня всегда выдавал правильный результат и для неотсортированных множеств

Вы что-то выдумываете. Поведение алгоритма std::includes на неупорядоченных последовательностях не определено, т.е. он вообще не работает на неупорядоченных последовательностях. Ваше "у меня всегда выдавал правильный результат" - это просто случайность (в которую, к тому же, трудно поверить).

Просто, чисто логично, сортировка тут не нужна вовсе

Отнюдь. Стандартная функция std::includes и остальные функции этой группы (std::set_difference, std::set_union и т.д.) для того и заведены, чтобы реализовать теоретико-множественные операции через хрестоматийный алгоритм синхронного прохода по двум отсортированным последовательностям. Без упорядоченности последовательностей эти алгоритмы не имеют смысла.