Запись моей собственной реализации подобного stl Итератора в C++
Я в настоящее время пытаюсь понять intrinsics итераторов на различных языках т.е. способе, которым они реализованы.
Например, существует следующий класс, выставляющий интерфейс списка.
template<class T>
class List
{
public:
virtual void Insert( int beforeIndex, const T item ) throw( ListException ) =0 ;
virtual void Append( const T item ) =0;
virtual T Get( int position ) const throw( ListException ) =0;
virtual int GetLength() const =0;
virtual void Remove( int position ) throw( ListException ) =0;
virtual ~List() =0 {};
};
По данным GoF, лучший способ реализовать итератор, который может поддерживать различные виды обхода, состоит в том, чтобы создать основной класс Итератора (друг Списка) с защищенными методами, которые могут получить доступ к участникам Списка. Конкретные реализации Итератора обработают задание по-разному и частные и защищенные данные списка доступа через основной интерфейс.
Отсюда дальше вещи становятся сбивающими с толку. Скажите, у меня есть класс LinkedList и ArrayList, оба полученные на основании Списка, и существуют также соответствующие итераторы, каждый из возвратов классов. Как я могу реализовать LinkedListIterator? Я абсолютно вне идей. И какой данные основной класс итератора может получить из Списка (который является простым интерфейсом, в то время как реализации всех производных классов значительно отличаются)?
2 ответа
STL на самом деле не использует абстрактные базовые классы и виртуальные функции. Вместо этого он сознательно разработан, чтобы не быть объектно-ориентированным (в смысле GoF) и полностью построен на шаблонах с целью «полиморфизма времени компиляции». Шаблоны не заботятся об абстрактных интерфейсах. Все работает до тех пор, пока у них достаточно похожий интерфейс (например, если бы вы вместо этого вызывали Append push_back , то для вас подойдет больше кода, ожидающего, что контейнеры, совместимые с STL, будут работать, например std :: back_insert_iterator ).
Итератор, совместимый с STL, должен был бы перегружать множество операторов, чтобы вести себя как указатель (насколько это возможно, учитывая ограничения контейнера), включая * , -> , ++ , - (если двунаправленный - двусвязный), == и ! = .
Стандартная библиотека C ++ не использует полиморфизм и наследование в своей реализации итераторов; вместо этого он использует метапрограммирование шаблонов C ++ и понятие (но не формальный синтаксис *) «концепций».
По сути, это будет работать, если интерфейс вашего класса итератора будет соответствовать некоторому набору требований. Этот набор требований называется «концепцией». Существует несколько различных концепций итераторов (см. на этой странице их список ), и они являются иерархическими. Основы создания совместимого итератора C ++ - привести ваш интерфейс в соответствие с концепцией. Для простого итератора, который работает только в прямом направлении, это потребует:
- Определение типа
value_typeдля значения, которое является результатом разыменования вашего итератора. - Typedef
reference_type, который является ссылочным типом для соответствующего типа значения. - Указатель typedef
- Typedef
iterator_category, который должен быть одним из input_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag или random_access_iterator_tag, в зависимости от вашего механизма обхода. - Определение типа
тип_различия, указывающее результат вычитания двух разных итераторов. - Функция
const value_type & operator * () constдля разыменования итератора. - Функция
value_type & operator * (), если ваш итератор может использоваться для управления значением. - Приращение (функции
operator ++ ()иoperator ++ (int)) для поиска вперед. - Функция разницы:
оператор разности_типа- (const type_of_iterator &)
Если вы выберете одну из более сложных категорий итераторов, вам также может потребоваться указать оператор декремента и плюс, чтобы иметь возможность искать назад или искать произвольное расстояние.
* Стандартная библиотека C ++ так часто использует концепции неформальным образом, что комитет по стандартам C ++ стремился ввести формальный механизм их объявления в C ++ (в настоящее время они существуют только в документации стандартной библиотеки, а не в каких-либо явных код). Однако постоянные разногласия по этому предложению привели к тому, что оно было отменено для C ++ 0x, хотя после этого оно, вероятно, будет пересмотрено для стандарта.