Какая разница между дозорным и конечным итератором?

Ответ 1

Sentinel просто позволяет конечному итератору иметь другой тип.

Разрешенные операции на итераторе прошедшего конца ограничены, но это не отражается в его типе. Это не нормально для * a .end() итератора, но компилятор позволит вам.

У дозорника нет унарного разыменования или ++, между прочим. Как правило, это ограничено, как самые слабые итераторы за конечным итератором, но принудительно выполняется во время компиляции.

Существует выигрыш. Часто обнаружение конечного состояния легче, чем его поиск. С часовым, == может отправить "обнаружить, если другой аргумент за конец" во время компиляции, а не время выполнения.

В результате некоторый код, который раньше был медленнее, чем эквивалент C, теперь сводится к скорости уровня C, например, копирование строки с нулевым завершением с использованием std::copy. Без стражей вам либо пришлось сканировать, чтобы найти конец перед копией, либо передать итераторы с флагом bool, говорящим "Я - конечный контрольный сигнал" (или эквивалент), и проверьте его на ==.

Существуют и другие аналогичные преимущества при работе с диапазонами, основанными на подсчете. Кроме того, некоторые вещи, такие как zip-диапазоны ¹ легче выразить (конечный zip-дозорчик может содержать оба источника-получателя и возвращать равным, если любой из них выполняет: zip-итераторы либо сравнивают только первый итератор, либо сравнивают и другое).

Другой способ думать об этом заключается в том, что алгоритмы, как правило, не используют полное богатство концепции итератора по параметру, переданному как прошлое итератору конца, и что на практике итератор обрабатывается по-разному. Sentinel означает, что вызывающий может использовать этот факт, что, в свою очередь, позволяет компилятору использовать его легче.

¹ Диапазон zip - это то, что вы получаете, когда начинаете с двух или более диапазонов, и "застегиваете" их вместе, как молния. Диапазон теперь превышает кортежи отдельных элементов диапазона. Продвижение zip-итератора продвигает каждый из "содержащихся" итераторов, а также для разыменования и сравнения.

Ответ 2

Sentinels и end iterators аналогичны тем, что они отмечают конец диапазона. Они различаются тем, как определяется этот конец; либо вы тестируете сам итератор, либо тестируете значение данных на итераторе. Если вы уже выполняете тесты по данным, дозорный сигнал может позволить вашему алгоритму закончить "бесплатно" без каких-либо дополнительных тестов. Это может либо упростить код, либо сделать его быстрее.

Очень частым часовым является нулевой байт, который используется для обозначения конца строки. Нет необходимости хранить отдельный итератор для конца строки, его можно определить при работе с символами самой строки. Недостатком этого соглашения является то, что строка не может содержать нулевой символ.

Обратите внимание, что я написал этот ответ, прежде чем читать предложение в ссылке; это классическое определение часового, которое может не совпадать с предложенным там определением.

Ответ 3

Центральная мотивация введения сторожевого устройства заключается в том, что существует много операций итератора, которые поддерживаются, но обычно не требуются для конечного итератора end(). Например, вряд ли есть смысл разыменовать его с помощью *end(), увеличивая его с помощью ++end() и т.д. (*).

Напротив, основное использование end() - это просто сравнить его с итератором it, чтобы сигнализировать, находится ли it в конце того, что он просто выполняет. И, как обычно в программировании, различные требования и разные приложения предлагают новый тип.

Библиотека range-v3 превращает это наблюдение в предположение (которое реализуется через концепцию): оно вводит новый тип для end() и требует только того, чтобы оно было сопоставимо по сравнению с соответствующим итератором, но не требуют обычных операций итератора). Этот новый тип end() называется дозорным.

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

struct my_iterator;    //some iterator
struct my_sentinel
{
     bool is_at_end(my_iterator it) const
     {
         //here implement the logic when the iterator is at the end
     }
};

auto operator==(my_iterator it, my_sentinel s)  //also for (my_sentinel s, my_iterator it)
{
    return s.is_at_end(it); 
}

См. абстракцию? Теперь вы можете реализовать любую проверку, которую вы хотите в функции is_at_end, например:

• остановить никогда (получить бесконечный диапазон)
• остановка после N увеличивается (чтобы получить подсчитанный диапазон)
• останавливается, когда встречается \0, т.е. *it = '\0' (для циклирования по C-строкам)
• остановитесь, когда на нем будет 12 часов (для обеда) и т.д.

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

(*) Заметим, что это не означает, что для такого рода операций вообще не нужно использовать. Например, --end() может быть полезна в некоторых местах, см., Например, этот вопрос. Однако, по-видимому, возможно реализовать стандартную библиотеку без них - это то, что сделала библиотека range-v3.