О понятии Sentinel говорят мало, особенно в русскоязычном пространстве. Вместе с Юрием Вашинко, опытным тимлидом и спикером нашего курса «С++ разработчик» сегодня рассмотрим, что такое Sentinel и как его использовать:
В каждом разработчике С++ (до 17 версии) прочно укоренилось понятие итератора, на котором построена по сути вся работа со контейнерами в STL. Но бывают случаи, когда приходится отказываться от использования алгоритмов в угоду собственных реализаций, т.к. они оказываются более выгодными с точки зрения эффективности.
Для начала давайте напомним всем известные понятия. Контейнеры предоставляют нам итераторы begin() и end(), где begin() указывает на первый элемент контейнера, а end() на «мифический» элемент, который находится сразу за последним элементом. И вот когда начинающие разработчики с этим знакомятся — тут бывает много интересного. Все представляют в первую очередь std::vector, и там можно представить, что находится в конце. Но если спросить — а что же будет, если этим контейнером является std::map — ответы будут разные. Да и объяснить бывает непросто, что этот элемент, по сути, нереальный.
Лично для меня итератор end() вообще выбивается из хардкорного, строго типизированного и структурированного языка С++. На момент создания и реализации данной концепции это было хорошим решением, но времена меняются и задачи тоже. Подумаем, а что нам делать, если обрабатывать массив нужно не весь, а закончить обработку в зависимости от значения внутри вектора. Или, к примеру, мы хотим создать бесконечный массив, то есть постоянно дополняемый. Что в таком случае считать признаком окончания? И вот для такого рода задач понимаешь, что нет ничего лучше чем прохода в виде while(true) и выходом по условию.
Для примера возьмем задачу, где нам нужно первое слово в предложении преобразовать в uppercase. (Опустим здесь зачем это может понадобится. Многообразие задач заказчика настолько велико, что самая нереальная и порой глупая задача на сегодняшний день может стать острой необходимостью завтра ?)
Решим ее при помощи цикла while:
char introString[] = "Hello sentinel";
int i = 0;
while (introString[i]!=' ' && introString[i] != '\0')
{
introString[i] = toupper(introString[i]);
i++;
}Если решать такую задачу через алгоритмы stl — придётся сначала найти, где находится ‘ ‘, а потом вызвать соответствующий алгоритм для прохода по данным в этой области ограничив его итераторами, что потенциально может привести полному двойному проходу по данным.
std::vector<char> vectorArray = {'H','e','l','l','o',' ','s','e','n','t','i','n','e','l'};
auto findex = std::find(vectorArray.begin(), vectorArray.end(),' ');
std::transform(vectorArray.begin(), findex, vectorArray.begin(), to_uppercase);Символ ‘ ‘ здесь играет роль границы, когда нужно прекращать обработку массива.
И вот мы пришли по сути к понятию sentinel (в дословном переводе - «страж»). Sentinel также называют флагом или сигналом завершения обработки. И теперь давайте представим, что нам нужно в алгоритмы stl передавать не end(), именно некий sentinel, который можно просто сравнить с итератором. Что нам это даст? В первую очередь, мы можем не задумываться о конечном итераторе в принципе и тип Sentinel может вообще не является итератором. Давайте перепишем наш пример с использованием отдельного класса Sentinel:
class Sentinel {
public:
bool operator==(std::vector<char>::iterator it) const {
return *it == ' ';
}
};
std::vector<char> vectorArray = {'H','e','l','l','o',' ','s','e','n','t','i','n','e','l'};
Sentinel sentinel;
for (auto it = vectorArray.begin();it!=sentinel;++it)
{
*it = std::toupper(*it);
}Таким образом, мы подошли к понятию Sentinel в том виде, в котором оно используется в C++20.
Так оно объявлено в стандарте:
template< class S, class I >
concept sentinel_for = std::semiregular<S> && std::input_or_output_iterator<I> &&
__WeaklyEqualityComparableWith<S, I>;Это концепт, который накладывает ограничение, которое означает, что в роли Sentinel может выступать объект, который можно сравнить с итератором.
Давайте модифицируем немного класс Sentinel, чтобы он смог останавливать обработку не только по символу ‘ ‘, но и по концу итератора
template <typename T>
struct Sentinel {
bool operator==(T Iter) const {
return Iter == ContainerEnd || *Iter == ' ';
}
T ContainerEnd;
};А теперь, используя класс Sentinel, решим изначальную задачу.
std::vector<char> vectorArray = { 'H','e','l','l','o',' ','s','e','n','t','i','n','e','l' };
auto res = std::ranges::for_each(
vectorArray.begin(), Sentinel{ vectorArray.end() }, [](auto &val) {
val = toupper(val);
}
);Более того, мы можем это использовать и в других алгоритмах:
std::ranges::sort(vectorArray.begin(), Sentinel{ vectorArray.end() }, std::greater());Но и это еще не все — наш «мифический» end() тоже может выступать в качестве sentinel (хотя у нас уже это заложено в классе Sentinel), и так по умолчанию и происходит, когда мы вызываем, к примеру, метод ranges::sort()
std::ranges::sort(vectorArray, std::greater());Но в данном случае end() приобретает совсем другой смысл, он хоть и остается неким абстрактным понятием, но может быть свободно заменен на нечто более ощутимое и связанное именно с реальными данными.
И сейчас, после того, как мы разобрали это понятие, становится очевидным, что использовать бесконечные массивы не так уж и сложно даже с алгоритмами.
Введение концепции Sentinel в C++20 значительно расширяет возможности работы с контейнерами и итераторами. Sentinel позволяет более гибко управлять границами последовательностей, заменяя «мифический» итератор end() на более выразительный объект, который не обязательно должен быть итератором. Это решение делает алгоритмы STL более эффективными, особенно при работе с частичными или бесконечными структурами данных. В итоге, Sentinel не только упрощает код, но и открывает новые возможности для создания производительных и понятных решений в современных приложениях на C++.
А подробнее о нюансах использования Sentinel и других особенностях языка С++ — на нашем курсе «Разработчик С++», старт — 28 октября. Подробности — по ссылке.
Комментарии (23)
slonopotamus
25.10.2024 16:24Тем временем в нормальных языках программирования у итератора есть два метода: next(), возвращающий элемент и hasNext(), сигнализирующий что всё, элементов больше нету. Это даже можно было бы скукожить до одного метода, возвращающего std::optional. Но нет, давайте изобретать костыли с указателями-хрен-знает-куда (и порожать баги вида "случайно сравнили с end от другой коллекции"), дополнительных объектов в виде sentinel и т.д...
KanuTaH
25.10.2024 16:24То, что в C++ обозначается универсальным образом (парой итераторов), "в нормальных-то языках" требует дополнительных сущностей, если ты, скажем, хочешь работать только с частью диапазона без создания копий - например, в расте это слайсы,
Range, и т.д., причем для каких-то контейнеров работает только что-то одно, а для каких-то только что-то другое, писать, так сказать, контейнеронезависимый универсальный код загребешься.slonopotamus
25.10.2024 16:24Если я хочу работать с частью диапазона, я создам итератор-обёртку, который скажет что он кончился раньше. Если я захочу работать только с чётными элементами, я создам итератор, который в next() будет делать два шага вперёд. Если я захочу создать бесконечный итератор, в цикле перебирающий коллекцию, я тоже прекрасно могу это сделать. Не нужны никакие дополнительные сущности.
KanuTaH
25.10.2024 16:24Замечательно, только вот... что если вам нужно, скажем, разбить существующий диапазон на поддиапазоны? В C++ это можно сделать без проблем, имея пару итераторов "начало-конец", а только лишь с предлагаемыми вами убогими недоитераторами это не сделаешь, нужно работать тогда непосредственно с тем, из чего вы такой итератор получили, да и то не всегда это поможет. Например, в C++ можно разбить диапазон, состоящий из пары итераторов, полученных хоть из массива, хоть из вектора, хоть из хешмапы, на поддиапазоны и закинуть обработку этих поддиапазонов по разным потокам, универсальным образом (опять же пара итераторов, никаких проблем). А что делать с вашим недоитератором? Ладно, окей, забьем на универсальность кода, будем работать с частным случаем - с исходным контейнером, скажем, с
HashMapиз раста, покажите, пожалуйста, как разбить этотHashMapскажем на 2 или 4 поддиапазона для параллельной обработки его элементов без создания копий.slonopotamus
25.10.2024 16:24Я правильно понимаю что вы хотите взять end() - begin(), поделить это на N кусков и пойти с ними что-то делать? Есть подозрение что вычисление концов промежуточных диапазонов на большом количестве коллекций (примерно всех, которые основаны не на массиве внутри) выльется в O(n) и перф будет грустить.
UPD: или даже хуже, это O(n) вообще для каких угодно коллекций, потому что у C++-итератора нет операции "сдвинуться на N". А раз речь про O(n) - ну берем begin, проматываем его полностью чтобы узнать размер, дальше мотаем опять от начала до нужных границ :)
KanuTaH
25.10.2024 16:24Даже если итератор не умеет в random access, то его инкремент как правило весьма дешевая операция. А вот обработка самих элементов, на которые ссылаются эти итераторы, может быть операцией весьма дорогой, так что распараллеливание принесет свои плюсы, даже если придется пройтись O(n) по самим итераторам.
потому что у C++-итератора нет операции "сдвинуться на N"
Вы бредите.
slonopotamus
25.10.2024 16:24Ну вот я и говорю, оно прекрасно делается с той же самой ассимптотикой имея на руках только лишь begin.
KanuTaH
25.10.2024 16:24Ну как вы разобьете нечто, что имеет лишь begin и next, возвращающий очередной элемент, на поддиапазоны? А ваши слова про "у итератора в C++ нет операции сдвинуться на N" - это просто бред человека, который не в теме.
slonopotamus
25.10.2024 16:24А ваши слова про "у итератора в C++ нет операции сдвинуться на N" - это просто бред человека, который не в теме.
И тут вы такой вжух, и ссылку на описание соответствующего метода.
KanuTaH
25.10.2024 16:24Да, без проблем, это называется RandomAccessIterator. Скажем
std::advanceимеет специализации для разных типов итераторов, чтобы можно было универсально с ними работать. Меня всегда поражали люди, которые начинают свои "а вот в нормальных языках-то", не удосужившись изучить матчасть.slonopotamus
25.10.2024 16:24имеет специализации
Ну начинается. Процитирую вас же: "писать, так сказать, контейнеронезависимый универсальный код загребешься". То есть в C++ специализации - это норм, а в других языках уже не норм.
Впрочем, учитывая вашу манеру общения с переходом на личности, продолжать беседу не имею ни малейшего желания. Хорошего вечера.
KanuTaH
25.10.2024 16:24То есть в C++ специализации - это норм, а в других языках уже не норм.
Ну так эти специализации уже есть, в обобщенном коде ты просто пишешь
std::advanceилиstd::distanceи все, все искаропки работает максимально эффективным образом.Впрочем, учитывая вашу манеру общения с переходом на личности, продолжать беседу не имею ни малейшего желания. Хорошего вечера.
Ну, ясно.
IQuant
25.10.2024 16:24В том же расте у итераторов есть дополнительные методы, такой универсальный диапазон можно организовать с помощью
.skip(a).take(b).KanuTaH
25.10.2024 16:24Здорово. Вот берем такой дженерик "в том же расте" (ведь это же "нормальный язык-то"?), который принимает итератор на
HashMapилиBTreeMapи удваивает значение каждого элемента своего диапазона:fn mul< I: std::iter::Iterator<Item = (K, V)>, K, V: std::ops::DerefMut<Target = T>, T: std::ops::MulAssign<i32>, >( iter: I, ) { for (_, mut val) in iter { *val *= 2; } }Пример работы. Пожалуйста, распараллельте (точнее, "партиционируйте") его. Ну так, чтобы внутри этой функции этот
iterразбивался на несколько поддиапазонов, представленных отдельными итераторами, которые затем, скажем, передавались бы в функцию, символизирующую распараллеливание работы (старт потока). В C++ это - элементарная задача для функции, принимающей классическую пару итераторовbegin/end, относящихся к контейнеру любого типа. Продемонстрируйте, пожалуйста, как это сделать в расте, только не словоблудием, а, как выше написал ваш коллега, "и вы тут такой вжух - и пример рабочего кода" (можно даже и без создания настоящих потоков, ожидания и т.д., просто покажите сам процесс партиционирования).
Yura_PST
25.10.2024 16:24Только функция next() нарушает принцип единственной ответственности, делает сразу две вещи, и итератор передвигает, и элемент возвращает.
slonopotamus
25.10.2024 16:24SRP абсолютно про другое.
Yura_PST
25.10.2024 16:24То есть, функцию next() делает две вещи, но принцип SRP не нарушает? Вот тут нужны прям подробные пояснения.
slonopotamus
25.10.2024 16:24Я специально дал ссылку. Цитирую дядюшку Мартина:
A class should have only one reason to change
Также
Another wording for the Single Responsibility Principle is: Gather together the things that change for the same reasons. Separate those things that change for different reasons.
Можно хоть миллион вещей запихивать в одну функцию, если они change for the same reasons, и это не будет нарушением SRP.
Yura_PST
25.10.2024 16:24Что дядюшка Мартин говорит про именование функций? Как бы он порекомендовал назвать функцию .которая возвращает текущий элемент и передвигает итератор?
Apoheliy
25.10.2024 16:24Предположу, что в случает с next дело больше в гарантиях исключений.
Есть очень хорошая гарантия, когда при выбрасывании исключения ничего другое в значениях не поменялось (т.е. осталось исходное состояние).
В случае с next, если при копировании возвращаемого значения вылетит исключение (а в C++ это очень возможно), то вы получите итератор на новой позиции. И это не очень хорошо.
Поэтому в стандартной библиотеке C++ любят делить собственно движение по контейнеру и возврат/удаление/итд элемента - тогда можно разделить обработку ошибок/исключений.
Если рассматривать другие языки (где копируются не объекты, а указатели, и при этом ошибок быть не может), то там функционал наподобие next применяется и приветствуется. Просто это другие языки :).
Apoheliy
Реклама, опять реклама :(.
Хотя бы ссылку на "подробности" сделайте нажимаемой, а то все усилия пропадут втуне.
--
Сарказм: не хочу показаться невежливым, но вы свой ник пробовали в переводчик вставить. Ну, на всякий случай.
apidev
Иногда хочется, чтобы у Хабра была платная подписка с бесплатным вариантом для школьников/студентов вместо сотрудничества с крупными компаниями в качестве рекламной платформы.
--
По поводу сарказма: предполагаю, что никнейм был взят из Urban Dictionary. Непропеченное печенье.