немного про архитектуру STL итераторов

Рассматривая STL можно увидеть как элегантно и красиво можно проектировать иерархию классов и интерфейсы объектов.
Итак, запишу ка пару выводов, которые недавно заимел :)

1. Итератор - это обобщение понятия указателя для работы с различными структурами данных стандартным способом.
Поскольку итератор является обобщением понятия «указатель», семантика у них одинаковая, и все функции, принимающие в качестве параметра итераторы, могут также работать и с обычными указателями. Это достигается за счет применения шаблонов.

Всего существует пять типов итераторов, на рисунке представлена их иерархия.
Iterator types

Над любым итератором определены следующие операции:

  • Доступ к элементу последовательности, через операции * и ->.
  • Переход к следующему элементу.
  • Сравнение на равенство и не равенство между однотипными итераторами.

Пусть i,j - итераторы одного вида, х - переменная того же типа, что и элемент последовательности, n - целая величина. Тогда:

Входные (Input) итераторы поддерживают передачу данных из последовательности: x = *i;
Выходные (Output) поддерживаю передачу в последовательность *i = x;
Прямые (Forward) итераторы поддерживают все то, что поддерживают предыдущие в иерархии, т.е. x = *i; и *i = x;
Двунаправленные (Bidirectional) поддерживает всё то что и Forward, но и декремент (--).
Произвольного доступа (Random Access) поддерживают всё что и Bidirectional, плюс следующие операции: i-j, i+n, i-n, i += n, i -= n, так же полный набор операций <,<=,>,>=

Прямой итератор, может использоваться везде, где требуются входные или выходные итераторы. А двунаправленный везде, где требуется прямой ( если в метод/ф-ю передавать итератор по ссылке - в базовый тип можно передать производный, но на практике такого пока не видел )

Таблица видов итераторов по конкретным объектам
Iterator types
Зелёным - указаны итераторы (как правило это адаптеры итераторов, кроме потоковых, которые являются самостоятельными итераторами).
Синим - итераторы, объявленные/cозданные внутри контейнеров.

2. Итератор может быть действительным (когда он указывает на какой-то элемент последовательности) или недействительным (не был инициализирован, контейнер изменил размеры или уничтожен, итератор указывает на конец последовательности)

3. Можно сказать что итератор - является представителем объектов (контейнерного типа). В алгоритмы STL (алгоритмами в STL называются шаблонные ф-ии) не передаются сами объекты, а передаются их представители - итераторы, которые, как правило (пока не встречал другого) в алгоритмах используются для указания границ объектов контейнерного типа.

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

Чтобы получать из итератора информацию о элементе, на который они указывают, была введена структура

  1. template<class Iter> struct iterator_traits {
  2. typedef typename Iter::difference_type difference_type;
  3. typedef typename Iter::value_type value_type;
  4. typedef typename Iter::pointer pointer;
  5. typedef typename Iter::reference reference;
  6. typedef typename Iter::iterator_category iterator_category;
  7. };

Где:
Ключевое слово typename необходимо для того, чтобы компилятор мог опознать Iter как имя типа.
difference_type - тип для хранения разности Random Access итераторов (ptrdiff_t)
value_type - тип элемента
pointer - тип указателя на элемент
reference - ссылка на элемент
iterator_category - тип итератора.

Так же определена специализация данной шаблонной структуры для обычных указателей.

  1. template<class T> struct iterator_traits<T*> {
  2. typedef ptrdiff_t difference_type;
  3. typedef T value_type;
  4. typedef T* pointer;
  5. typedef T& reference;
  6. typedef random_access_iterator_tag iterator_category;
  7. };

С введением этой специализации, можно использовать итераторы с обычными массивами, и получать из этих массивов необходимые данные. Всю её полезность увидим ниже.

В этой структуре просто инкапсулированы типы, которые хранит в себе итератор, для удобства обращения к ним. Увидим это ниже, на примере обратного итератора.

