#опытным
С++20 библиотека диапазонов принесла нам много новых полезных алгоритмов и способов управления данными. Но не только это. Рэнджи задублировали и привычные нам "древние" стандартные алгоритмы.
Хотя кажется "что какая разница, использовать новое апи или старое?" - разница все-таки есть. И сегодня поговорим об одном конкретном кейсе.
Что делает std::find? Ищет элемент в промежутке между итератором начала и конца последовательности и возвращает на него итератор на этот элемент:
auto it = std::find(vec.begin(), vec.end(), 42);
Если элемент не найден, то find просто возвращает итератор на конец диапазона.
Ровно такую же строчку можно написать с std::ranges::find и это заработает:
auto it = std::ranges::find(vec.begin(), vec.end(), 42);
Однако здесь открываются новые возможности. Все потому, что второй аргумент алгоритм - конец диапазона - не обязан быть того же типа, что и итератор начала:
// std::find
template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );
// std::ranges::find
template< std::input_iterator I, std::sentinel_for<I> S,
class T, class Proj = std::identity >
requires std::indirect_binary_predicate
<ranges::equal_to, std::projected<I, Proj>, const T*>
constexpr I find( I first, S last, const T& value, Proj proj = {} );
По шаблонным параметрам видно, что во втором случае first и last могут быть разных типов, в отличие от std::find.
Это позволяет использовать кастомный тип ограничителя последовательности, который позволит сделать поиск несколько эффективнее.
std::find реализован примерно вот так:
template<class InputIt, class T = typename std::iterator_traits<InputIt>::value_type>
constexpr InputIt find(InputIt first, InputIt last, const T& value)
{
for (; first != last; ++first)
if (*first == value)
return first;
return last;
}
На каждой итерации цикла идет проверка, не дошли ли мы до конца. Это нужно, чтобы мы не вышли за границы последовательности при поиске.
Но что, если у нас данные в таком формате, что мы точно знаем о существовании там нужного элемента?
Пусть мы парсим какие-то данные в заданном формате. Например, csv. Мы четко знаем, что между элементами всегда есть разделитель. Это либо запятая, либо символ конца строки.
При чтении каждого отдельного элемента мы точно знаем, что он закончится либо запятой, либо символом конца строки. В этом случае при поиске разделителя мы точно не выйдем за границы диапазона, ведь мы четко знаем, что он там будет.
В этом случае было бы довольно полезным просто выкинуть проверку на окончание диапазона. Это бы дано очень несущественный, но все же импакт в скорость программы, особенно для больших файлов.
И ограничитель std::unreachable_sentinel фактически позволяет это сделать. Причина в том, что операция проверки на равенство для него всегда возвращает false.
template<std::weakly_incrementable I>
friend constexpr bool operator==( unreachable_sentinel_t, const I& ) noexcept
{ return false; }
И хоть алгоритм std::ranges::find не сильно отличается по реализации от std::find (там тоже есть проверка конца последовательности), компилятор видит, что проверка конца всегда возвращает false и выкидывает ее из кода.
Таким образом мы экономим одну операцию при проверке очередного элемента последовательности.
Однако здесь есть очевидная проблема. Если нужный элемент по какой-то причине не будет найден в пределах заданного диапазона, то мы получаем выход за границы и выстрел UB в упор. Поэтому использовать std::unreachable_sentinel нужно очень осторожно и только в случае полной уверенности в формате данных.
Be sure. Stay cool.
#cpp20 #optimization
