STL Итераторы Категории итераторов

Опубликовано 20.10.2012 | Автор: admin

Продолжая знакомство с итераторами, посмотрим на различные их категории.

Итераторы подчиняются принципу чистой абстракции, то есть любой объект, который ведет себя как итератор, является итератором.

Категории итераторов:

Итераторы ввода и вывода
Однонаправленные итераторы и двунаправленные итераторы
Итераторы произвольного доступа
Вспомогательные итераторы
Реверсивные итераторы
Итераторы потоков
Итераторы вставки
Константные итераторы

Итератор ввода — это такой итератор, который перемещается только вперед и поддерживает только чтение.

Итератор ввода — это самая простая разновидность итераторов. Доступны такие итераторы только для чтения. Чтобы узнать прочтённый элемент, к итератору применяется оператор разыменования (как с указателем). Иногда может потребоваться узнать, указывают ли два итератора ввода на один и тот же объект, для этого разрешено сравнивать два итератора ввода между собой. Вместо итератора ввода может подставляться любой основной итератор кроме итератора вывода.

В моём представлении самым простым примером итератора ввода будет вывод на экран элементов массива с помощью итератора ввода:

//C++		Листинг #1		Итератор ввода
#include <algorithm>    //нужен для алгоритма  for_each
#include <iostream>

using namespace std;             //нужно пространство имен std

void printValue(int num){        //эту функцию надо передавать в алгоритм for_each
  cout << num << "\n";           //выводим параметр функции на экран (num в студию)
}

int main(){
  int Arr[] = {1, 2, 3, 4, 5};      //массив 
  for_each(Arr, Arr + 5, print);    //алгоритм for_each принимает три указателя
}

//C++ Листинг #1 Итератор ввода

#include <algorithm> //нужен для алгоритма for_each

#include <iostream>

using namespace std; //нужно пространство имен std

void printValue(int num){ //эту функцию надо передавать в алгоритм for_each

cout << num << "\n"; //выводим параметр функции на экран (num в студию)

}

int main(){

int Arr[] = {1, 2, 3, 4, 5}; //массив

for_each(Arr, Arr + 5, print); //алгоритм for_each принимает три указателя

}

for_each — это алгоритм. Алгоритм for_each принимает указатель на начало массива, указатель на первый элемент за границей массива и указатель на функцию. Не путайте саму функцию с указателем на нее. Кто не понял, при чем тут итератор, читайте самые первые строки. Еще может кому-то не очень понятен параметр num. В этот параметр записывается значение, которое получил алгоритм for_each. Подробней про for_each написано в теме C++ для начинающих. Алгоритм for_each

В качестве ещё одного примера можно взять заполнение контейнера STL из текстового файла (заполнение с помощью итератора ввода).

//C++		Листинг #2		Итератор ввода
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
int main()
{
      /*СОЗДАЕМ ФАЙЛ*/
	 const char FName[] = "D:/1.txt";      //Путь должен быть корректным
	 ofstream out(FName);
      out<<"1\n";
      out<<"2\n";
      out<<"3\n";	
	 out.close();

      /*ИСПОЛЬЗУЯ ИТЕРАТОР ВВОДА, ЗАПИСЫВАЕМ В ВЕКТОР ДАННЫЕ ФАЙЛА*/
	 ifstream f(FName);
	 vector<char> v((istreambuf_iterator<char>(f)),
                     istreambuf_iterator<char>());

	 vector<char>::iterator it;
	 
	 for (it=v.begin();it!=v.end();it++){
         cout<<*it;
	 }
}

//C++ Листинг #2 Итератор ввода

#include <iostream>

#include <vector>

#include <fstream>

using namespace std;

int main()

{

/*СОЗДАЕМ ФАЙЛ*/

const char FName[] = "D:/1.txt"; //Путь должен быть корректным

ofstream out(FName);

out<<"1\n";

out<<"2\n";

out<<"3\n";

out.close();

/*ИСПОЛЬЗУЯ ИТЕРАТОР ВВОДА, ЗАПИСЫВАЕМ В ВЕКТОР ДАННЫЕ ФАЙЛА*/

ifstream f(FName);

vector<char> v((istreambuf_iterator<char>(f)),

istreambuf_iterator<char>());

vector<char>::iterator it;

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

cout<<*it;

}

Могут возникнуть вопросы: &quotlчто такое istreambuf_iterator?" — это почти такой же итератор, как istream_iterator. А что такое "istream_iterator?" — это итератор входного потока, который читает (с помощью operator <<) последовательные элементы из входного потока, для которого создан.

Чтобы никто не запутался, уточню

