Повторная проверка итератора STL для конечного (прошедшего) итератора? - PullRequest
Новая
       48

Повторная проверка итератора STL для конечного (прошедшего) итератора?

0 голосов
/ 16 ноября 2018

См. Связанные вопросы об аннулировании итератора прошлого: это , это .

Это больше вопрос проектирования, а именно существует ли (в STL или в другом месте) такое понятие, как итератор "конца конца" "повторная проверка" ?

Что я имею в виду под этим и случай использования: предположим, что алгоритму требуется«хвост» контейнера (например, очереди).Он пересекает контейнер, пока не будет достигнут end(), затем останавливается;независимо от этого, другая часть программы ставит в очередь больше элементов в очереди.Как алгоритм может (РЕДАКТИРОВАТЬ) эффективно сказать, "было ли в очереди больше элементов", удерживая ранее завершенный итератор (назовите его tailIt)?(это подразумевает, что он может проверить, если tailIt == container.end() все еще, и если это неверно, заключите, что tailIt теперь действителен и указывает на первый элемент, который был вставлен).

Пожалуйста, не отклоняйте вопрос как «нет, нет» - я стремлюсь сформировать суждение о том, как разработать некоторую логику идиоматическим образом и иметь много вариантов (на самом деле рассматриваемые итераторысозданная вручную структура данных, для которой я могу предоставить это свойство - end () revalidation - но я бы хотел судить, если это хорошая идея).

РЕДАКТИРОВАТЬ: дал понять, что у нас есть итератор tailIt и ссылка на container.Тривиальный обходной путь для того, что я пытаюсь сделать, - это также помните count: = сколько предметов вы обработали, а затем проверьте, все еще ли container.size() == count, и если нет, то найдите container[count] и продолжите обработку оттуда.Это имеет много недостатков (дополнительное состояние, допущение, что контейнер не появляется спереди (!), Произвольный доступ для эффективного поиска).

Ответы [ 2 ]

0 голосов
/ 16 ноября 2018

Не в общем. Вот некоторые проблемы с вашей идеей:

  • Некоторые устаревшие итераторы вообще не "указывают" на блок данных; фактически это будет справедливо для любого итератора, кроме векторного итератора. Итак, в целом, существующий конечный итератор никогда не станет действительным итератором данных;
  • Итераторы часто становятся недействительными при изменении контейнера & mdash; хотя это не всегда так, оно также исключает общее решение, основанное на разыменовании некоторого итератора до мутации;
  • Действительность итератора ненаблюдаема & mdash; перед разыменованием итератора вам уже нужно знать, действителен он или нет. Это информация, которая приходит откуда-то, обычно это ваш мозг и ад; под этим я подразумеваю, что разработчик должен прочитать код и сделать определение на основе его структуры и потока.

Соберите все это вместе, и становится ясно, что конечный итератор просто не может быть использован таким образом, поскольку интерфейс итератора в настоящее время разрабатывается. Итераторы ссылаются на данные в диапазоне, а не на контейнер; следовательно, очевидно, что они не содержат информации о контейнере, и если контейнер вызывает изменение диапазона, то нет иного объекта, о котором итератор знает, что он может попросить выяснить это.

Можно ли создать описанную логику? Конечно! Но с другим интерфейсом итератора (и поддержкой из контейнера). Вы можете обернуть контейнер в свой собственный тип класса, чтобы сделать это. Однако я не советую делать вещи, которые выглядят как стандартные итераторы, но ведут себя иначе; это будет очень запутанно.

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

0 голосов
/ 16 ноября 2018

В случае с std :: queue нет, нет (хех).Не потому, что итераторы для очереди становятся недействительными после того, как что-то выдвинуто, а потому, что в очереди вообще нет никаких итераторов.

Что касается других типов итераторов, большинство (или любой из них) не имеютt требуется ссылка на владельца контейнера (управляющий объект, содержащий всю информацию о базовых данных).Это компромисс между эффективностью и гибкостью.(Я быстро проверил реализацию gcc's std :: vector :: iterator)
Можно написать реализацию для типа итератора, который сохраняет ссылку на держатель в течение его времени жизни, таким образом, итераторы никогда не должны быть аннулированы!(если держатель не std :: move'd)

Теперь, чтобы добавить мое профессиональное мнение , я не возражаю против просмотра safe_iterator / flex_iterator для случаев, когда итератор обычно будетпризнан недействительным во время итераций.

Возможный пользовательский интерфейс: 

for (auto v : make_flex_iterator(my_vector)) {
    if (some_outside_condition()) {
        // Normally the vector would be invalidated at this point
        // (only if resized, but you should always assume a resize)
        my_vector.push_back("hello world!");
    }
}

Буквально повторная проверка итераторов может быть слишком сложной для построения в случае использования (я не знаю, с чего начать), но разработкаИтератор, который просто никогда не делает недействительными, довольно тривиален, с такими большими издержками, как цикл * 1013.
Но, учитывая сказанное, я не могу заверить вас, насколько хорошо компилятор будет оптимизировать, как развертывание циклов, с этими итераторами.Я предполагаю, что это все еще сделает довольно хорошую работу.

...