Определение итератора моего собственного контейнера

Question

Меня смущают некоторые концепции определения моего собственного итератора:

Отсюда: http://www.cs.northwestern.edu/~riesbeck/programming/c++/stl-iterator-define.html,, который, кажется, предлагает использовать внутренний класс итератора, который определяет операторы.Многие другие наследуют базовый класс iterator для переопределения операторов.

Я не совсем понимаю, какие методы следует использовать.Почему, например,

typedef ptrdiff_t difference_type;

, в начале определения класса контейнера?

Большое спасибо!

Answer 1

Спецификация C ++ относительно того, что именно является контейнером STL, требует, чтобы у любого типа контейнера STL было несколько различных доступных полей. Некоторые из них, например begin() и end(), являются функциями, а другие, например iterator, являются типами. Эти ограничения также применяются к итераторам. Это позволяет шаблонным функциям C ++ анализировать свои типы аргументов для поиска дополнительных свойств. Например, все типы итераторов STL должны определять поле iterator_category, содержащее тип, кодирующий их возможности. Таким образом, алгоритмы STL могут иметь разные реализации разных функций в зависимости от мощности итераторов, которые они принимают. Примером класса является функция distance, которая принимает два итератора и возвращает количество пробелов между ними. Если входное значение является просто ForwardIterator или BidirectionalIterator, это работает, продвигая итераторы вперед и подсчитывая, сколько шагов было сделано, которое выполняется в O (n). Если входное значение равно RandomAccessIterator, то итераторы можно просто вычесть, чтобы получить результат в O (1).

До C ++ 17 рекомендовалось включать заголовок <iterator> и наследовать от std::iterator для автоматической генерации необходимых вложенных типов (reference, pointer и т. Д.). Этот тип теперь устарел , поэтому вам придется либо вручную добавить typedef s, либо специализироваться std::iterator_traits для экспорта этой информации.

Что касается операторов, которые необходимо перегрузить, как минимум вам нужно получить ++ (префикс и постфикс), ==, !=, * (разыменование указателя) и -> определено , Все типы итераторов поддерживают это. Для двунаправленных итераторов или выше вы должны также определить -- (префикс и постфикс). Наконец, для итераторов с произвольным доступом вы должны поддерживать [], +, +=, - (выполнить резервное копирование множества шагов и вычесть два итератора), -=, <, >, <= и >=.

Надеюсь, это поможет!

Answer 2

Хотя ответ @ templattypedef точен, возможно, я смогу немного прояснить ситуацию.

Итератор обычно определяется как вложенный класс внутри контейнера.std::iterator обычно используется в качестве базового класса, чтобы вам было проще определить свой класс итератора.На самом деле у вас нет для использования std::iterator - это просто для того, чтобы немного упростить работу и (особенно) уменьшить объем кода, который вам нужно набрать.На самом деле, std::iterator официально устарела, поэтому использовать его не рекомендуется.Когда-нибудь он может быть удален из стандарта (хотя я не знаю какой-либо конкретной даты, когда он может быть удален).предпочтительнее, чтобы итератор определялся вне класса контейнера, который повторяется.Когда определение класса итератора вложено в определение контейнера, итератор зависит от всех параметров шаблона окружающего класса.Это редко необходимо или желательно, хотя.Например, два вектора с разными распределителями обычно могут иметь одинаковый тип итератора - изменение распределителя не меняет итерацию.

Answer 3

Хотя использование std::iterator может помочь с typedef s, это, конечно, не поможет с реальной реализацией.

В библиотеке Boost.Iterator есть много хороших вещей для этого, и я предлагаю прочитать о boost :: iterator_adaptor , который значительно сокращает объем кода, который вам нужно набирать для определения нового итератор поверх старого.