istream_iterator — итератор для чтения элементов из входного потока (использует операцию <<).

streambuf_iterator — итератор, похожий на istream_iterator, и работает аналогично, но объекты итератора istream_iterator обращаются прямо к буферу потока и читают непосредственно следующий символ.

Это работает приблизительно так: первый вариант читает до первого пробела в потоке, а второй читает весь поток.

Невозможно записывать что-либо использованием входных итераторов!

Итераторы вывода — это противоположность итераторам ввода. Служат они для ссылки на области памяти, куда выводятся данные. Разыменовывать такие итераторы нужно только для того, чтобы присваивать некие значения объектам, на который итераторы ссылаются. Итераторы ввода могут быть возвращены итераторами потоков вывода (ostream_iterator) и итераторами вставки inserter, front_inserter и back_inserter.

Как и в первом случае, приведу два примера: для массива и для файла.

//C++		Листинг #3		Вывод на экран через итератор вывода
#include <iostream>
#include <vector> //без этого не сработает 

using namespace std; //нужное пространство имен

int main(){
  int Arr[] = {1, 2, 3, 4, 5}; //массив с данными
  copy(Arr,Arr+5,ostream_iterator<int>(cout,"\n"));   //с помощью алгоритма выводим элементы массива в поток cout
}

//C++ Листинг #3 Вывод на экран через итератор вывода

#include <iostream>

#include <vector> //без этого не сработает

using namespace std; //нужное пространство имен

int main(){

int Arr[] = {1, 2, 3, 4, 5}; //массив с данными

copy(Arr,Arr+5,ostream_iterator<int>(cout,"\n")); //с помощью алгоритма выводим элементы массива в поток cout

}

//C++		Листинг #4		Запись в файл с помощью итератора вывода
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;
int main()
{
   char FName[]="D:/1.txt";            //Имя файла FName
   char A[3]={'1','2','3'};            //Массив для инициализации вектора
   vector<char> v(A,A+3);              //Копируем массив в вектор
	
   ofstream in(FName);                 //Создаем файловый поток in
       copy(v.begin(), v.end(), ostream_iterator<char>(in)); //Копируем данные вектора в фаловый поток in
   in.close();                         //заканчиваем работу с файловым потоком in
}

//C++ Листинг #4 Запись в файл с помощью итератора вывода

#include <iostream>

#include <vector>

#include <fstream>

using namespace std;

int main()

{

char FName[]="D:/1.txt"; //Имя файла FName

char A[3]={'1','2','3'}; //Массив для инициализации вектора

vector<char> v(A,A+3); //Копируем массив в вектор

ofstream in(FName); //Создаем файловый поток in

copy(v.begin(), v.end(), ostream_iterator<char>(in)); //Копируем данные вектора в фаловый поток in

in.close(); //заканчиваем работу с файловым потоком in

}

В файл будет записана строка: "1,2,3".

Разумеется, работать можно не только с файлами, но и с любыми потоками вообще. Используем итератор вывода для вывода всех элементов вектора на экран. Похожее уже было, но мало ли кто не понял. Выводим элементы вектора в поток cout:

//C++		Листинг #5		С помощью итератора вывода выводим значения из вектора в cout
#include <iostream>
#include <vector> 

using namespace std;
int main()
{
    char A[3]={'1','2','3'};
    vector<char> v(A,A+3);	

    copy(v.begin(), v.end(), ostream_iterator<char>(cout)); //Копируем вектор в поток cout с помощью итератора вывода
    cout<<endl;
}

//C++ Листинг #5 С помощью итератора вывода выводим значения из вектора в cout

#include <iostream>

#include <vector>

using namespace std;

int main()

{

char A[3]={'1','2','3'};

vector<char> v(A,A+3);

copy(v.begin(), v.end(), ostream_iterator<char>(cout)); //Копируем вектор в поток cout с помощью итератора вывода

cout<<endl;

}

Не путайте copy с итератором, copy — это алгоритм и for_each тоже алгоритм. ostream_iterator — итератор.

Если объединить итератор ввода и итератор вывода, то получится однонаправленный итератор.

Однонаправленный итератор — это итератор, который поддерживает чтение и запись адресуемого элемента.

Как один из понятных примеров, могу привести пример поиска элемента в массиве:

//C++		Листинг #6		Однонаправленный итератор
#include <algorithm> //Будем использовать алгоритм find
#include <iostream>

