Пассивные и активные итераторы

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

- наличие выделенного итератора классов, позволяющего одновременно проводить несколько просмотров одного и того же объекта;

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

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

Ниже приведен пример использования активного итератора.

// --------------- реализация aktiv_itr.h файла -------------

#include <iostream>

#include <vector>

#include <string>

using namespace std;

Class Node

{ string name;

public:

Node(string s): name(s) {}

Node() {}

string getName() const

{ return name;}

};

Class NodeCollection

{ vector<Node> vec;

int index;

public:

NodeCollection(): index(0) {}

void addNode(Node);

Node getNode(int) const;

int getIndex() const; //возвращает индекс последнего элемента

};

Class Iterator // интерфейс итератора

{

public:

virtual Node next() = 0;

virtual bool isDone() const = 0;

virtual ~Iterator() { }

};

Class ActiveIterator: public Iterator // реализация итератора

{ NodeCollection collection;

int currentIndex; // текущий индекс

public:

ActiveIterator(const NodeCollection&);

Node next();

bool isDone() const;

virtual ~ActiveIterator() { }

};

 

// ---------------- реализация aktiv_itr.cpp файла ---------------

#include "aktiv_itr.h"

void NodeCollection::addNode(Node n)

{ vec.push_back(n);

index++;

}

Node NodeCollection::getNode(int i) const

{ return vec[i]; }

int NodeCollection::getIndex() const

{ return index; }

ActiveIterator::ActiveIterator(const NodeCollection& c)

{ collection = c;

currentIndex = 0; // отсчет элементов начинается с нуля

}

Node ActiveIterator::next()

{ return(collection.getNode(currentIndex++)); }

bool ActiveIterator::isDone() const

{ if(collection.getIndex() > currentIndex)

return false; // продолжение итерации

else

return true; // итерация завершена

}

main()

{ NodeCollection c;

c.addNode(Node("first"));

c.addNode(Node("second"));

c.addNode(Node("third"));

Iterator* pI = new ActiveIterator(c); //инициализируем итератор

Node n;

while(!pI->isDone())

{ n = pI->next();

cout << n.getName() << endl;

}

delete pI;

return 0;

}

Результат работы программы:

first

second

third

Каждому итератору ставится в соответствие определенный объект. Переход к следующему элементу последовательности выполняется функцией next(), возвращающей 0, если итерация завершена. Функция isDone() проверяет принадлежность текущего индекса допустимому диапазону и возвращает информацию о состоянии процесса (true - если итерация завершена, иначе false).

Конструктор класса ActiveIterator сначала устанавливает связь между итератором и конкретным объектом. Затем текущий индекс устанавливается равным 0.

Класс итератора – абстрактный класс с отложенной реализацией методов next и isDone. Конкретная реализация их передана классу производному от Iterator.

Пассивный итератор, который также называют аппликатором, характеризуется тем, что он применяет определенную функцию к каждому элементу структуры. Для класса Queue пассивный итератор можно определить следующим образом:

template <class Item>

class PassiveIterator

{public:

PassiveIterator(const Queue<Item>&);

~PassiveIterator();

int apply(int (*) (const Item&));

protected:

const Queue<Item>& queue

};

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

 

Алгоритмы

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

Каждый алгоритм использует итераторы определённого типа. Например, алгоритм простого поиска (find) просматривает элементы подряд, пока нужный не будет найден. Для такой процедуры вполне достаточно итератора ввода. С другой стороны, алгоритм более быстрого двоичного поиска (binary_search) должен иметь возможность переходить к любому элементу последовательности и поэтому требует итератора с произвольным доступом. Вполне естественно, что вместо менее функционального итератора можно передать алгоритму более функциональный, но не наоборот.

Все стандартные алгоритмы описаны в заголовочном файле algorithm, в пространстве имён std.

Ниже при описании прототипов некоторых алгоритмов будем использовать следующие обозначения итераторов:

OutIt - iterator вывода;

InIt - iterator ввода;

FwdIt - однонаправленный iterator;

BidIt - двунаправленный iterator;

RanIt - iterator прямого доступа.

Алгоритмы сортировки sort, partial_sort, sort_heap

Для сортировки данных в STL имеются различные алгоритмы. Рассмотрим некоторые из них.

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

template<class RanIt>

void sort(RanIt first, RanIt last);

template<class RanIt, class Pred>

void sort(RanIt first, RanIt last, Pred pr);

Действие первого из них основано на использовании перегруженной операции opepator<() для сортировки данных по возрастанию. Второй вариант заменяет операцию сравнения функцией сравнения pr(x,y), тем самым позволяя сортировать данные в порядке, определяемом пользователем.

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