Как же устроен итератор?

  1. template<class Category, class T, class Distance = ptrdiff_t,
  2. class Pointer = T*, class Reference = T&>
  3. struct iterator {
  4. typedef T value_type;
  5. typedef Distance difference_type;
  6. typedef Pointer pointer;
  7. typedef Reference reference;
  8. typedef Category iterator_category;
  9. };

/*Видно что данная структура описывает лишь типы данных но не сам итератор. Описание типов нужно для удобного наследования адаптеров итераторов. А сами же объекты - итераторы описываются внутри своих контейнеров. А структура выше просто содержит обязательные для итератора поля. Применение этой структуры можно посмотреть на примере адаптера reverse_iterator */

Посмотрим на его описание:

  1. template <class Iterator>
  2. class reverse_iterator : public
  3. iterator<typename iterator_traits<Iterator>::iterator_category,
  4. typename iterator_traits<Iterator>::value_type,
  5. typename iterator_traits<Iterator>::difference_type,
  6. typename iterator_traits<Iterator>::pointer,
  7. typename iterator_traits<Iterator>::reference> {
  8. protected:
  9. Iterator current;
  10. public:
  11. typedef Iterator iterator_type;
  12. typedef typename iterator_traits<Iterator>::difference_type difference_type;
  13. typedef typename iterator_traits<Iterator>::reference reference;
  14. typedef typename iterator_traits<Iterator>::pointer pointer;
  15.  
  16. reverse_iterator();
  17. explicit reverse_iterator(Iterator x);
  18. template <class U> reverse_iterator(const reverse_iterator<U>& u);
  19. template <class U> reverse_iterator& operator=(const reverse_iterator<U>& u);
  20.  
  21. Iterator base() const; // explicit
  22. reference operator*() const;
  23. pointer operator->() const;
  24.  
  25. reverse_iterator& operator++();
  26. reverse_iterator operator++(int);
  27. reverse_iterator& operator--();
  28. reverse_iterator operator--(int);
  29.  
  30. reverse_iterator operator+ (difference_type n) const;
  31. reverse_iterator& operator+=(difference_type n);
  32. reverse_iterator operator- (difference_type n) const;
  33. reverse_iterator& operator-=(difference_type n);
  34. operator[](difference_type n) const;
  35. };

К слову, в объекте обратного итератора содержится объект обыкновенного итератора current и операция инкремента в обратном итераторе, реализуется путем декремента этого итератора.

  1. template <class It> reverse_iterator<It>&
  2. reverse_iterator<It>::operator ++ ( )
  3. { --current; return *this; }

/* Вот на примере обратного итератора видно, зачем нужна struct iterator_traits. Казалось бы можно было бы обратиться на прямую к полям итератора, переданного в шаблон. Но это только для "нормальных итераторов". А что будет если это итератор на основе простого указателя? Вот тут то и пригождается интерфейс iterator_traits и его специализация*/

4. Алгоритму важен тип итератора.

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

Что здесь имеется в виду. А имеется, то что в зависимости от типов итераторов можно по разному реализовать, например алгоритмы stl::distance(InputIterator, InputIterator); и stl::advance(InputIterator &, Distance); Эти ф-ии для всех итераторов, кроме итераторов произвольного доступа выполняют работу с использованием операции ++ - т.е. время работы - пропорционально количеству "перескакиваемых" элементов. А вот для итераторов произвольного доступа существует иная реализация, благодаря которой перескакивание осуществляется за постоянное время (как при адресной арифметике)

Посмотрим подробнее, как это работает:

  1. template<class InputIterator, class Distance>
  2. void advance_impl(InputIterator& i, Distance n, std::random_access_iterator_tag) {
  3. i += n;
  4. }
  5.  
  6. template<class InputIterator, class Distance>
  7. void advance_impl(InputIterator& i, Distance n, std::bidirectional_iterator_tag) {
  8. if (n < 0) {
  9. while (n++) --i;
  10. } else {
  11. while (n--) ++i;
  12. }
  13. }
  14.  
  15. template<class InputIterator, class Distance>
  16. void advance_impl(InputIterator& i, Distance n, std::input_iterator_tag) {
  17. assert(n >= 0);
  18. while (n--) ++i;
  19. }
  20.  
  21. template<class InputIterator, class Distance>
  22. void advance (InputIterator& i, Distance n) {
  23. advance_impl(i, n,
  24. typename std::iterator_traits<InputIterator>::iterator_category());
  25. }

