Итераторы

Далее под итераторами мы будем иметь в виду 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 для вектора существует), но их можно использовать для дека.

 

Функциональные объекты

Функциональными объектами называются объекты (шаблоны объектов), к которым можно применять operator() с одним или двумя параметрами. Функциональные объекты служат заменой унарных или бинарных операций. Функциональные объекты используются в алгоритмах, в которых требуется указать операцию, которую необходимо применить для набора элементов в исходных контейнерах.

Существует набор стандартных (реализованных в STL) функциональных объектов. Например:

template <class T>struct plus : binary_function<T, T, T> {    T operator()(const T& x, const T& y) const { return x + y; } };

template <class T>struct minus : binary_function<T, T, T> {    T operator()(const T& x, const T& y) const { return x - y; } };

template <class T> struct negate : unary_function<T, T> {    T operator()(const T& x) const { return -x; } };

Ничто не мешает пользователю создавать свои функциональные объекты:

template <class T> struct sqr : unary_function<T, T> {    T operator()(const T& x) const { return x*x; } };

 

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

 

Алгоритмы

Алгоритмами называются шаблоны для работы (перебора/поиска/изменения и т.д.) с контейнерами.

Например, шаблон for_each(), используемый выше.

 

Алгоритм find() (find_if()):

vector<int> v;  vector<int>::iterator it;  v.resize(10);  for(it=v.begin();it!=v.end();++it)*it=(it-v.begin());

             it=find(v.begin(),v.end(),5);

             if(it!=v.end())cout<<*it<<endl;

 

 int v[10]; for(int i=0;i<10;i++)v[i]=i;

             it=find_if(v,v+10,Eq5);

             if(it!=v.end())cout<<*it<<endl;

 

Алгоритм поиска подпоследовательности в последовательности search():

vector<int> s; s.push_back(1);s.push_back(2);

  int x[]={1,1,2,3,4};

  int *it=search(x,x+sizeof(x), x.begin(),x.end());

  if(it==y+sizeof(y))cout<<"not found"<<endl;

  else cout<<"position="<<it-y<<endl;

 

Алгоритм partition() (stable_partition())  (используется поток вывода и итератор вывода):

vector<int> x; vector<int>::iterator it;  ostream_iterator<int> itOut(cout," ");

  for(int i=0;i<20;i++)  x.push_back(rand()%10-5);

  it=stable_partition<vector<int>::iterator>(x.begin(),x.end(),lt0);

  stable_partition<vector<int>::iterator>(it,x.end(),eq0);

  copy(x.begin(),x.end(), itOut); cout<<endl;

 

Алгоритм transform() (применяются функциональные объекты):

vector<int> x,y,z;

  for(int i=0;i<20;i++)  { x.push_back(rand()%10-5); y.push_back(rand()%10-5);}

  transform(x.begin(),x.end(), y.begin(), z.begin(), multiplies<int>());

 

Здесь следует обратить внимание на синтаксис использования функционального объекта (сравните с синтаксисом задания указателя на обычные функцию в предыдущем примере).

 

Алгоритм sort() (stable _sort ()):

 vector<int> v;  vector<int>::iterator it;  v.resize(10);  for(it=v.begin();it!=v.end();++it)*it=(it-v.begin());

             sort<vector<int>::iterator>(v.begin(),v.end(),comp);

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

 

Про эффективность алгоритма sort() можно судить по времени работы алгоритма на моем ноутбуке при работе под MSVisualStudio для массива из 108 случайных элементов (значение элемента задается как m0[i]=rand()|(rand()<<14)

) в сравнении с другими алгоритмами:

Алгоритм sort():                                                                 26сек

Стандартная функция qsort():                                         28сек

Алгоритм деления пополам с рекурсией из лекции:      34сек

Функция быстрой сортировки QSort2() из лекции:       22сек

 

Для `менее’ случайных элементов (значение элемента задается как m0[i]=rand()) имеем:

Алгоритм sort():                                                                 14сек

Стандартная функция qsort():                                         20сек

Алгоритм деления пополам с рекурсией из лекции:      17сек

Функция быстрой сортировки QSort2() из лекции:       13сек

 

 

Алгоритм copy():

  int m[5]={1,2,3,4,5}; vector<int> v(m+0,m+5),v2(m+0,m+5);

  copy(v.rbegin(),v.rend(), v2.begin());

  for_each(v2.begin(),v2.end(),print);cout<<endl;

 

Алгоритм copy_if():

  int m[5]={1,2,3,4,5}; vector<int> v(m+0,m+5),v2(m+0,m+5);

  copy_if(v.rbegin(),v.rend(), v2.begin(),funif);

  for_each(v2.begin(),v2.end(),print);cout<<endl;