25 Stl. Итераторы. Алгоритмы: поиск, сортировка, суммирование.

Итератор- обобщенный указатель, который позволяет работать с различными структурами данных (контейнерами) и алгоритмами единообразным способом. Основное назначение итераторов – возможность обращаться к любому элементу контейнера при сокрытии его внутренней структуры.

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

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

В STL итератор реализуется как шаблонный класс. Для каждого типа контейнера реализуется собственный класс-итератор. Доступ к классу-итератору можно получить через контейнерный класс.

Пример:

list <int> m;

list <int>::iterator st;

deque <short> s;

deque <short>::iterator il;

Во всех классах-итераторах реализован оператор разыменования (operator *).

Оператор разыменования используется для получения значения, на которое указывает итератор.

Поскольку контейнеры STL позволяют хранить элементы произвольных типов (классы, структуры), то оператор разыменования выполняет функцию приведения указателя к производному типу данных.

Пример:

#include <stack>

#include <list>

using namespace std;

void main()

{

list<int> m;

list<int>::iterator it;

int v;

m.push_back(1);

m.push_back(5);

m.push_back(10);

for (it=m.begin(); it!=m.end(); ++it)

{

v=(*it); //1,5,10

}

Различают 5 типов итераторов:

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

Итераторы используются только для чтения значения. В классе реализовано всего 2 оператора (*, ++).

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

Итераторы используются только для записи новых значений. Операторы (*,++,=).

3)Однонаправленные итераторы.

Итераторы используются для перемещения по элементам контейнера в одном направлении. Операторы (*, ++, =, ==, !=).

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

Итераторы используются для перемещения по элементам контейнеров в двух направлениях ( от начала к концу или от конца к началу). Операторы (*, ++, -, = =, !=, --).

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

Итераторы используются для произвольного доступа к элементам контейнера. Реализуются все вышеперечисленные операторы + (<, >, >=, <=, []).

Как правило, пользователь самостоятельно не определяет тип итератора. Тип устанавливается автоматически в зависимости от контекста использования итератора.

Пример:

#include <stack>

#include <list>

#include <iostream>

#include <conio.h>

using namespace std;

class A

{

public:

A(int v, char* s)

{

val=v;

str=s;

}

A(const A &ob)

{

val=ob.val;

str=ob.str;

}

int getint()

{

return val;

}

private:

int val;

string str;

};

void main()

{

list<A> m;

list<A>::iterator it;

m.push_back(A(1,"str1"));

m.push_back(A(2,"str2"));

m.push_back(A(3,"str2"));

for(it=m.begin();it!=m.end();++it)

{

A*p=&(*it);

A ob=(*p);

cout<<ob.getint();//1,2,3

}

getch();

}

Во всех классах-контейнерах реализуются следующие функции для работы с итераторами:

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

end() – возвращает итератор, указывающий за пределы контейнера.

find() – возвращает итератор, указывающий на найденный элемент. Если такой элемент не нашелся, то возвращается итератор, который возвращается функцией-членом end().