using namespace std; //нужное пространство имен std
int main()
{
   int x;										 //элемент, который будем искать
   int Arr[ 6 ] = { 27, 210, 12, 47, 109, 83 };  //массив с заданными значениями

   cout << "Что ищем?: ";
   cin >> x; 									//считали с клавиатуры элемент x

   int *presult = find(Arr, Arr+6, x ); 		//используем алгоритм find для поиска элемента внутри массива

   if (presult == Arr+6){
      cout << " не найдено" << endl; 			//если указатель стал указывать на последний элемент, значит не нашлось элемента x
   }
   else{
      cout << *presult << " найдено" << endl; 	//если указатель встретил то, что мы попросили, то значит найдено
   }
}

//C++ Листинг #6 Однонаправленный итератор

#include <algorithm> //Будем использовать алгоритм find

#include <iostream>

using namespace std; //нужное пространство имен std

int main()

{

int x; //элемент, который будем искать

int Arr[ 6 ] = { 27, 210, 12, 47, 109, 83 }; //массив с заданными значениями

cout << "Что ищем?: ";

cin >> x; //считали с клавиатуры элемент x

int *presult = find(Arr, Arr+6, x ); //используем алгоритм find для поиска элемента внутри массива

if (presult == Arr+6){

cout << " не найдено" << endl; //если указатель стал указывать на последний элемент, значит не нашлось элемента x

}

else{

cout << *presult << " найдено" << endl; //если указатель встретил то, что мы попросили, то значит найдено

}

Чтобы немного конкретизировать, поясню. Сначала мы запоминаем значение в x, потом это значение даём алгоритму find как один из параметров. После этого алгоритм ищет этот полученный для поиска элемент x в обозначенном диапазоне. Если поиски были удачны, то прочитанный алгоритмом элемент выводится на экран, если же поиски неудачны, то попытки вывести элемент (presult) с очень большой вероятностью приведут к выводу мусора. Так как для одного и того же алгоритма были произведены и ввод в алгоритм и вывод элемента из алгоритма, при этом происходил последовательный перебор элементов, то, согласно определению, это можно называть однонаправленным итератором.

Еще один пример однонаправленного итератора — использование такого в алгоритме replace. Проведем небольшую перестановку в массиве:

//C++		Листинг #7		Однонаправленный итератор
#include <algorithm>
#include <iostream>

using namespace std;

int main()
{
   int Arr[]={0,0,0,1,1,1};

   replace(Arr, Arr + 6, 0, 2); // сначала поменяем все нули на нейтральное значение
   replace(Arr, Arr + 6, 1, 0); //потом поменяем все единицы на нули
   replace(Arr, Arr + 6, 2, 1); //поменяем все нейтральные значения на единицы
 
  copy(Arr, Arr + 6, ostream_iterator<int>(cout, "\n")); //выводим массив Arr на экран
}

//C++ Листинг #7 Однонаправленный итератор

#include <algorithm>

#include <iostream>

using namespace std;

int main()

{

int Arr[]={0,0,0,1,1,1};

replace(Arr, Arr + 6, 0, 2); // сначала поменяем все нули на нейтральное значение

replace(Arr, Arr + 6, 1, 0); //потом поменяем все единицы на нули

replace(Arr, Arr + 6, 2, 1); //поменяем все нейтральные значения на единицы

copy(Arr, Arr + 6, ostream_iterator<int>(cout, "\n")); //выводим массив Arr на экран

}

Алгоритм replace читает значения, изменяет их и производит внутреннее перемещение итератора от одного элемента к другому.

Есть и другие примеры, но к тем, кто не очень понял, лучшее понимание прийдет со временем, главное заниматься

Двунаправленные итераторы аналогичны однонаправленным и широко применяются в реверсивных алгоритмах.

//C++		Листинг #8		Двунаправленный итератор
#include <algorithm>
#include <iostream>

using namespace std;

int main(){
  int Arr[] = {1, 2, 3, 4, 5}; //наш массив
  reverse(Arr, Arr + 5); //реверсивный алгоритм
  copy(Arr, Arr + 5, ostream_iterator<int>(cout, "\n")); //выводим элементы массива с конца массива
}

//C++ Листинг #8 Двунаправленный итератор

#include <algorithm>

#include <iostream>

using namespace std;

int main(){

int Arr[] = {1, 2, 3, 4, 5}; //наш массив

reverse(Arr, Arr + 5); //реверсивный алгоритм

copy(Arr, Arr + 5, ostream_iterator<int>(cout, "\n")); //выводим элементы массива с конца массива

}

Итераторы контейнерных классов list, set, multiset, map и multimap являются двунаправленными.

Двунаправленные итераторы способны перемещаться в обоих направлениях благодаря инкременту (++) и декременту (— —).

Итераторы произвольного доступа имеют большие возможностей по сравнению со всеми остальными основными итераторами. Использование таких итераторов очень и очень сильно похоже на использование арифметики указателей.

//C++		Листинг	#9		Итератор произвльного доступа
#include <vector> //будем использовать вектор
#include <iostream>
using namespace std; //нужно пространство имен std

int main()
{
  int Arr[] = {1, 2, 3, 4, 5}; //массив для записи в вектор
  vector <int> v(Arr,Arr+5); //копируем массив в вектор
  vector <int>::iterator it; //объявляем итератор it

  copy(Arr,Arr+5,it=v.begin()); //используем алгоритм копирования и делаем итератор указателем на начало вектора

  cout << *( it + 4 ) << endl; //получаем произвольный элемент вектора с помощью итератора произвольного доступа 
  cout << *( it=it + 3 ) << endl; //стараемся испортить вектор, как портили указателями переменные в старые времена
  cout << *( it=it - 1) << endl; //и выводим при этом значения из вектора на экран
  cout << *( it-= 1) << endl;

  copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //проверяем вектор. Вектор выжил, гад
}

//C++ Листинг #9 Итератор произвльного доступа

#include <vector> //будем использовать вектор

#include <iostream>

using namespace std; //нужно пространство имен std

int main()

{

int Arr[] = {1, 2, 3, 4, 5}; //массив для записи в вектор

vector <int> v(Arr,Arr+5); //копируем массив в вектор

vector <int>::iterator it; //объявляем итератор it

copy(Arr,Arr+5,it=v.begin()); //используем алгоритм копирования и делаем итератор указателем на начало вектора

cout << *( it + 4 ) << endl; //получаем произвольный элемент вектора с помощью итератора произвольного доступа

cout << *( it=it + 3 ) << endl; //стараемся испортить вектор, как портили указателями переменные в старые времена

cout << *( it=it - 1) << endl; //и выводим при этом значения из вектора на экран

cout << *( it-= 1) << endl;

copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //проверяем вектор. Вектор выжил, гад

}

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

Реверсивные итераторы — это такие итераторы, которые помогают делать обходы наоборот. Надеюсь, с понятием реверсивности вы знакомы. Получить реверсивные итераторы для контейнеров можно добавлением буквы r к begin() и end(): rbegin(), rend().

//C++		Листинг #10		Прямой и реверсивный итераторы:
#include <vector> //используем вектор
#include <iostream> 
using namespace std; //нужно пространство имен std

int main(){
  int Arr[] = {1, 2, 3, 4, 5}; 						//массив для записи в вектор
  vector <int> v(Arr,Arr+5); 						//копируем массив в  вектор
  vector <int>::iterator it = v.begin(); 			//указываем итератору точку старта

  copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //прямой двунаправленный итератор
  cout<<endl;

  copy(v.rbegin(),v.rend(),ostream_iterator<int>(cout," ")); //реверсивный двунаправленный итератор
  cout << endl;
}

//C++ Листинг #10 Прямой и реверсивный итераторы:

#include <vector> //используем вектор

#include <iostream>

using namespace std; //нужно пространство имен std

int main(){

int Arr[] = {1, 2, 3, 4, 5}; //массив для записи в вектор

vector <int> v(Arr,Arr+5); //копируем массив в вектор

vector <int>::iterator it = v.begin(); //указываем итератору точку старта

copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //прямой двунаправленный итератор

cout<<endl;

copy(v.rbegin(),v.rend(),ostream_iterator<int>(cout," ")); //реверсивный двунаправленный итератор

cout << endl;

}

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

//C++		Листинг #11		Итераторы вставки (пример на list)
#include <algorithm>
#include <iostream>
#include <list>
using namespace std;
int main(){
  int Arr[]  = {0, 0}; 			//Начальный массив
  int Arr1[] = {3, 2, 1}; 		//Массив для первой вставки
  int Arr2[] = {1, 2, 3}; 		//Массив для второй вставки
  int Arr3[] = {1, 1, 1}; 		//Массив для третей вставки
  list<int> l(2); 				//список в два элемента

  copy(Arr, Arr + 2, l.begin()); //копируем в список начальный массив
  copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); //выводим список на экран
  cout << " - Список перед вставкой в голову " << endl;

  //вставка в голову
  copy(Arr1, Arr1 + 3, front_inserter(l)); 						//вставляем в голову массив первой вставки
  copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); 	//выводим массив на экран
  cout << " - Список перед вставкой в Хвост" << endl;

   //вставка в хвост
  copy(Arr2, Arr2 + 3, back_inserter(l));						//вставляем в хвост массив второй вставки
  copy(l.begin(), l.end(), ostream_iterator<int>(cout, " "));	//выводим список на экран
  cout << " - список перед вставкой в середину" << endl;

   //вставка в середину
  list<int>::iterator it = l.begin(); 							//Объявляем новый итератор и указываем на начало вектора как на точку старта
  advance(it, 4); 												//специальной операцией advance делаем приращение переменной итератора так, чтобы она указывала на четвертый объект в цепочке данных списка
  copy(Arr3, Arr3 + 3, inserter(l, it));						//вставляем в середину массив третей вставки
  copy(l.begin(), l.end(), ostream_iterator<int>(cout, " "));	//выводим список на экран
  cout << endl;
}

