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().

 

Алгоритмы

 

Алгоритмы – наборы готовых функций, которые могут быть применены к контейнерам.

Условно можно поделить на 3 группы:

1)Алгоритмы для перебора элементов контейнера и выполнения определенных действий над каждым из элементов.

count – подсчет элементов;

find – поиск;

for_each – применение заданной функции к заданному диапазону элементов;

equal – сравнение двух элементов на равенство;

swap – меняет местами заданные два значения;

fill – заполняет диапазон заданными значениями;

remove – удаление элементов из заданного диапазона.

2)Алгоритмы для сортировки элементов контейнера.

sort – сортировка заданного диапазона;

binary_search - просматривает элементы от start до end в поисках значения val. Просматриваемые элементы между start и end должны быть упорядочены по возрастанию, что определено оператором <. (start, end – итераторы).

merge – объединение двух упорядоченных последовательностей, помещая результат в третью последовательность.

3)Алгоритмы для выполнения определенных арифметических действий над элементами контейнера.

accumulate – нахождение суммы элементов контейнера или подконтейнера;

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

partial_sum – вычисляет частичную сумму элементов, расположенных в диапазоне [start,end) и располагает результат в result. (start, end, result – итераторы).

Пример:

#include <algorithm>

#include <numeric>

 

void main()

{

list<int> m;

list<int>::iterator it;

m.push_back(3);

m.push_back(2);

it = find (m.begin(), m.end(), 2); // получаем указатель на элемент с значением 2.

}

 

Реализация сортировки.

Не все контейнеры поддерживают sort. Например, list не поддерживает, а vector поддерживает.

Пример:

#include <algorithm>

#include <numeric>

#include <vector>

using namespace std;

void main()

{

vector<int> m;

m.push_back(2);

m.push_back(1);

m.push_back(5);

sort(m.begin(), m.end(), greater<int>());

// сортировка по возрастанию (greater)

// сортировка по убыванию (less)

}

 

Функция суммирования accumulate – сумма всех элементов контейнера.

int v = accumulate(m.begin(), m.end(), 2);

//значение 2 будет прибавлено к полученной сумме.