C++ / Недооценённые итераторы

Речь пойдет о стандартной библиотеке шаблонов STL. Будут рассмотрены существующие типы итераторов и их классификация, а также будут предложены несколько новых обёрток над итераторами. Которые позволят в некоторых случаях избежать лямбда-выражений, которых до С++11 как бы и нет.

Вступительное слово

Одной из основных парадигм данной библиотеки было разделение двух сущностей. Контейнеров и алгоритмов. Но для непосредственного воздействия алгоритмом на данные контейнера пришлось ввести промежуточную сущность — итератор.

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

Типы итераторов в STL

Помимо итераторов, осуществляющих доступ к данным определённого контейнера в библиотеке STL имеются ещё несколько итераторов:
1. back_insert_iterator и front_insert_iterator
2. insert_iterator
3. istream_iterator и ostream_iterator

Итераторы типов back_insert_iterator и front_insert_iterator при модификации содержимого осуществляют вставку элемента методом push_back() или push_front(). Операции перемещения к предыдущему/следующему элементу контейнера эти итераторы попросту игнорируют.

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

Итераторы istream_iterator и ostream_iterator осуществляют считывание данных из потока и запись данных в поток. В конструкторы этих итераторов необходимо передать входной или же выходной поток.

Классификация итераторов

Существующая классификация итераторов насчитывает 5 категорий итераторов:
1. Input iterator
2. Output iterator
3. Forward iterator
4. Bidirectional iterator
5. Random access iterator

Итераторы, принадлежащие различным категориям имеют различный набор допустимых операций. Операции соотносятся с категориями следующим образом:

Разработка декоратора итератора

Для реализации нескольких следующих идей необходимо было реализовать обертку или декоратор (wrapper ^[1]). Декоратор итератора должен иметь ту же самую категорию, что и оборачиваемый итератор, а значит предоставлять тот же самый набор методов. В соответствии с приведённой таблицей категорий было разработано:
1. Пять классов-примесей (mixin ^[2]), реализующих не пересекающиеся наборы методов.
2. Шаблонный класс декоратора, параметризуемый категорией итератора.
3. Пять специализаций шаблона, отличающиеся набором подмешиваемых примесей.
4. Фабрика для удобного (без явных шаблонных параметров) обёртывания итератора.
[На этот код можно взглянуть здесь ^[3], он почти работает]

После небольшого обсуждения получившейся структуры с одним хорошим человеком была выработана новая структура. Не такая насыщенная шаблонами и более лаконичная. Решено было реализовать все методы всех категорий итераторов в одном шаблонном классе, параметризуемом категорией итератора. Было использовано следующее свойство языка C++: компилируются только те методы шаблонного класса, вызов которых реально осуществляется.

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

Битовый итератор

Битовый итератор позволяет обходить элементы контейнеров побитно. Итератор может использоваться как для считывания, так и для записи значений битов. У итератора имеются параметры:
1. В каком порядке обходить байты элементов контейнера
2. В каком порядке обходить биты в байтах

Пример использования:

{     // 00001010 00001011 00001010 00001011     //     * *      * **     * *      * **          char input[] = "x0Ax0Bx0Ax0B";     char * input_ptr = input;          int a = std::count(bit_walker(input_ptr),                        bit_walker(input_ptr+4), 1);      EXPECT_EQ(2 + 3 + 2 + 3, a); } 

Полевой итератор

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

{     // What to find:        [200]           "puper"     //     // {100,"hello"}     // {200,"super"} => {200,"super"}     // {300,"puper"}                  => {300,"puper"}          struct ABC     {         int value;         std::string str;     };          ABC input[] =      {         {100,"hello"},         {200,"super"},         {300,"puper"}     };     ABC * input_ptr = input;          int a = std::find(field_walker(input_ptr, fieldof(ABC,value)),                       field_walker(input_ptr+3, fieldof(ABC,value)),                       200) - input_ptr;      int b = std::find(field_walker(input_ptr, fieldof(ABC,str)),                       field_walker(input_ptr+3, fieldof(ABC,str)),                       "puper") - input_ptr;      EXPECT_EQ(1, a);     EXPECT_EQ(2, b); } 

Макрос fieldof(Class,Field) выглядит следующим образом:

#define fieldof(Object,field) (&(((Object*)NULL)->field)) 

Сортирующий итератор

Сортирующий итератор представляет из себя итератор, выполняющий обход элементов в порядке их сортировки. Элементы контейнера не модифицируются в процессе обхода итератором. Плюсом в данном случае является то, что время на сортировку не тратится (нет определённого участка времени отведённого под сортировку).

При перемещении итератора к следующему элементу осуществляется поиск наименьшего элемента среди оставшихся, которые больше-или-равны предыдущему. Таким образом сложность алгоритма получается O(N²), но специального времени отведённого под сортировку нет. Сортировка осуществляется в процессе обращения к данным. Обращение через итераторы осуществляется пошаговое — сортировка тоже пошаговая.

Итератор параметризуется порядком сортировки. По-умолчанию: сортировка по возрастанию.

Пример использования:

{     // A:{ 5,2,1,2,2 } => A:{ 5,2,1,2,2 }     // B:{ 0,0,0,0,0 } => B:{ 5,2,2,2,1 }      int input[5]  = { 5,2,1,2,2 };     int output[5] = { 0,0,0,0,0 };     int * input_ptr  = (int *)input;     int * output_ptr = (int *)output;      std::copy(sorter<Descending>(input_ptr,input_ptr+5),               sorter<Descending>(input_ptr+5),               output_ptr);      // Expect input     EXPECT_EQ(5, input[0]);     EXPECT_EQ(2, input[1]);     EXPECT_EQ(1, input[2]);     EXPECT_EQ(2, input[3]);     EXPECT_EQ(2, input[4]);      // Expect output     EXPECT_EQ(5, output[0]);     EXPECT_EQ(2, output[1]);     EXPECT_EQ(2, output[2]);     EXPECT_EQ(2, output[3]);     EXPECT_EQ(1, output[4]); } 

Примечания:

1. Таблица категорий итераторов позаимствована отсюда (в ней были найдены пара багов — сайт источник уведомлён об ошибках): http://www.cplusplus.com/reference/std/iterator/ ^[4]
2. Как многие из Вас могли заметить, примеры кода представляют из себя тесты для Google C++ Testing Framework ^[5], а значит код лежит в репозитории и к нему имеются тесты. Найдёте баг — пишите тест, выявляющий его)) Вот где лежит весь код: http://code.google.com/p/stliw/ ^[6] Комментарии к коду можно оставлять без регистрации — welcome.

P.S.
Данная статья была написана мной полгода назад. Сегодня я обнаружил её в практически законченном состоянии и опубликовал. Трудно сказать почему она полгода пролежала в моих черновиках. Может я хотел что-то доделать или переделать, в любом случае — публикую сейчас или никогда.

Автор: k06a