//C++ Листинг #11 Итераторы вставки (пример на list)

#include <algorithm>

#include <iostream>

#include <list>

using namespace std;

int main(){

int Arr[] = {0, 0}; //Начальный массив

int Arr1[] = {3, 2, 1}; //Массив для первой вставки

int Arr2[] = {1, 2, 3}; //Массив для второй вставки

int Arr3[] = {1, 1, 1}; //Массив для третей вставки

list<int> l(2); //список в два элемента

copy(Arr, Arr + 2, l.begin()); //копируем в список начальный массив

copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); //выводим список на экран

cout << " - Список перед вставкой в голову " << endl;

//вставка в голову

copy(Arr1, Arr1 + 3, front_inserter(l)); //вставляем в голову массив первой вставки

copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); //выводим массив на экран

cout << " - Список перед вставкой в Хвост" << endl;

//вставка в хвост

copy(Arr2, Arr2 + 3, back_inserter(l)); //вставляем в хвост массив второй вставки

copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); //выводим список на экран

cout << " - список перед вставкой в середину" << endl;

//вставка в середину

list<int>::iterator it = l.begin(); //Объявляем новый итератор и указываем на начало вектора как на точку старта

advance(it, 4); //специальной операцией advance делаем приращение переменной итератора так, чтобы она указывала на четвертый объект в цепочке данных списка

