Итераторы
Итератор предоставляет обобщенный способ перебора элементов любого контейнера– как последовательного, так и ассоциативного. Пусть 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 }; |
В разделе 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 ); |