Как обрабатывать несколько типов итераторов

Question

У меня есть настраиваемая структура данных, к которой можно получить доступ несколькими способами. Я хочу попытаться сохранить эту структуру данных, чтобы она соответствовала стандартам STL, а также возможно. Поэтому у меня уже есть много typedefs, которые задают параметры шаблона STL-имена. Для меня это обычное дело.

Однако я не уверен, как правильно добавить итераторы в свою структуру данных. Основная проблема, с которой я столкнулся, заключается в том, что в отношении структуры данных будет много политик итераций. Самый простой вариант использования - итерация по всем элементам, которые будут хорошо обрабатываться STL-Conforming iterators над файловой структурой. Однако также можно получить доступ к элементам, которые каким-то образом похожи на данный ключ. Я также хотел бы перебрать все эти подобные элементы таким образом, чтобы я мог взаимодействовать с STL.

Эти идеи я думал о до сих пор:

• Обеспечить только один тип итератора:

Это поясню, что std::map делает. Итераторы запуска и завершения для поддиапазона представлены std::map::lower_bound() и std::map::upper_bound().

Однако это хорошо работает, потому что итераторы, возвращаемые begin(), end(), lower_bound() и upper_bound() совместимы, то есть operator==() может быть дано очень хорошо определенный смысл на них. В моем случае это было бы трудно получить, или даже было бы невозможно дать четкую семантику. Например, я, вероятно, получаю некоторые случаи, когда it1==it2, но ++it1!=++it2. Я не уверен, разрешено ли это STL.

• Обеспечить несколько типов итераторов:

Гораздо легче обеспечить чистую operator==() семантику. С другой стороны, Nasty, потому что он увеличивает количество типов.

• Обеспечить один тип итератора и использование СТЛ :: алгоритмы для специализированного доступа

Я не уверен, если это вообще возможно. Итерационное состояние должно храниться итератором каким-то образом (прямо или в Memento). Использование этого подхода означало бы специализацию всех stl :: алгоритмов и доступ к предикату непосредственно в специализации. Скорее всего, невозможно, и, если возможно, очень плохая идея.

Прямо сейчас я в основном выбираю версию 1, т. Е. Для обеспечения только одного типа итератора. Однако, поскольку я не понимаю, как очистить семантику, я еще не решил.

Как вы справитесь?

Answer 1

Стандартные контейнеры поддерживают две политики итерации с двумя типами итераторов: ::iterator и ::reverse_iterator. Вы можете конвертировать между ними, используя конструктор std::reverse_iterator, и его функцию-член base().

В зависимости от того, как подобны ваши итерационные политики, может быть или не быть легко обеспечить конверсии для разных типов итераторов. Идея состоит в том, что результат должен указывать на «эквивалентную позицию» в политике итерации типа назначения. Для обратных итераторов эта эквивалентность определяется тем, что если вы вставляете в эту точку, результат будет таким же. Так что если rit является обратным итератора, vec.insert(rit.base(), ...) вставляет элемент «перед» ritв обратном итерации, то есть после того, как элемент, на который указывает rit в контейнере. Это довольно сложно, и только ухудшится, когда политика итерации полностью не связана. Но если все ваши типы итераторов (или могут быть сделаны похожими) обертки вокруг «нормального» итератора, который охватывает все элементы, то вы можете определить преобразования в терминах этой базовой позиции итератора.

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

Если различные итерационные политики повторяются в обычном порядке по подмножеству элементов, просмотрите boost::filter_iterator.

Возможно, у меня были бы случаи, когда it1==it2, но ++it1!=++it2. Я не уверен, разрешено ли это STL.

Если я правильно понимаю, вы получили it1, начав с thing.normal_begin(), и вы получили it2, начав с thing.other_policy_begin(). Стандартные контейнеры не определяют результат сравнения итераторов того же типа, которые относятся к разным диапазонам, поэтому, если вы использовали общий тип, то я думаю, что это было бы хорошо, если бы в документации было ясно, что хотя operator== происходит с работа, диапазоны разделены в зависимости от того, откуда итератор.

Например, у вас может быть skip_iterator, который принимает в качестве параметра конструктора количество шагов, которые он должен перемещать каждый раз, когда вызывается ++. Тогда вы можете либо включить это целое число в сравнение, чтобы thing.skip_begin(1) != thing.skip_begin(2), либо вы могли исключить его так, чтобы thing.skip_begin(1) == thing.skip_begin(2), но ++(++(thing.skip_begin(1))) == ++(thing.skip_begin(2)). Я думаю, что все прекрасно, если оно задокументировано, или вы можете документировать, что сравнение их - UB, если они не пришли из той же начальной точки.

Answer 2

Почему больше типов проблем? Это не обязательно означает гораздо больше кода. Например, вы можете сделать шаблон iterator-type шаблоном, который принимает итерационную политику в качестве параметра шаблона.Итерация-политика могла бы обеспечить выполнение итерации:

struct iterate_all_policy { 
    iterate_all_policy(iterator<iterate_all_policy> & it) : it(it) {} 

    void advance() { /* implement specific advance here */ } 
private: 
    iterator<iterate_all_policy> & it; 
} 

Вы, вероятно, придется сделать итерационные-политики-классы друзей итератора-типов.