Disclaimer
Honour must be given to whom honour is due. Firstly, honour must be given to Bjarne Stroustrup for providing us with the C++ formalism with which we present our ideas. Secondly, honour must be given to Alexander Stepanov for presenting to us this style of reasoning, his ideas and hard-work have greatly changed the way programs are written.
All codes presented here are based on what the smart minds behind SGI STL have bequeathed to humanity. I do not make claim to the concepts, approaches detailed here but only provide explanations based on my understanding with the hope that it may be useful to some other programmer who cares about beautifully crafted components.
Motivation
What is a better way to put theory to test if not by implementation. I classify algorithms at Algorithmcity. Confident of my C++ skills, I applied at think-cell, I flunked the interview, I was humbled and needed to rethink my design approach. I was made to appreciate the difference between coding an algorithm and designing a useful software component. First I devoured most papers by Alexander Stepanov, then I set my eyes on the Standard Template Library and the Boost Library. This are some of the things I have learn’t when messing with this libraries.
Iterator Traits
Iterators are not complete without there associated types. We need a way to encode useful properties of iterators. When creating generic algorithms, this properties are need, say for example, you need to create a variable of the value type of a particular iterator, you should be able to have access to this value type.
Consider again that you need to know the iterator category or provide algorithm for a specific iterator class, you need a way to access all these.
STL uses the idea of an iterator trait class.
As show above the associated types of an iterator includes
- iterator category
- value_type
- difference_type
- pointer
- reference
1, 2 and 3 are most often used.
From the code above we can see that a partial specialization for the random access iterator denoted by a pointer was also included. In fact it is the main reason for the iterator traits class. Associated types for other iterators for structures like the linked list, binary tree can be called directly from there class definition but it is not same for the random access iterator based pointer to C style arrays.
std:: iterator_traits
Standard algorithms determine certain properties of the iterators passed to them and the range they represent by using the members of the corresponding iterator_traits instantiation.
For every iterator type, a corresponding specialization of iterator_traits class template shall be defined, with at least the following member types defined:
- input_iterator_tag
- output_iterator_tag
- forward_iterator_tag
- bidirectional_iterator_tag
- random_access_iterator_tag
The iterator_traits class template comes with a default definition that obtains these types from the iterator type itself (see below). It is also specialized for pointers ( T* ) and pointers to const ( const T* ).
Note that any custom class will have a valid instantiation of iterator_traits if it publicly inherits the base class std::iterator .
Name already in use
articles / cpp / 2018-05-10-std-iterator-deprecated.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
В STL C++17 устарело несколько компонентов, которые были с самого начала C++ и std::iterator один из них.
Скорее всего в вашем проекте не используется C++17 на данный момент. Но рано или поздно вам придётся его использовать. Лучше уже сегодня подготовиться и перестать использовать устаревшие компоненты STL.
Посмотрим как использовался std::iterator , почему он устарел и что использовать вместо него.
std::iterator использовался для указания особенностей итератора .
Обобщённый код, который использует интенсивно итераторы, такой как алгоритмы стандартной библиотеки, нуждается в информации о них. Например, ему нужен тип объекта, на который ссылается итератор. Чтобы получить эту информацию, стандартная библиотека требует, чтобы итератор объявил тип с именем value_type .
Для иллюстрации рассмотрим алгоритм std::reduce . Одна из его перегрузок принимает два итератора и возвращает сумму объектов, которые находятся между этими двумя итераторами:
Этот код выведет в консоль сумму всех элементов вектора number , которое равно 15 .
Но что если коллекция чисел будет пустой?
Что должен вывести этот код? В описании для функции std::reduce говорится, что она вернёт объект, который будет инициализирован значением по умолчанию, используя пустые фигурные скобки <> . В нашем случае это будет int<> , который имеет значение 0 .
Откуда std::reduce знает, что вектор number содержит элементы типа int ? Функция не работает с вектором напрямую, т.к. она взаимодействует с его итераторами, полученными из функций begin() и end() .
Вот почему итераторы должны объявлять тип value_type , который в данном случае является типом элементов вектора int .
Также может потребоваться получить информацию о возможностях итератора: может это итератор ввода, который поддерживает ++ , но не должен быть прочитан дважды? Или может это однонаправленный итератор, который можно прочитать несколько раз? Или это двунаправленный итератор, который поддерживает — ? Или это итератор произвольного доступа, где можно перемещаться с помощью операторов += , + , -= и — ? Или это итератор вывода?
Эта информация полезна для некоторых алгоритмов, которые будут эффективнее в зависимости от возможностей итератора. Такой алгоритм обычно имеет несколько реализаций и выбирается в зависимости от категории итератора.
STL требует, чтобы итераторы предоставляли тип iterator_category , который описывает категорию итератора. Существуют следующие категории:
- std::input_iterator_tag ,
- std::forward_iterator_tag ,
- std::bidirectional_iterator_tag ,
- std::random_access_iterator_tag ,
- std::output_iterator_tag .
Также STL требует ещё три типа у итератора, кроме value_type и iterator_category :
- difference_type : тип, который является результатом разницы двух итераторов;
- pointer : тип указателя на элемент, на который ссылается итератор;
- reference : тип ссылки на элемент, на который ссылается итератор.
Итого нужно итератору определить пять типов.
Все итераторы в стандартной библиотеке соответствуют этому (статическому) интерфейсу. Если вам нужно реализоваться свой собственный итератор, вам также необходимо определить эти типы.
Если вы хотите получить доступ к этим пяти типам у итератора, то можно подумать, что все итераторы определяют все эти пять типов. Например, можно получить тип элемента: Iterator::value_type .
Это почти всегда так, кроме одного исключения — когда итератор является указателем. Некоторые STL реализации используют указатели как итераторы вектора (арифметика указателей хорошо подходит для операций с итератором). Также может использоваться указатель в случае для итерирования по массиву в стиле языка Си.
В случае с указателем мы не можем получить тип элемента int*::value_type , т.к. указатель не имеет вложенных типов!
Чтобы решить эту проблему, предлагается не вызывать напрямую ::value_type или ::iterator_category , а использовать шаблон std::iterator_traits , который предоставляет все пять типов.
Если тип Iterator из шаблона std::iterator_traits<Iterator> не является указателем, то типы std::iterator_traits просто берутся у типа Iterator . Например:
будет означать что и:
Но если тип шаблона окажется указателем, скажем T* , то тогда std::iterator_traits<T*>::value_type вернёт тип T и тип std::iterator_traits<T*>::iterator_category всегда будет равен std::random_access_iterator_tag .
Шаблон std::iterator помогает объявить типы итератора, который принимает 5 шаблонных параметров:
Эти пять параметров нам уже знакомы, не так ли? Эти типы шаблона соотвествуют пяти типам, которые требует STL.
Задача шаблона std::iterator состоит в том, чтобы объявить эти типы. Вот возможная реализация std::iterator :
Чтобы использовать шаблон std::iterator для определения пяти типов — нужно наследоваться от него и передать как минимум два параметра, т.к. остальные три параметра имеют значения по умолчанию:
Теперь класс MyIterator имеет пять типов, которые требует STL от итераторов.
Зачем отказываться от использования std::iterator?
Этот шаблон кажется очень полезным, так зачем от него отказываться?
Важно отметить, что устарел только шаблон std::iterator . Это не касается пяти типов, которые должен определять итератор для предоставления информации о себе.
Теперь нужно отказаться от наследования от std::iterator для определения типов. Вот и всё!
Так что же не так с std::iterator ?
Давайте представим наследование от std::iterator с указанием пяти типов в качестве параметров:
В этом коде не ясно, какой тип передаётся каждому из типов итератора.
Более явный способ указать типы — написать декларации using (или typedefs , если вы используете стандарт до C++11) непосредственно внутри итератора:
Поэтому лучше определять типы внутри итератора явно, чем с помощью std::iterator . Такой код легче читать и меньше шанс сделать ошибку.
Также документ P0174 предлагает ещё причину для прекращения использования std::iterator . Отсутствие ясности кода ещё заметнее при определении итератора вывода:
Для того, чтобы убедить комитет стандартизации C++ отказаться от std::iterator достаточно было причины отсутствия ясности кода, но есть ещё одна причина данного подхода при наследовании: вы не можете обращаться напрямую к псевдонимам типов базового класса. Например, вы не можете получить тип value_type :
Также отмечено в LWG2438, что необходимо убрать std::iterator из STL, т.к. вводит пользователей в заблуждение, что их собственные итераторы должны использовать наследование std::iterator , а также функции могут получать std::iterator в качестве аргумента.
Минусы ручного определения типов
Нет определения типов по умолчанию
Мы уже упоминали, что std::iterator имеет три шаблонный параметра по умолчанию:
Поэтому было достаточно указать как минимум два обязательных типа:
Теперь нужно полностью определить все пять типов внутри вашего собственного итератора.
Случай с итератором вывода
Итератор вывода, такой как std::back_inserter (если быть точнее, то итератор сгенерированный этой функцией), также должны определять типы: iterator_category является std::output_iterator_tag , а остальные типы как void .
Последние четыре типа определяются как void , т.к. они не используются при работе с итераторами вывода. С std::iterator мы бы использовали для определения итератора вывода следующим образом:
Здесь всё равно пришлось указывать все пять типов.
Когда я узнал о том что std::iterator сделали устаревшим в C++17, то подумал, что причина в определении итераторов вывода.
Можно подумать, что для итератора вывода достаточно объявить только тип iterator_category , а остальные всё равно не используются:
Но этот код не выполняет требования STL по определению пяти типов для итератора, но может работать на некоторых платформах. Такой код не переносим на другие платформы. Правильно будет объявить все пять типов итератора:
Если вам интересно почему некоторые платформы позволяют использовать один тип iterator_category , а другие — нет, то мы рассмотрим реализацию std::iterator_traits в STL поставляемой с компиляторами GCC и Clang. Если вам это не важно, то можете переходить к разделу заключение. Главное помнить, чтобы код был переносимым нужно определять все пять типов у итератора.
Итак, почему некоторые платформы заставляют вас писать все 5 типов, даже если вы их не используете?
libstdc++, используемый GCC
Если вы посмотрите в исходный код libstdc++, используемый GCC, то вы увидите, что std::iterator_traits реализован следующим образом:
Если вы попытаетесь получить к одному любому типу из пяти, то тогда шаблон инстанцируется и определит типы, основываясь на типах _Iterator . Если хотя бы один тип не существует, то это приведёт к ошибке компиляции.
libc++, используемый Clang
И если вы посмотрите код в libc++, используемый Clang, то вы заметите, что std::iterator_traits здесь реализован по-другому чем в libstdc++:
Определение типов в этом коде нет непосредственно в std::iterator_traits . Эти определения типов находятся в базовом классе. Это очень важно, т.к. если вы попытаетесь использовать любой один тип в своём коде (например, iterator_category ), то ваш код скомпилируется, даже если отсутствует любой тип, даже value_type .
Честно говоря, я не знаю, какое языковое правило позволяет это сделать в этом случае. Если вы знаете, как это работает, то пожалуйста поделитесь знанием в комментариях.
GCC и Clang очень популярны при разработке и одна из платформ не поддерживает создание итератора без указания всех пяти типов. Все эти типы лучше определять, чтобы не было проблем с переносимостью кода.
std::iterator устарел и мы должны прекратить его использовать. В следующих стандартах может быть он удалён из STL как это случилось с std::auto_ptr .
Альтернативой использования std::iterator в C++03 является простое объявление пяти псевдонимов типов внутри ваших итераторов. Даже если ваш код не используется все пять псевдонимов — всё равно определите их, чтобы итератор соответствовал требованиям STL.
What are the typical use cases of an iterator_trait
I am new to C++ so please bear with me. I am trying to understand STL iterator_traits . In the book "The C++ Standard Library" the structure iterator_traits is defined as follows:
So it seems to me that it is re-exposing the subtypes that T already exposes. Moving ahead further, the book gives an example of how to use it, which is something like the following
My question is why do I need this iterator_traits structure here, if the idea was to obtain the value_type , couldn’t I have obtained it from MyIterator directly ? My confusion seems to arise from my (surely incorrect) understanding that the information of the subtypes have to be sourced from the template <class T> used to instantiate the iterator_trait . So if you could explain, and preferably with an example why and where would I need iterator_traits that would be very helpful.