С++ для начинающих

       

Итераторы


Итератор предоставляет обобщенный способ перебора элементов любого контейнера– как последовательного, так и ассоциативного. Пусть iter является итератором для какого-либо контейнера. Тогда

++iter;

перемещает итератор так, что он указывает на следующий элемент контейнера, а

*iter;

разыменовывает итератор, возвращая элемент, на который он указывает.

Все контейнеры имеют функции-члены begin() и end().

  • begin() возвращает итератор, указывающий на первый элемент контейнера.
  • end() возвращает итератор, указывающий на элемент, следующий за последним в контейнере.
  • Чтобы перебрать все элементы контейнера, нужно написать:

    for ( iter = container. begin();

          iter != container.end(); ++iter )

        do_something_with_element( *iter );

    Объявление итератора выглядит слишком сложным. Вот определение пары итераторов вектора типа string:

    // vector<string> vec;



    vector<string>::iterator iter = vec.begin();

    vector<string>::iterator iter_end = vec.end();

    В классе vector для определения iterator используется typedef. Синтаксис

    vector<string>::iterator

    ссылается на iterator, определенный с помощью typedef внутри класса vector, содержащего элементы типа string.

    Для того чтобы напечатать все элементы вектора, нужно написать:

    for( ; iter != iter_end; ++iter )

        cout << *iter << '\n';

    Здесь значением *iter выражения является, конечно, элемент вектора.

    В дополнение к типу iterator в каждом контейнере определен тип const_iterator, который необходим для навигации по контейнеру, объявленному как const. const_iterator позволяет только читать элементы контейнера:

    #include <vector>

    void even_odd( const vector<int> *pvec,

                   vector<int> *pvec_even,

                   vector<int> *pvec_odd )

    {

        // const_iterator необходим для навигации по pvec

        vector<int>::const_iterator c_iter = pvec->begin();

        vector<int>::const_1terator c_iter_end = pvec->end();

        for ( ; c_iter != c_iter_end; ++c_iter )


            if ( *c_iter % 2 )

                pvec_even->push_back( *c_iter );

            else pvec_odd->push_back( *c_iter );

    }

    Что делать, если мы хотим просмотреть  некоторое подмножество элементов, например взять каждый второй или третий элемент, или хотим начать с середины? Итераторы поддерживают адресную арифметику, а значит, мы можем прибавить некоторое число к итератору:

    vector<int>::iterator iter = vec->begin()+vec.size()/2;

    iter получает значение адреса элемента из середины вектора, а выражение

    iter += 2;

    сдвигает iter на два элемента.

    Арифметические действия с итераторами возможны только для контейнеров vector и deque. list не поддерживает адресную арифметику, поскольку его элементы не располагаются в непрерывной области памяти. Следующее выражение к списку неприменимо:

    ilist.begin() + 2;

    так как для перемещения на два элемента необходимо два раза перейти по адресу, содержащемуся в закрытом члене next. У классов vector и deque перемещение на два элемента означает прибавление 2 к указателю на текущий элемент. (Адресная арифметика рассматривается в разделе 3.3.)

    Объект контейнерного типа может быть инициализирован парой итераторов, обозначающих начало и конец последовательности копируемых в новый объект элементов. (Второй итератор должен указывать на элемент, следующий за последним копируемым.) Допустим, есть вектор:

    #include <vector>

    #include <string>

    #include <iostream>

    int main()

    {

        vector<string> svec;

        string intext;

        while ( cin >> intext )

            svec.push_back( intext );

        // обработать svec ...

    }

    Вот как можно определить новые векторы, инициализируя их элементами первого вектора:

    int main() {

        vector<string> svec;

        // ...

        // инициализация svec2 всеми элементами svec

        vector<string> svec2( svec.begin(), svec.end() );

        // инициализация svec3 первой половиной svec

        vector<string>::iterator it =

                   svec.begin() + svec.size()/2;



        vector<string> svec3 ( svec.begin(), it );

        // ...

    }

    Использование специального типа istream_iterator (о нем рассказывается в разделе 12.4.3) упрощает чтение элементов из входного потока в svec:

    #include <vector>

    #include <string>

    #include <iterator>

    int mainQ

    {

        // привязка istream_iterator к стандартному вводу

        istream_iterator<string> infile( cin );

        // istream_iterator, отмечающий конец потока

        istream_iterator<string> eos;

        // инициализация svec элементами, считываемыми из cin;

        vector<string> svec( infile, eos );

        // ...

    }

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

    #include <string>

    string words[4] = {

        "stately", "plump", "buck", "mulligan"

    };

    Мы можем инициализировать вектор с помощью указателей на первый элемент массива и на элемент, следующий за последним:

    vector< string > vwords( words, words+4 );

    Второй указатель служит “стражем”: элемент, на который он указывает, не копируется.

    Аналогичным образом можно инициализировать список целых элементов:

    int ia[6] = { 0, 1, 2, 3, 4, 5 };

    list< int > ilist( ia, ia+6 );

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

    Упражнение 6.9

    Какие ошибки допущены при использовании итераторов:

    const vector< int > ivec;

    vector< string >    svec;

    list< int >         ilist;

    (a) vector<int>::iterator it = ivec.begin();

    (b) list<int>::iterator   it = ilist.begin()+2;

    (c) vector<string>::iterator it = &svec[0];

    (d) for ( vector<string>::iterator

               it = svec.begin(); it != 0; ++it )

        // ...

    Упражнение 6.10

    Найдите ошибки в использовании итераторов:

    int ia[7] = { 0, 1, 1, 2, 3, 5, 8 };

    string sa[6] = {

        "Fort Sumter", "Manassas", "Perryville", "Vicksburg",

        "Meridian", "Chancellorsvine" };

    (a) vector<string> svec( sa, &sa[6] );

    (b) list<int> ilist( ia+4, ia+6 );

    (c) list<int> ilist2( ilist.begin(), ilist.begin()+2 );

    (d) vector<int> ivec( &ia[0], ia+8 );

    (e) list<string> slist( sa+6, sa );

    (f) vector<string> svec2( sa, sa+6 );


    Содержание раздела