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

    Речь пойдет о стандартной библиотеке шаблонов 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

    Итераторы, принадлежащие различным категориям имеют различный набор допустимых операций. Операции соотносятся с категориями следующим образом:
    Категория итератора Характеристика Валидное выражение
    все категории Может быть скопирован и создан по образу и подобию X b(a);
    b = a;
    Может быть увеличен на единицу ++a
    a++
    *a++
    Random Access Bidirectional Forward Input Поддерживает сравнение на равенство/неравенство a == b
    a != b
    Может быть разыменован как rvalue только для получения значения *a
    a->m
    Output Может быть разыменован как lvalue для использования слева от знака присваивания *a = t
    *a++ = t
    Может быть скопирован и использован для повторного обхода X a(b);
    ++a == ++b
    Может быть уменьшен на единицу --a
    a--
    *a--
    Поддерживает арифметические операции + и - a + n
    n + a
    a — n
    a — b
    Поддерживает сравнения (<, >, <= and >=) между итераторами a < b
    a > b
    a <= b
    a >= b
    Поддерживает операции увеличения += и уменьшения -= a += n
    a -= n
    Поддерживает разыменование по индексу ([]) a[n]

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


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

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

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

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


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

    Пример использования:
    {
        // 00001010 00001011 00001010 00001011
        //     * *      * **     * *      * **
        
        char input[] = "\x0A\x0B\x0A\x0B";
        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))
    

    UPD
    Как заметил пользователь mayorovp, можно было обойтись указателем на поле класса:

    &Object::field
    


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


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

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

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

    Пример использования:
    {
        // 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/
    2. Как многие из Вас могли заметить, примеры кода представляют из себя тесты для Google C++ Testing Framework, а значит код лежит в репозитории и к нему имеются тесты. Найдёте баг — пишите тест, выявляющий его)) Вот где лежит весь код: http://code.google.com/p/stliw/ Комментарии к коду можно оставлять без регистрации — welcome.

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

    Комментарии 16

      +3
      По поводу полевого итератора:
      чем же вам не угодила такая конструкция С++, как указатель на поле?

      #define fieldof(Object,field) (&Object::field)
        +1
        Ни разу не использовал указатель на поле на практике) Потому получился костыль. Спасибо, сейчас впишу в статью.
          +1
          Вы это изменение тестировали?

          А то у вас получается, будто простое изменение макроса все упрощает. А там еще нужно шаблон редактировать.
            +1
            Еще не протестировал, да похоже простой заменой не обойтись… Придется поколдовать. Я сейчас далеко от компа. Сегодня не допилю…
          +1
          Есть же стандартный макрос для сего дела: offsetof (http://www.cplusplus.com/reference/clibrary/cstddef/offsetof/).
          Делает тоже самое кстати. Но не хочется плодить лишние сущьности )
            +1
            В моем макросе сохраняется информация о типе поля и смещении. А offsetof дает только смещение…
              +1
              Точно. Вот что значит програмить в основном на сях последние 3 года…
                +1
                Сурово) Откуда такой спрос на Си?
                Производительность весьма критична?
                  +1
                  В принципе да. Производительность критична. Пишу прилаги для мобильных устройсв под управлением iOS. В принципе С++ тоже юзаю но гораздо реже. Всетаки Obj-C + С гораздо удобнее юзать чем Obj-C + C++.
                +1
                И ЕМНИП он UB.
            +4
            На мой взгляд, в таблице упущена одна из самых важных особенностей Forward Iterators, которая выгодно отличает их от Input/Output Iterators — возможность повторного прохода! На этом стоит поставить акцент.

            Кроме того, весьма удивлен положению пункта «Может быть создан без параметров». Для Input/Output Iterators это тоже справедливо, ведь именно так и создается итератор, указывающий на конец абстрактной последовательности данных.
              +2
              Действительно. Спасибо, сегодня поправлю таблицу.
              +3
              Любителям итераторов рекомендую Александреску:

              www.informit.com/articles/printerfriendly.aspx?p=1407357

              совсем другой подход.
                +2
                Я уже проникся Range-ами Александреску) Об этом отдельную статью возможно напишу. Понравилась его презентация «Iterators Must Go».
              0
              Чтобы не описывать в реализации кучу однотипных операций (типа +=, +, []), в качестве указанного декоратора удобно использовать boost::iterator_adaptor. Он все такие функции определяет через примитивные операции типа increment/decrement/advance etc.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое