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

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

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

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

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

Ответы

Ответ 1

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

К счастью, обычно вам не нужно явно перечислять все typedef. Там тип утилиты в заголовке <iterator>, называемый iterator, который параметризуется множеством разных аргументов. Если вы определяете собственный тип итератора, вы можете наследовать от iterator, чтобы автоматически импортировать всю эту информацию. Это, по сути, более быстрый способ иметь все typedef на месте.

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

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

Ответ 2

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

Итератор обычно определяется как вложенный класс внутри контейнера. std::iterator обычно используется в качестве базового класса, чтобы упростить определение вашего класса итератора. Вам никогда не придется использовать std::iterator - он просто там, чтобы сделать работу немного проще и (особенно) уменьшить количество кода, который вам нужно ввести.

Ответ 3

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

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