Алгоритм advance на самом деле является оберткой над конкретными реализациями. В нём используется обращение к шаблонному классу (структуре) которая будучи инициализирована итератором - предоставляет доступ к его типам (так же как это было в объявлении обратного итератора) и далее этот тип (а вернее объект соответствующего типа) передается в непосредственную реализацию алгоритма, который рализован в виде перегруженных шаблонных функций. Компилятору остаётся лишь выбрать правильную и создать пути по которым программа будет иметь возможность вызвать нужный вариант - для итераторов большинства контейнеров буде выбрана последовательная реализация, а для итераторов контейнеров поддерживающих операцию [] будет выбрана более быстрая реализация.

В реализациях функций _impl фигурирует параметр -тип итератора, который в теле ф-ии не используется, а служит лишь меткой для компилятора для выбора нужной перегруженной ф-ии по её интерфейсу.

Типы итераторов определены в заголовочном файле :

  1. struct input_iterator_tag { };
  2. struct output_iterator_tag { };
  3. struct forward_iterator_tag: public input_iterator_tag { };
  4. // функционал output здесь пишется руками, а не наследуется
  5. // как функционал input итератора
  6. struct bidirectional_iterator_tag: public forward_iterator_tag { };
  7. struct random_access_iterator_tag: public bidirectional_iterator_tag { };

Вот ещё небольшой пример, аналога алгоритма std::reverse, на нём видно польза шаблона iterator_traits как своего рода контейнера типов.

  1. #include <iostream>
  2. #include <iterator>
  3. #include <vector>
  4. #include <list>
  5.  
  6. template<class BidirIt>
  7. void my_reverse(BidirIt first, BidirIt last)
  8. {
  9. typename std::iterator_traits<BidirIt>::difference_type n = std::distance(first, last);
  10. --n;
  11. while(n > 0) {
  12. typename std::iterator_traits<BidirIt>::value_type tmp = *first;
  13. *first++ = *--last;
  14. *last = tmp;
  15. n -= 2;
  16. }
  17. }
  18.  
  19. int main()
  20. {
  21. int arr [] = {1, 2, 3, 4, 5};
  22. std::vector<int> v (arr, arr + 5);
  23. my_reverse(v.begin(), v.end());
  24. for ( std::vector<int>::iterator i=v.begin(); i != v.end(); ++i ) {
  25. std::cout << (*i) << ' ';
  26. }
  27. std::cout << std::endl;
  28.  
  29. std::list<int> l (arr, arr + 5);
  30. my_reverse(l.begin(), l.end());
  31. for ( std::list<int>::iterator i=l.begin(); i != l.end(); ++i ) {
  32. std::cout << (*i) << ' ';
  33. }
  34. std::cout << std::endl;
  35. }

5. Итераторы вставки.
Так же являются адаптерами итераторов, Рассмотрим итератор вставки в произвольное место.

  1. template <class Container>
  2. class insert_iterator :
  3. public iterator<output_iterator_tag,void,void,void,void> {
  4. protected:
  5. Container* container;
  6. typename Container::iterator iter;
  7. public:
  8. typedef Container container_type;
  9.  
  10. insert_iterator(Container& x, typename Container::iterator i);
  11. insert_iterator<Container>&
  12. operator=(const typename Container::value_type& value);
  13. insert_iterator<Container>&
  14. operator=(typename Container::value_type&& value);
  15.  
  16. insert_iterator<Container>& operator*();
  17. insert_iterator<Container>& operator++();
  18. insert_iterator<Container>& operator++(int);
  19. };

Что здесь примечательно?

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