copy(Arr3, Arr3 + 3, inserter(l, it)); //вставляем в середину массив третей вставки

copy(l.begin(), l.end(), ostream_iterator<int>(cout, " ")); //выводим список на экран

cout << endl;

}

Надеюсь, комментарии дадут все понять, итак много как-то вышло написать.

Еще есть константный итератор. Константный итератор не допускает изменений в данных, на которые ссылается. Можно считать константный итератор указателем на константу.

//C++		Листинг #12		Константный итератор
list<int>::const_iterator it; //итератор it является константным итератором списка list

1 2	//C++ Листинг #12 Константный итератор list<int>::const_iterator it; //итератор it является константным итератором списка list

Такое вот знакомство с итераторами получилось. В принципе, не очень сложно, но и не сказать, что совсем просто. Много непонятных моментов, многое может запутать. Главное — заниматься, и все станет на свои места. Цель этого материала не досконально объяснить итераторы, а дать обобщенное понятие и себе и читателю, чтоб было легче ориентироваться в понятиях итераторов. Досконально объяснить я все равно не могу.

Добавлю в публикацию эту небольшую таблицу:

Итератор	Описание
для чтения	Читают значения с движением вперед. Могут быть инкрементированы, сравнены и разыменованы.
для записи	Пишут значения с движением вперед. Могут быть инкрементированы и разыменованы.
однонаправленные	Читают или пишут значения с движением вперед. Комбинируют функциональность предыдущих двух типов с возможностью сохранять значение итератора.
двунаправленные	Читают и пишут значения с движением вперед или назад. Похожи на однонаправленные, но их также можно инкрементировать и декрементировать.
с произвольным доступом	Читают и пишут значения с произвольным доступом. Самые мощные итераторы, сочетающие функциональность двунаправленных итераторов и возможность выполнения арифметики указателей и сравнений указателей.
обратные	Или итераторы с произвольным доступом, или двунаправленные, движущиеся в обратном направлении.

Итераторы для существующих элементов в контейнере могут стать недействительными после изменения контейнера. Это делает изменение контейнера при итерациях проблематичной. Контейнеры предлагают различные гарантии в этой связи:
vector: вставка / удаление может аннулировать все итераторы.
list/map: удаление делает недействительными только итераторы на удаленный элемент(ы), но не на другие элементы.

Рубрика: STL

Василь:

27.02.2014 в 11:49 дп

А что такое istream_iterator? – Это итератор входного потока. 
Читает (используя operator <<) последовательные элементы из входного потока, для которого он был создан
Читает используя operator >>;  не?