void Print(int x)

{ cout << x <<' '; }

int main()

{ vector<int> v(4);

v[0] = 3;

v[1] = 1;

v[2] = 5;

v[3] = 2;

sort(v.begin(), v.end());

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

return 0;

}

Результатом работы программы будет массив

1 2 3 5

Использованный в программе алгоритм for_each полезен тогда, когда надо произвести перебор всех элементов контейнера и выполнить некоторое действие для каждого из них.

Для использования алгоритма sort с тремя параметрами требуется в качестве третьего аргумента использовать указатель на функцию или функциональный объект. Например, для сортировки в обратном порядке требуется включить заголовок<functional>:

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

Алгоритм partil_sort предназначен для сортировки только части массива.

Алгоритм sort_heap предназначен для сортировки накопителя.

Алгоритмы поиска find, find_if, find_end, binary_search

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

#include <vector>

#include <iostream>

#include <algorithm>

#define T int

using namespace std;

bool fun(T i){return i%2==0;}

int main()

{ T m1[]={5,3,4,7,3,12};

std::vector<T> v1(m1,m1+sizeof(m1)/sizeof(T));

std::ostream_iterator<T> out(cout," ");

std::vector<T>::iterator itr;

cout<<"вектор v1: ";

std::copy(v1.begin(),v1.end(),out);

itr=std::find(v1.begin(),v1.end(),5);

cout<<"\nзначение 5 ";

if(itr!=v1.end()) cout<<"найдено в позиции "<<itr-v1.begin()<<endl;

else cout<<"не найдено\n";

itr=std::find_if(v1.begin(),v1.end(),fun);

if(itr!=v1.end()) cout<<"первый четный элемент вектора v1["<<

itr-v1.begin()<<"]= "<<*itr<<endl;

else cout<<"четные элементы в векторе v1 отсутствуют\n";

// std::sort(v1.begin(),v1.end()); // необходимо выполнить

if(std::binary_search(v1.begin(),v1.end(),3)) // сортировку вектора

cout<<"число 3 найдено в векторе v1\n"; // для binary_search

else cout<<"число 3 не найдено в векторе v1\n";

return 0;

}

В приведенной программе использован алгоритм find, выполняющий поиск в векторе v1 значения 5.

itr=std::find(v1.begin(),v1.end(),5);

Далее в программе использована функция find_if нахождения первого значения вектора v, для которого унарная предикатная функция fun возвращает true:

itr=std::find_if(v1.begin(),v1.end(),fun);

Каждый из алгоритмов find и find_if возвращает итератор ввода на найденный элемент либо (если элемент не найден) итератор, равный v.end(). Аргументы find и find_if должны быть, по крайней мере, итераторами ввода.

В строке:

if(std::binary_search(v1.begin(),v1.end(),3))

для поиска значения 3 в векторе v1 использована функция binary_search. При этом последовательность элементов вектора в анализируемом диапазоне должна быть отсортирована в возрастающем порядке. Функция возвращает значение bool. В STD имеется вторая версия алгоритма binary_search, имеющая четвертый параметр, – бинарная предикатная функция, возвращающая true, если два сравниваемых элемента упорядочены.

Алгоритмы fill, fill_n, generate и generate_n

Алгоритмы данной группы предназначены для заполнения определенным значением некоторого диапазона элементов контейнера. При этом алгоритмы generate и generate_n используют порождающую функцию. Порождающая функция не принимает никаких аргументов и возвращает значение, заносимое в элемент контейнера.

Прототип функций fill, fill_n имеет вид:

template<class FwdIt, class T>

void fill(FwdIt first, FwdIt last, const T& x);

template<class OutIt, class Size, class T>

void fill_n(OutIt first, Size n, const T& x);

Пример программы, использующей алгоритм generate, приведен ниже.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// функция нахождения чисел Фибоначчи

int Fibonacci(void)

{ static int r;

static int f1 = 0;

static int f2 = 1;

r = f1 + f2;

f1 = f2;

f2 = r;

return f1;

}

void main()

{ const int v_size = 8;

typedef vector<int > vect;

typedef vect::iterator vectIt;

vect numb(v_size); // вектор, содержащий числа

vectIt start, end, it;

start = numb.begin(); // позиция первого элемента

end = numb.end(); // позиция последнего эл-та

// заполнение [first, last +1) числами Фибоначчи

// используя функцию Fibonacci()

generate(start, end, Fibonacci);

cout << "numb { "; // вывод содержимого

for(it = start; it!= end; it++)

cout << *it << " ";

cout << " }\n" << endl;

}