Также его конструктор имеет два параметра - первый ссылка на контейнер вставки (именно контейнер а не итератор, как например в обратном), второй параметр - это итератор на место с которого идёт вставка.
Вот пример:

  1. // insert_iterator example
  2. #include <iostream> // std::cout
  3. #include <iterator> // std::insert_iterator
  4. #include <list> // std::list
  5. #include <algorithm> // std::copy
  6.  
  7. int main ( )
  8. {
  9. std::list<int> foo, bar;
  10. for (int i=1; i<=5; i++)
  11. { foo.push_back(i); bar.push_back(i*10); }
  12.  
  13. std::list<int>::iterator it = foo.begin();
  14. advance(it,3);
  15.  
  16. std::insert_iterator< std::list<int> > insert_it (foo,it);
  17.  
  18. std::copy (bar.begin(),bar.end(),insert_it);
  19.  
  20. std::cout << "foo:";
  21. for ( std::list<int>::iterator it = foo.begin(); it!= foo.end(); ++it )
  22. std::cout << ' ' << *it;
  23. std::cout << '\n';
  24.  
  25. return 0;
  26. // output: 1 2 3 10 20 30 40 50 4 5
  27. }

Примечательно, что данный тип итератора увеличивает размер контейнера (вызывая внутри себя метод insert своего внутреннего контейнера). Обычные же итераторы, могут только "читать" контейнер - т.е. только изменять его элементы но не изменять их количество. Т.е. в алгоритме std:copy если бы использовался обычный итератор в третьем параметре, то в случае если диапазон первых двух параметров оказался бы длиннее чем размер контейнера, то вставка бы не осуществилась до конца. И копирование было бы замещающим (как печатать текст в режиме insert) а не дополняющим.

Для каждого итератора вставки существует своя ф-я обёртка, позволяющая использовать более компактный код. Вот аналог программы выше, использующий ф-ю вставки, а не непосредственно итератор.

  1. // inserter example
  2. #include <iostream> // std::cout
  3. #include <iterator> // std::front_inserter
  4. #include <list> // std::list
  5. #include <algorithm> // std::copy
  6.  
  7. int main () {
  8. std::list<int> foo, bar;
  9. for (int i=1; i<=5; i++)
  10. { foo.push_back(i); bar.push_back(i*10); }
  11.  
  12. std::list<int>::iterator it = foo.begin();
  13. advance (it,3);
  14.  
  15. std::copy (bar.begin(),bar.end(),std::inserter(foo,it));
  16.  
  17. std::cout << "foo contains:";
  18. for ( std::list<int>::iterator it = foo.begin(); it!= foo.end(); ++it )
  19. std::cout << ' ' << *it;
  20. std::cout << '\n';
  21.  
  22. return 0;
  23. }
  24. // output: 1 2 3 10 20 30 40 50 4 5

Но как в алгоритм (который хочет разыменовывать и инкрементировать свой третий параметр) передается функция? Ведь над ней не определены эти операции.

  1. template<class InputIterator, class OutputIterator>
  2. OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
  3. {
  4. while (first!=last) {
  5. *result = *first;
  6. ++result; ++first;
  7. }
  8. return result;
  9. }

Всё очень просто - ф-я inserter - является всего лишь обёрткой, которая конструирует нужный итератор вставки и возвращает его - т.е. в алгоритм попадает уже готовый итерартор вставки

  1. template <class Container, class Iterator>
  2. std::insert_iterator<Container> inserter( Container& c, Iterator i )
  3. {
  4. return std::insert_iterator<Container>(c, i);
  5. }

