Написание собственной реализации stl-подобного Iterator на C ++ - PullRequest
Новая
       16

Написание собственной реализации stl-подобного Iterator на C ++

12 голосов
/ 17 апреля 2010

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

Например, существует следующий класс, представляющий интерфейс списка. 

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

С этого момента все становится запутанным. Скажем, у меня есть классы LinkedList и ArrayList, оба получены из List, и есть также соответствующие итераторы, каждый из классов возвращает. Как я могу реализовать LinkedListIterator? У меня совершенно нет идей. И какого рода данные базовый класс итератора может извлечь из списка (который представляет собой простой интерфейс, в то время как реализации всех производных классов существенно различаются)?

Ответы [ 2 ]

14 голосов
/ 17 апреля 2010

STL на самом деле не использует абстрактные базовые классы и виртуальные функции. Вместо этого он сознательно разработан, чтобы не быть ОО (в смысле GoF) и построен полностью на шаблонах, нацеленных на «полиморфизм во время компиляции». Шаблоны не заботятся об абстрактных интерфейсах. Все работает, если у них достаточно схожий интерфейс (например, если вы вместо этого вызовете Append push_back, больше кода, ожидающего STL-совместимые контейнеры, будет работать для вас, например std::back_insert_iterator).

STL-совместимый итератор должен был бы перегружать множество операторов, чтобы вести себя как указатель (насколько это возможно, учитывая ограничения контейнера), включая *, ->, ++, -- ( если двунаправленный - двунаправленный), == и !=.

7 голосов
/ 17 апреля 2010

Стандартная библиотека C ++ не использует полиморфизм и наследование в своей реализации итераторов; вместо этого он использует метапрограммирование шаблона C ++ и понятие (но не формальный синтаксис *) «концепций».

По сути, это будет работать, если интерфейс вашего класса итераторов соответствует некоторому набору требований. Этот набор требований называется «концепцией». Существует несколько различных концепций итераторов (см. на этой странице для списка всех из них ), и они являются иерархическими. Основы создания совместимого итератора C ++ - чтобы ваш интерфейс соответствовал концепции. Для простого итератора, который работает только в прямом направлении, для этого потребуется:

  • typedef value_type для значения, полученного в результате разыменования вашего итератора.
  • typedef reference_type, который является ссылочным типом для соответствующего типа значения.
  • typedef pointer, который является типом указателя для соответствующего типа значения.
  • typedef iterator_category, который должен быть одним из input_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag или random_access_iterator_tag, в зависимости от вашего механизма обхода.
  • typedef difference_type, указывающий результат вычитания двух разных итераторов.
  • A const value_type& operator*()const функция для разыменования итератора.
  • A value_type& operator*() функция, если ваш итератор может использоваться для манипулирования значением.
  • Инкремент (функции operator++() и operator++(int)) для поиска вперед.
  • Функция разности: difference_type operator-(const type_of_iterator&)

Если вы выберете одну из более продвинутых категорий итераторов, вам также может понадобиться указать оператор уменьшения и плюс, чтобы иметь возможность искать в обратном направлении или искать произвольное расстояние.

* Стандартная библиотека C ++ использует понятия так часто неформально, что комитет по стандартам C ++ попытался ввести формальный механизм их объявления в C ++ (в настоящее время они существуют только в документации стандартной библиотеки, а не в явном виде код). Однако постоянные разногласия в отношении этого предложения привели к тому, что оно было отклонено для C ++ 0x, хотя после этого оно, вероятно, будет пересмотрено для стандарта.

...