Improved Iterator Categories and Requirements

Boost , ,

Improved Iterator Categories and Requirements

Introduction

Examples of useful iterators that do not ``fit''

Из-за смешивания итератора и типа возврата отсчета многие полезные итераторы не могут быть соответствующим образом классифицированы. Например,vector::iteratorявляется почти итератором случайного доступа, но тип возврата неbool&(см.выпуск 96и статью Херба Саттера J16/99-0008 = WG21 N1185). Поэтому итераторы отвечают только требованиям входного итератора и выходного итератора. Это настолько нелогично, что по меньшей мере одна реализация ошибочно присваиваетrandom_access_iterator_tagв качестве егоiterator_category. Кроме того,vector— не единственный пример полезных итераторов, которые не возвращают истинных ссылок: есть часто приводимый пример дисковых коллекций.

Другой пример — итератор подсчета, итератор возвращает последовательность целых чисел при инкрементировании и отсчете (см.boost::counting_iterator). Существует два способа реализации этого итератора: 1) сделатьэталонныйтип истинной ссылкой (ссылка на целый элемент данных счетного итератора) или 2) сделатьэталонныйтип таким же, какзначение_тип. Вариант 1) сталкивается с проблемами, обсуждаемыми вВыпуске 198, ссылка не будет действительна после уничтожения итератора. Поэтому вариант 2) является лучшим выбором, но тогда у нас есть счетчик итератора, который не может быть итератором случайного доступа.

Еще одним примером является преобразующий итератор, адаптер итератора, который применяет объект унарной функции к сносному значению обернутого итератора (см.boost::transform_iterator). Для унарных функций, таких какstd::times, тип возврата оператора*явно должен бытьresult_typeобъекта функции, который обычно не является ссылкой. Однако при нынешних требованиях к итератору, если вы завернетеint*с преобразователем, вы получите не итератор случайного доступа, как ожидалось, а итератор ввода.

Четвертый пример можно найти в итераторах вершины и края библиотекиBoost Graph Library. Эти итераторы возвращают дескрипторы вершины и края, которые являются легкими ручками, созданными на лету. Они должны быть возвращены по стоимости. В результате их текущей стандартной категорией итераторов являетсяstd::input_iterator_tag, что означает, что, строго говоря, вы не можете использовать эти итераторы с такими алгоритмами, какstd::min_element().. В качестве временного решения мы представили концепциюMulti-Pass Input Iteratorдля описания дескрипторов вершины и края, но, как показывают примечания к концепции, требуется лучшее решение.

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

• Итераторы часто бывают пропущенными.
• Алгоритмические требования являются более строгими, чем это необходимо, поскольку они не могут отделить потребность в случайном доступе от потребности в истинном эталонном типе возврата.

Proposal for new iterator categories and requirements

• Читаемый итератор
• Итератор
• Итератор Swappable
• Постоянный итератор значений
• Изменяемый итератор значений

• Итератор поворота вперед
• Двунаправленный итератор поворотов
• Итератор случайного доступа

Примечание: мы рассмотрели определение одноместного итератора, который может быть объединен с читаемым или письменным итератором для замены требований к вводу и выводу итератора. Мы отвергли эту идею, потому что существует несколько различий между итераторами ввода и вывода, которые затрудняют их объединение: итератор ввода требует сопоставимого равенства, а итератор вывода - нет, а итератор ввода требует назначения, а итератор вывода - нет.

New categories and traits classes

namespace std {
  // Return Type Categories
  struct readable_iterator_tag { };
  struct writable_iterator_tag { };
  struct swappable_iterator_tag { };
  struct mutable_lvalue_iterator_tag : virtual public writable_iterator_tag,
    virtual public readable_iterator_tag { };
  struct constant_lvalue_iterator_tag : public readable_iterator_tag { };
  // Traversal Categories
  struct forward_traversal_tag { };
  struct bidirectional_traversal_tag : public forward_traversal_tag { };
  struct random_access_traversal_tag : public bidirectional_traversal_tag { };
}

namespace std {
  struct new_iterator_base { };
  template <typename Iterator>
  struct return_category
  {
    // Pseudo-code
    if (Iterator inherits from new_iterator_base) {
      typedef typename Iterator::return_category type;
    } else {
      typedef std::iterator_traits<Iterator> OldTraits;
      typedef typename OldTraits::iterator_category Cat;
      if (Cat inherits from std::forward_iterator_tag)
	if (is-const(T))
	  typedef boost::constant_lvalue_iterator_tag type;
	else
	  typedef boost::mutable_lvalue_iterator_tag type;
      else if (Cat inherits from std::input_iterator_tag)
	typedef boost::readable_iterator_tag type;
      else if (Cat inherits from std::output_iterator_tag)
	typedef boost::writable_iterator_tag type;
    }
  };
  template <typename T>
  struct return_category<T*>
  {
    // Pseudo-code
    if (is-const(T))
      typedef boost::constant_lvalue_iterator_tag type;
    else
      typedef boost::mutable_lvalue_iterator_tag type;
  };
  template <typename Iterator>
  struct traversal_category
  {
    // Pseudo-code
    if (Iterator inherits from new_iterator_base) {
      typedef typename Iterator::traversal_category type;
    } else {
      typedef std::iterator_traits<Iterator> OldTraits;
      typedef typename OldTraits::iterator_category Cat;
      if (Cat inherits from std::random_access_iterator_tag)
	typedef boost::random_access_traversal_tag type;
      else if (Cat inherits from std::bidirectional_iterator_tag)
	typedef boost::bidirectional_traversal_tag type;
      else if (Cat inherits from std::forward_iterator_tag)
	typedef boost::forward_traversal_tag type;
    }
  };
  template <typename T>
  struct traversal_category<T*>
  {
    typedef boost::random_access_traversal_tag type;
  };
}

Impact on the Standard Algorithms

The New Iterator Requirements

Notation

Readable Iterator

Associated Types

Refinement of

Valid expressions

Writable Iterator

Definitions

Associated Types

Refinement of

Valid expressions

Swappable Iterator

Примечание: требования к Swappable Iterator зависят от проблем, связанных с решениемstd::swap(). Здесь мы предполагаем, что проблема будет решена, разрешив перегрузкуstd::swap()для определенных пользователем типов.

Примечание: Readable Iterator and Writable Iterator Combined подразумевает Swappable Iterator из-за полностью шаблонизированногоstd::swap(). Однако Swappable Iterator не подразумевает ни Readable Iterator, ни Writable Iterator.

Associated Types

Valid expressions

Constant Lvalue Iterator

Refinement of

Associated Types