Итераторы

Далее под итераторами мы будем иметь в виду STL-итераторы.

Максимально упрощенный подход

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

Итераторы не используются для работы с очередью и приоритетной очередью.

Существует несколько типов итераторов (!!!), но пока не будем заострять на этом внимания. Для каждого контейнера существует свой тип итератора, который можно использовать для работы с данным контейнером:

vector::iterator

list::iterator

deque::iterator

и т.д.

 

но все они имеют одинаковый (на самом деле, не всегда) набор функций, что унифицирует работу с итераторами.

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

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

iterator begin()                       возвращает итератор, указывающий на первый элемент в контейнере

iterator end()              возвращает итератор, указывающий на элемент, следующий после последнего элемента в контейнере

iterator rbegin()          возвращает итератор, указывающий на первый элемент в контейнере для обратного перебора элементов

iterator rend()             возвращает итератор, указывающий на элемент, следующий после последнего элемента в контейнере, используемого при обратном переборе элементов

 

К итераторам применима префиксная операция ++, возвращающая итератор, указывающий на следующий элемент в контейнере (постфиксная операция ++ тоже может существовать, но это нечто более сложное).

К итераторам применима префиксная операция *, возвращающая значение элемента данных, содержащееся в элементе контейнера, на который указывает итератор.

Приведем пример перебора элементов контейнер set.

  set<int> v;  set<int>::iterator it;

  v.insert(2);v.insert(1);v.insert(3);v.insert(4);v.insert(4);

  for(it=v.begin();it!=v.end();++it)cout<<*it<<" ";

 

Итераторы ввода

Все, что было сказано в предыдущем разделе относится к итераторам ввода. Под вводом имеется в виду ввод данных из контейнера в окружающую программу (например, ввод данных из контейнера требуется при выводе содержимого контейнера на экран). Полный список операций для итераторов различных типов можно найти, например, в вышеприведенной книге Александра Степанова. Итераторы ввода поддерживают только перемещение вперед по элементам контейнера и дают возможность получить значение элемента в контейнере без права его изменения. Итераторы ввода можно присваивать друг другу и их можно сравнивать на равенство/неравенство.

istream_iterator<int> itIn,itEnd=istream_iterator<int>(); int m[10],n;

  ostream_iterator<int> itOut(cout," ");

  itIn=cin;

  for(n=0;itIn!=itEnd;++itIn,n++)m[n]=*itIn;

  for_each(m,m+n,print);cout<<endl;

Итераторы вывода

Итераторы вывода не дают возможности для сравнения итераторов, но для них можно использовать оператор * слева от знака присваивания.

vector<int> v; v.resize(10); size_t n;

  istream_iterator<int> it; ostream_iterator<int> itOut(cout," ");

  for(it=cin,n=0;it!=istream_iterator<int>();++it,n++)v[n]=*it;

  for(vector<int>::iterator it=v.begin();it!=v.end();++it)*itOut=*it;  cout<<endl;

Последовательные итераторы

Последовательные итераторы объединяют возможности итераторов ввода и вывода.

Двунаправленные итераторы

Двунаправленные итераторы поддерживают все свойства последовательных итераторов плюс операцию -- . Например, итераторы ассоциативных контейнеров является двунаправленными:

  multimap<int,double> v; multimap<int,double>::iterator it;

  v.insert(pair<int,int>(1,1));v.insert(pair<int,int>(2,2));v.insert(pair<int,int>(3,40));v.insert(pair<int,int>(4,30));v.insert(pair<int,int>(4,40));

  it=v.find(4);  cout<<"[4]="<<it->second<<endl;

  --it; cout<<"[3]="<<it->second<<endl;

Итераторы произвольного доступа

К свойствам двунаправленного итератора добавляются возможности прибавления/вычитания целого числа и оператор []. Например, итератор вектора (vector) является итератором произвольного доступа.

  vector<int> v;  vector<int>::iterator it;  v.resize(10);

  for(it=v.begin();it!=v.end();++it)*it=(it-v.begin());

  for_each(v.begin(),v.end(),print);

Итераторы вставки

Все вышеперечисленные итераторы позволяют перебирать и модифицировать элементы контейнеров, но для списков требуется дополнительная операция вставки, поэтому, соответственно, пришлось создавать итератор вставки. Достаточно рассмотреть итераторы вставки в начало объекта, в хвост объекта и на определенную позицию объекта. Начнем с того, что полегче J

inserter              - функция, возвращающая итератор вставки на определенную позицию

back_inserter  - функция, возвращающая итератор вставки в хвост контейнера

front_inserter  - функция, возвращающая итератор вставки в голову контейнера

int x[]={1,2,3,4,5}; list<int> l; list<int>::iterator it;

  copy(x,x+sizeof(x)/sizeof(x[0]), front_inserter<list<int>>(l));//вставляем в начало

  copy(x,x+sizeof(x)/sizeof(x[0]), back_inserter<list<int>>(l));//вставляем в конец

  it=l.begin(); ++it;

  copy(x,x+sizeof(x)/sizeof(x[0]), inserter<list<int>>(l,it));//вставляем со второй позиции (после первого элемента)

  copy(l.begin(),l.end(), ostream_iterator<int>(cout," ")); cout<<endl;

 

Не плохо понимать, что происходит в предыдущем примере. В нем используются не итераторы, а функции, возвращающие итераторы. В следующем примере итераторы используются напрямую (это сложнее!!!)

inserter              - функция, возвращающая итератор вставки на определенную позицию

back_inserter  - функция, возвращающая итератор вставки в хвост контейнера

front_inserter  - функция, возвращающая итератор вставки в голову контейнера

int x[]={1,2,3,4,5}; list<int> l; list<int>::iterator it;

  front_insert_iterator<list<int>> itF(l);

  copy(x,x+sizeof(x)/sizeof(x[0]), itF);

  back_insert_iterator<list<int>> itB(l);

  copy(x,x+sizeof(x)/sizeof(x[0]), itB);

  copy(l.begin(),l.end(), ostream_iterator<int>(cout," ")); cout<<endl;

  insert_iterator<list<int>> itI(l,++l.begin());

  copy(x,x+sizeof(x)/sizeof(x[0]), itI);

  copy(l.begin(),l.end(), ostream_iterator<int>(cout," ")); cout<<endl;

 

Надо помнить, что итераторы вставки используются только для вставки!!! Эта фраза подразумевает, что, например, в последнем примере операция ++itI не приведет к изменению позиции итератора (хотя, синтаксически не приведет к ошибке!).

Не удается использовать итераторы вставки для вектора и ассоциативных контейнеров (хотя, функция insert для вектора существует), но их можно использовать для дека.