Насколько умен std :: max_element ()?

Question

Предположим, у меня есть std::vector<int>:

std::vector<int> v;
[v is initialized]

, и я хочу получить максимальный элемент v. Для этого есть алгоритм:

int max_value = *std::max_element(v.begin(), v.end());

Пока все хорошо.

Теперь предположим, что v содержит 10 000 000 элементов, а его 10-й элемент равен std::numeric_limits<int>::max() . Собирается ли std::max_element() (без необходимости) проверять 9 999 990 последних элементов v или распознает, что не может быть элементов больше std::numeric_limits<int>::max(), и, таким образом, остановится после 10-го элемента?

Answer 1

Я не могу говорить обо всех реализациях, но реализация max_element в libc ++ этого не делает.

Есть пара проблем с идеей:

• Предположение, что существует специализация numeric_limits для типа элементов последовательности. (max_element работает со всем, что можно заказать.) Это можно обойти с помощью некоторого метапрограммирования шаблонов.
• Есть версия max_element, которая принимает предикат сравнения, а не только operator <. Какое максимальное значение в этом случае?
• Это потребует, чтобы тип в последовательности был «сопоставимым по равенству», а не просто «меньше сопоставимого».
• (Вероятно, самый важный) Это введет тест внутри l oop, который перечисляет элементы последовательности, тем самым замедляя алгоритм для всех остальных.