Motivation

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

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

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

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

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

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

Impact on the Standard

Это предложение для TR1 является чистым расширением. Кроме того, новые концепции итератора обратно совместимы со старыми требованиями итератора, а старые итераторы - с новыми концепциями итератора. Другими словами, итераторы, удовлетворяющие старым требованиям, также удовлетворяют соответствующим концепциям в новой системе, и итераторы, моделирующие новые концепции, автоматически удовлетворяют соответствующим старым требованиям.

Design

Требования к итератору должны быть разделены на две группы. Один набор понятий обрабатывает синтаксис и семантику доступа к стоимости:

• Читаемый итератор
• Письменный итератор
• Заменяемый итератор
• Lvalue итератор

Концепции доступа описывают требования, относящиеся к оператору* и оператору->, включая значение_тип, ссылка и поисковик ассоциированных типов.

Другой набор понятий обрабатывает прохождение:

• Необычный итератор
• Итератор Single Pass
• Вперед Traversal Iterator
• Двунаправленный итератор поворотов
• Случайный доступ Traversal Iterator

Соотношения уточнения для концепций прохождения находятся на следующей диаграмме.

В дополнение к операторам движения итератора, таким как оператор++, концепции обхода также включают требования к сравнению позиций, такие как оператор== и оператор<. Причина тонкого срезания концептов в Инкрементируемый и Единый проход состоит в том, чтобы предоставить концепции, которые точно соответствуют первоначальным требованиям итератора ввода и вывода.

Это предложение также включает в себя концепцию для определения, когда итератор совместим с другим итератором, в том смысле, что int* совместим с intconst*.

• Взаимодействующие итераторы

Связь между понятиями нового итератора и старого приведена на следующей диаграмме.

Как и в случае со старыми требованиями к итератору, мы предоставляем теги для отправки, основанные на концепциях обхода. Теги связаны через наследование, так что тег конвертируется в другой тег, если концепция, связанная с первым тегом, является уточнением второго тега.

Наш дизайн повторно использует iterator_traits::iterator_category, чтобы указать возможность прохождения итератора. Чтобы указать возможности, не захваченные какой-либо категорией итератора старого стиля, дизайнер итератора может использовать тип iterator_category, который конвертируется как в наиболее производный старый тег категории итератора, который подходит, так и в соответствующий новый тег обхода итератора.

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

Сложное дизайнерское решение касалось оператора . Прямой подход для определения оператор [] будет иметь тип возврата ссылка ; такой же, как оператор*. Однако движение в этом направлении будет означать, что итератор, удовлетворяющий старым требованиям Random Access Iterator, не обязательно будет моделью Readable или Writable Lvalue Iterator. Вместо этого мы выбрали дизайн, который соответствует предпочтительному разрешению , выпуск 299: оператор [] требуется только для возврата чего-либо конвертируемого в value_type (для Readable Iterator), и требуется поддержка назначения i[n] t (для Writable Iterator).

Proposed Text

 { X tmp = r; -r; возврат tmp; } 

 { Расстояние m = n; если (m >= 0) в то время как (m--) ++r; в то время как (m++) -r; возврат r; } 

// lib.iterator.traits, traits and tags
template <class Iterator> struct is_readable_iterator;
template <class Iterator> struct iterator_traversal;
struct incrementable_traversal_tag { };
struct single_pass_traversal_tag : incrementable_traversal_tag { };
struct forward_traversal_tag : single_pass_traversal_tag { };
struct bidirectional_traversal_tag : forward_traversal_tag { };
struct random_access_traversal_tag : bidirectional_traversal_tag { };

category-to-traversal(iterator_traits<X>::iterator_category)

category-to-traversal(C) =
    if (C is convertible to incrementable_traversal_tag)
        return C;
    else if (C is convertible to random_access_iterator_tag)
        return random_access_traversal_tag;
    else if (C is convertible to bidirectional_iterator_tag)
        return bidirectional_traversal_tag;
    else if (C is convertible to forward_iterator_tag)
        return forward_traversal_tag;
    else if (C is convertible to input_iterator_tag)
        return single_pass_traversal_tag;
    else if (C is convertible to output_iterator_tag)
        return incrementable_traversal_tag;
    else
        the program is ill-formed