Рассмотрим ещё один выходной итератор - итератор выходного потока.

  1. /*
  2.   * @tparam _Tp The type to write to the ostream.
  3.   * @tparam _CharT The ostream char_type.
  4.   * @tparam _Traits The ostream char_traits.
  5. */
  6. template
  7. <typename _Tp, typename _CharT = char, typename _Traits = char_traits<_CharT> >
  8. class ostream_iterator
  9. : public iterator<output_iterator_tag,void,void,void,void>
  10. {
  11. public:
  12. typedef _CharT char_type;
  13. typedef _Traits traits_type;
  14. typedef basic_ostream<_CharT, _Traits> ostream_type;
  15.  
  16. private:
  17. ostream_type* _M_stream;
  18. const _CharT* _M_string;
  19.  
  20. public:
  21. ostream_iterator(ostream_type& __s) : _M_stream(&__s), _M_string(0) {}
  22.  
  23. // Второй параметр конструктора - строка разделитель
  24. ostream_iterator(ostream_type& __s, const _CharT* __c)
  25. : _M_stream(&__s), _M_string(__c) { }
  26.  
  27. /// Copy constructor.
  28. ostream_iterator(const ostream_iterator& __obj)
  29. : _M_stream(__obj._M_stream), _M_string(__obj._M_string) { }
  30.  
  31. // M_stream это строка, которая передается в конструкторе
  32. ostream_iterator&
  33. operator=(const _Tp& __value)
  34. {
  35. *_M_stream << __value;
  36. if (_M_string)
  37. *_M_stream << _M_string;
  38. return *this;
  39. }
  40.  
  41. ostream_iterator&
  42. operator*()
  43. { return *this; }
  44.  
  45. ostream_iterator&
  46. operator++()
  47. { return *this; }
  48.  
  49. ostream_iterator&
  50. operator++(int)
  51. { return *this; }
  52. };

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

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

Вот такие вот красивости существуют в STL. Так же хочется упомянуть например про контейнер словарь (std::map). Почему бы не хранить пару элементов как они есть? В словаре вводится тип pair. Потому что благодаря инкапсуляции данного типа - код словаря очень похож на код, скажем множества (std::set) - т.е. элемент value_type есть уже некоторая пара а не просто единичный элемент, но внешне он остаётся единичным элементов, и внешний код остаётся прежним. Более того пара (std::pair) обладает всеми свойствами полноценного типа, и может пихаться в тот же std::set :) если уж на то пошло.

В общем изучая STL начинаешь понимать ООП лучше, и всё богатство шаблонов, наследования, и проектирования интерфейсов.

Используемый материал.

Павловская, "С/C++ Программирование на языке высокого уровня"
и эти ссылки:
ссылка 1 - отвлеченный пример.
ссылка 2 - более практический пример.
ссылка 3 - хорошее описание заголовочного файла итераторов.

Комментарии

Аватар пользователя Илья Лесной

Стоит упомянуть, что описанный выше класс (структура) итератора по сути является своего рода контейнером, для хранения типов итератора, а вернее, типов, описывающих элемент, на который указывает итератор. И всё. Назовем struct iterator - "контейнером_типов".

Далее.

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

А что же например, в списке или деке или остальных "итераторных" контейнерах? ( на примере GNU реализации STL )

Там свои реализации классов(структур) итераторов, со своими операциями (в отличии от итератора вектора, для которого хватает стандартных операций, определенных над указателями) и именно эти структуры являются типами для объектов - итераторов контейнеров.

  1. //итератор листа, объявлен в bits/stl_list.h
  2. typedef _List_iterator<_Tp> iterator;
  3. //итератор дека, объявлен в bits/stl_deque.h
  4. typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;

При этом, эти структуры все сами по себе, и ни от кого не наследуются, но имеют внутри себя все те же поля, что и упоминаемый нами "контейнер типов" struct iterator.

Давайте заметим, что struct iterator_traits и struct iterator по сути одно и тоже, и ниже увидим чем же оправдано существование _traits.

Далее уже чуточку интереснее:

  1. typedef std::reverse_iterator<iterator> reverse_iterator;
  2. typedef std::reverse_iterator<iterator> reverse_iterator;

В контейнерах по сути нет никакого настоящего обратного итератора - он получается из структуры обратного итератора, описанной выше, которая наследуется от обычной пустой struct iterator, но имеет полный набор своих операций и инкапсулирует в себя и объект-итератор, с которым она была сконструирована.

Таким образом, когда мы создаём итератор

  1. list <int>:: iterator itL(myList.begin());
  2. //или
  3. map <string, int, less<string> >::iterator itM = m.find(word);

Создаются объекты абсолютно разных типов (да, имеющие общие свойства внутри, но они абсолютно разные для компилятора).