Алгоритмы equal, mismatch и lexicographical_compare

Алгоритмы данной группы используются для выполнения сравнения на равенство последовательностей значений.

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main()

{ int m1[]={2,3,5,7,12};

int m2[]={2,3,55,7,12};

std::vector<int> v1(m1,m1+sizeof(m1)/sizeof(int)),

v2(m2,m2+sizeof(m2)/sizeof(int)),

v3(m1,m1+sizeof(m1)/sizeof(int));

bool res=equal(v1.begin(), v1.end(),v2.begin());

cout<<"\nВектор v1 "<<(res?"":" не ")<<" равен вектору v2";

res=equal(v1.begin(), v1.end(),v3.begin());

cout<<"\nВектор v1 "<<(res?"":" не ")<<" равен вектору v3";

std::pair<std::vector<int>::iterator,

std::vector<int>::iterator> pr;

pr=std::mismatch(v1.begin(), v1.end(),v2.begin());

cout<<"\nv1 и v2 имеют различие в позиции "

<<(pr.first-v1.begin())<<" где v1= "<<*pr.first

<<" а v2= "<<*pr.second<<'\n';

char s1[]="abbbw", s2[]="hkc";

res=std::lexicographical_compare(s1,s1+sizeof(s1)/sizeof(char),

s2,s2+sizeof(s2)/sizeof(char));

cout<<s1<<(res?" меньше ":" не меньше ")<<s2<<'\n';

return 0;

}

В строке

bool res=equal(v1.begin(), v1.end(),v2.begin());

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

Имеется также версия equal, принимающая четвертым параметром предикатную функцию, получающую два сравниваемых элемента и возвращающую значение типа bool. Это может быть полезно для последовательностей объектов или указателей на сравниваемые значения.

Алгоритм mismatch возвращает пару итераторов для двух сравниваемых последовательностей (v1 и v2), указывающих позиции, где элементы различаются:

std::pair<std::vector<int>::iterator,

std::vector<int>::iterator> pr;

pr=std::mismatch(v1.begin(), v1.end(),v2.begin());

Для определения позиции, в которой векторы различаются, требуется выполнить pr.first-v1.begin(). Согласно арифметике указателей это соответствует числу элементов от начала вектора v1 до элемента, отличного от соответствующего элемента вектора v2.

Алгоритм lexicographical_compare использует четыре итератора (по крайней мере для чтения) для сравнения, обычно строк. Если элемент первой последовательности (итерируемый первыми двумя итераторами) меньше элемента второй (два последних итератора), то функция возвращает true, иначе false.

Математические алгоритмы

Приводимая ниже программа демонстрирует использование нескольких математических алгоритмов: random_shuffle, count, count_if, min_element, max_element, accumulate и transform.

#include <iostream>

#include <algorithm>

#include <functional>

#include <vector>

using namespace std;

// возвращает целое число в диапазоне 0 - (n - 1)

int Rand(int n)

{ return rand() % n; }

 

void main()

{ const int v_size = 8;

typedef vector<int > vect;

typedef vect::iterator vectIt;

vect Numbers(v_size);

vectIt start, end, it;

// инициализация вектора

Numbers[0] = 4; Numbers[1] = 10;

Numbers[2] = 70; Numbers[3] = 4;

Numbers[4] = 10; Numbers[5] = 4;

Numbers[6] = 96; Numbers[7] = 100;

start = Numbers.begin(); // location of first

end = Numbers.end(); // one past the location

cout << "До выполнения random_shuffle:" << endl;

cout << "Numbers { ";

for(it = start; it!= end; it++)

cout << *it << " ";

cout << " }" << endl;

random_shuffle(start, end,pointer_to_unary_function<int, int>(Rand));

cout << "После выполнения random_shuffle:" << endl;

cout << "Numbers { ";

for(it = start; it!= end; it++)

cout << *it << " ";

cout << " }" << endl;

cout<<"число 4 встречается"<<count(start, end,4)<<" раз"<<endl;

}

Результат работы программы:

До выполнения random_shuffle

Numbers {4 10 70 4 10 4 96 100}

После выполнения random_shuffle

Numbers {10 4 4 70 96 100 4 10}

число 4 встречается 3 раза

Кратко охарактеризуем данные алгоритмы:

random_shuffle - имеется две версии функции для расположения в произвольном порядке чисел в диапазоне, определяемом аргументами-итераторами;

count, count_if – используются для подсчета числа элементов с заданным значением в диапазоне;

min_element, max_element – нахождение min- и max- элемента в диапазоне;

accumulate – суммирование чисел в диапазоне;

transform – применение общей функции к каждому элементу вектора.