Как работает категория итераторов в C ++?

Question

Я пытался понять реализацию итератора, и во время игры с источником я увидел следующее утверждение:

typedef output_iterator_tag iterator_category;

Я не понимаю, как эта typedef работает в классе?Какой побочный эффект это дает?Кто-нибудь может провести меня через это?

Answer 1

Вам нужно прочитать об общем программировании, потому что вы вряд ли получите этот ответ.

«Итератор вывода» - это концепция, которой соответствуют определенные итераторы. Каждый итератор, который является реализацией этой концепции, имеет определенные функциональные возможности, связанные с ним. Это как наследство, но это не так.

C ++ не имеет ничего такого, что представляло бы концепции (было предложено дополнение к C ++ 0x, но не смогло сделать это). В этом случае нам нужны различные конструкции шаблона, чтобы позволить нам связать «тег» с типом итератора. Связывая тип output_iterator_tag с итератором, мы утверждаем, что наш тип итератора реализует концепцию OutputIterator.

Это становится очень важным, когда вы пытаетесь написать алгоритмы, которые максимально оптимизированы, а также являются общими. Например, выполнение сортировки с помощью итератора, который может быть увеличен или уменьшен на произвольное значение (иными словами, чем 1), более эффективно, чем то, которое не имеет такой возможности. Кроме того, чтобы получить новый итератор, который находится на расстоянии X от другого, могут потребоваться различные операции в зависимости от возможностей итератора. Для написания такого алгоритма вы используете «диспетчеризацию тегов». Чтобы объяснить это более полно, вот реализация (непроверенная) std :: advance, которая работает как с итераторами, которые имеют оператор + =, так и с итераторами, которые имеют только оператор ++, и работает максимально быстро с обеими версиями.

template < typename RandomAccessIterator >
RandomAccessIterator advance( RandomAccessIterator it
                            , int amount
                            , random_access_iterator_tag) 
{ return it + amount; }

template < typename ForwardIterator >
ForwardIterator advance(ForwardIterator it, int amount, forward_iterator_tag)
{
  for (;amount; --amount) ++it;
  return it;
}

template < typename Iterator >
Iterator advance(Iterator it, int amount)
{
  typedef typename std::iterator_traits<Iterator>::iterator_tag tag;
  advance(it, amount, tag());
}

Это по памяти, так что, вероятно, оно пронизано ошибками (возможно, даже с кучей неправильных типов) ... но это идея. Теги итератора являются типами, которые являются пустыми и также наследуются друг от друга точно так же, как концепции улучшают друг друга. Например, итератор произвольного доступа является прямым итератором. Таким образом, random_access_iterator_tag является производной от forward_iterator_tag. Из-за правил разрешения перегрузки функции передача функции random_access_iterator_tag разрешается в эту версию функции, а не в версию forward_iterator_tag.

Опять, читайте об общем программировании. Важно использовать все возможности C ++.

Да, и наконец ... typedef есть в определении класса итератора, потому что это удобное и удобное место для его размещения. Итератор по умолчанию итератор может искать его там. Вы захотите использовать iterator_traits, а не это определение, хотя необработанные указатели также являются итераторами и не могут иметь внутренних typedefs.

Answer 2

output_iterator_tag - пустой класс.Его цель - позволить алгоритмам идентифицировать общие классификации итераторов, которые следуют определенным правилам и предоставляют конкретные операторы.Это позволяет алгоритмам предоставлять более специализированную реализацию данного алгоритма при определенных условиях.

Например, в заголовке VS2010 алгоритм "std :: distance" имеет две реализации в зависимости от typedef 'iterator_category'd в переданных итераторах.

std :: distance требуется только входной итератор для вычисления расстояния между двумя итераторами, но для вычисления ответа может потребоваться линейное 'O (n)' время.

Если, однако, компилятор выясняет, что используется итератор произвольного доступа, и, таким образом, может использовать оператор вычитания для вычисления расстояния в постоянное время 'O (1)'.

Iрекомендовал бы посмотреть видео Стефана Т. Лававея, где он немного разбирается в чертах типов и их использовании в стандартной библиотеке шаблонов.