В чем разница между часовым и конечным итератором?
Во время чтения Эрика Ниблера предложение диапазона,
Я встретил термин «страж» как замену конечного итератора.
Мне трудно понять преимущества дозорного по сравнению с конечным итератором.
Может ли кто-нибудь привести наглядный пример того, что sentintel вносит в таблицу, чего нельзя сделать стандартными парами итераторов?
«А страж является абстракцией сквозного итератора. Стражи
Обычные типы, которые можно использовать для обозначения конца диапазона.
сторож и итератор, обозначающие диапазон, должны быть EqualityComparable.
Часовой обозначает элемент, когда итератор i сравнивается равным
Страж, и я указываю на этот элемент. «- N4382
Я думаю, что часовые работают как функции в определении конца диапазона, а не только позиции?
Решение
Sentinel просто позволяет конечному итератору иметь другой тип.
Допустимые операции на итераторе с последним завершением ограничены, но это не отражается в его типе. Это не нормально * .end() итератор, но компилятор позволит вам.
Часовой не имеет одинарного разыменования или ++кроме всего прочего. Как правило, он ограничен самыми слабыми итераторами после конечного итератора, но применяется во время компиляции.
Есть вознаграждение. Часто обнаружить конечное состояние легче, чем найти его. Со стражем, == может отправить «определить, не прошел ли другой аргумент конец» во время компиляции, а не во время выполнения.
В результате некоторый код, который раньше был медленнее, чем эквивалент C, теперь компилируется до скорости уровня C, например, копируя строку с нулевым символом в конце, используя std::copy, Без часовых вы должны были либо сканировать, чтобы найти конец перед копией, либо передать итераторы с флагом bool, говорящим «Я конечный страж» (или эквивалентный), и проверить его на ==,
Есть и другие подобные преимущества при работе с подсчетом диапазонов. Кроме того, некоторые вещи, такие как почтовые диапазоны1 стало проще выражать (конечный почтовый индекс может содержать обоих исходных стражей и возвращать равные, если это делает один из часовых: итераторы zip либо сравнивают только первый итератор, либо сравнивают оба).
Еще один способ думать об этом заключается в том, что алгоритмы, как правило, не используют всю полноту концепции итератора для параметра, передаваемого как прошедший конечный итератор, и этот итератор обрабатывается по-разному на практике. Sentinel означает, что вызывающая сторона может использовать этот факт, что, в свою очередь, позволяет компилятору использовать его проще.
1 Диапазон почтовых индексов — это то, что вы получаете, когда начинаете с двух или более диапазонов и «застегиваете» их вместе, как молнию. Диапазон теперь по кортежам отдельных элементов диапазона. Продвижение zip-итератора продвигает каждый из «содержащихся» итераторов и то же самое для разыменования и сравнения.
Другие решения
Часовые и конечные итераторы похожи в том, что они отмечают конец диапазона. Они отличаются тем, как этот конец обнаружен; либо вы тестируете сам итератор, либо тестируете значение данных в итераторе. Если вы уже выполняете тестирование данных, дозорный может позволить вашему алгоритму завершиться «бесплатно» без каких-либо дополнительных тестов. Это может либо упростить код, либо сделать его быстрее.
Очень распространенным сторожем является нулевой байт, который используется для обозначения конца строки. Нет необходимости хранить отдельный итератор для конца строки, его можно определить по мере работы с символами самой строки. Недостатком этого соглашения является то, что строка не может содержать нулевой символ.
Обратите внимание, что я написал этот ответ, прежде чем читать предложение в ссылке; это классическое определение дозорного, которое может не совпадать с предложенным там определением.
Основная мотивация для введения дозорного состоит в том, что существует много операций итератора, которые поддерживаются, но обычно никогда не требуются для конечного итератора. 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.