Ну и далее, наконец то приходим к изюминке - "алгоритмы", чтобы добраться до типа элемента контейнера, используют унифицированный "контейнер_типов" правда конечно не на прямую struct iterator а через обёртку struct iterator_traits.

Может возникнуть вопрос: зачем нужна обёртка iterator_traits, когда в алгоритмах поля итератора можно получить непосредственно из типа итератора.

  1. template<class InputIterator, class Distance>
  2. void advance1 (InputIterator& i, Distance n) {
  3. std::cout << "hello\n";
  4. advance_impl(i, n,
  5. typename std::iterator_traits<InputIterator>::iterator_category());
  6. }
  7.  
  8. template<class InputIterator, class Distance>
  9. void advance2 (InputIterator& i, Distance n) {
  10. std::cout << "hello\n";
  11. advance_impl(i, n,
  12. typename InputIterator::iterator_category());
  13. }

Да, это так, но это для тех случаев, когда тип итератора - является некоторый пользовательский тип-объект. А если у нас в "алгоритм" попадает указатель на обычный массив или же итератор на вектор, то второй вариант уже не применим, т.к. данные типы не имеют тех полей, к которым будет обращаться алгоритм - например InputIterator::iterator_category().

кстати заметили скобочки? А они здесь потому, что создается безымянный объект указанного типа, который имеет конструктор, и именно так можно осуществить его вызов. Это нужно, когда ф-я приёмник, должна иметь в своих входящих параметрах явно существующий объект (например как перегруженные advance_imp, для того чтобы компилятор мог выбрать нужную). Если бы передавали без скобочек - ::iterator_category, то мы бы просто упомянули тип, но передали бы объект, и компилятор бы нас не понял. Просто этот момент иногда не совсем явный для понимания (имхо). При этом, в данном случае созданный объект использоваться не будет, а служит лишь для создания пути компилятору.. Например здесь в bubble_sort_imlp используется тот же подход, но в вызывающей ф-ии скобочек нет. И вот разность этого и побудило меня уделить этому столько строк. А скобочек там нет - потому что передается уже не тип - а готовый объект. Т.е. в нашем случае можно было бы сделать и так:

  1. emplate<class InputIterator, class Distance>
  2. void advance (InputIterator& i, Distance n) {
  3. typename std::iterator_traits<InputIterator>::iterator_category cat;
  4. advance_impl(i, n, cat );
  5. }

Но первый вариант предпочтительнее - нет лишней переменной, хотя и создается лишний объект, но зато это экономит код (текстовый). Иначе пришлось бы придумывать ф-ии с разными именами, или придумывать более сложные интерфейсы - которые содержали бы "не лишние" объекты, но тратили на свое создание больше бы ресурсов.

Вот тут-то и пригодится шаблон iterator_traits, который служит дополнительным связывающим звеном между итераторами (которые могут или не могут иметь поля, и алгоритмами), т.е. iterator_traits для объектов-итераторов просто возвращает их же поля, а для указателей-итераторов (через свою специализацию) генерирует те поля которых нет у простых указателей. [еще один пример полезности этой шаблонной структуры]

Красиво. Если честно, пока сложно весь этот пласт держать в голове, но позже попробую визуализировать это :)

В информации выше есть намеренная оговорка про вектор. Про то что итератор вектора является указателем. Такая оговорка существует в качестве ошибки, в частности есть в моей любимой книге Подбельской по Си++, или например здесьтоже фигурирует. А все потому что действительно существует шаблонный класс вектор, в котором объявлен итератор как typedef T * int;, но только вот этот вектор принадлежит не STL а библиотеке libitm. Тогда выкладки про нужность struct iterator_traits VS struct iterator становятся справедливыми только для указателей, и возможно для нестандартных (пользовательских) контейнеров, в качестве примера - того же вектора из libitm. Ну и так же очевидно, что над итератором вектора тоже определены именно свои операции.

Ну и в добавок, специализировать такую обертку как iterator_traits указателей намного проще ( по писанине ) чем специализировать iterator для указателей.

Вот как-то так.