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

Ответ 1

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

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

С++ не имеет ничего такого, что представляло бы концепции (было предложено дополнение к С++ 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.

Опять же, начните читать общие программы. Необходимо использовать всю мощь С++.

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

Ответ 2

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

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

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

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

Я бы порекомендовал наблюдать за тем, как Stephan T. Lavavej видео, где он немного разбирается в чертах типов и их использовании в стандартной библиотеке шаблонов.