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

Question

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

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

Вот идеи, о которых я думал до сих пор:

• Предоставьте только один тип итератора :

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

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

• Предоставить несколько типов итераторов :

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

• Предоставьте один тип итератора и используйте алгоритмы stl :: для специализированного доступа

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

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

Как бы вы справились с этим?

Answer 1

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

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;
}

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

Answer 2

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

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

Вы* на самом деле нужно преобразований, если есть функции-члены, которые добавляют или удаляют элементы контейнера, потому что вы, вероятно, не хотите предоставлять отдельную перегрузку для каждого типа итератора (так же, как стандартные контейнеры не делаютопределить 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, если они не исходили из одной и той же начальной точки.