Итераторы обеспечивают доступ к элементам в коллекции

Итераторы для конкретного класса коллекции определяются внутри класса этой коллекции. В STL существует три типа итераторов: iterator, reverse_iterator, и random access iterator. Для обхода коллекции от меньшего индекса к большему, используются обычные или forward итераторы. Для обхода коллекции в обратном направлении используются reverse итераторы. Random access iterator являются итераторами, которые могут обходить коллекцию как вперед, так и назад. Ниже приведен пример использования итераторов для удаления половины элементов вектора:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

void printInt(int number);

 

int main()

{

vector<int> myVec;

vector<int>::iterator first, last;

for (long i = 0; i<10; i++)

{

myVec.push_back(i);

}

first = myVec.begin();

last = myVec.begin() + 5;

if (last >= myVec.end())

{

return -1;

}

myVec.erase(first, last);

for_each(myVec.begin(), myVec.end(), printInt);

return 0;

}

void printInt(int number)

{

cout << number << endl;

}

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

Алгоритмы

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

STL - алгоритмы представляют набор готовых функций, которые могут быть применены к STL коллекциям и могут быть подразделены на три основных группы:

Функции для перебора всех членов коллекции и выполнения определенных действий над каждым из них:

count, count_if, find, find_if, adjacent_find, for_each, mismatch, equal, search copy, copy_backward, swap, iter_swap, swap_ranges, fill, fill_n, generate, generate_n, replace, replace_if, transform, remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy, reverse, reverse_copy, rotate, rotate_copy, random_shuffle, partition, stable_partition

Функции для сортировки членов коллекции:

Sort, stable_sort, partial_sort, partial_sort_copy, nth_element, binary_search, lower_bound, upper_bound, equal_range, merge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference, make_heap, push_heap, pop_heap, sort_heap, min, max, min_element, max_element, lexographical_compare, next_permutation, prev_permutation

Функции для выполнения определенных арифметических действий над членами коллекции:

Accumulate, inner_product, partial_sum, adjacent_difference

Ранее мы уже использовали один из алгоритмов: for_each () для того, чтобы распечатать все значения из вектора. Я думаю, не требует дополнительных объяснений то, что произошло при этом. Единственное, что бы хотелось отметить, что, кроме указателя на функцию в этом случае мы могли бы передать функтор - специальный класс с перегруженным оператором operator (). Для того, чтобы показать, как это делается, ниже приведена простая программа.

#include <iostream>

#include <strstream>

#include <string>

#include <vector>

#include <algorithm>

 

using namespace std;

 

class MyFunctor

{

string comment;

public:

MyFunctor()

{

comment = "My comment";

};

MyFunctor(string comment)

{

this - >comment = comment;

}

void operator ()(int test)

{

cout << test << comment << endl;

};

};

 

int main()

{

vector<int> test;

// fill vector:

for (int i = 0; i < 5; i++)

{

test.push_back(i);

}

// now use our functor:

MyFunctor functor(" Test comment");

for_each(test.begin(), test.end(), functor);

return 0;

}

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

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

#include <iostream>

#include <strstream>

#include <string>

#include <vector>

#include <algorithm>

 

using namespace std;

 

void printMan(string user);

int main()

{

vector<string> maleRoom;

vector<string> fimaleRoom;

maleRoom.push_back("Vasya");

maleRoom.push_back("Petya");

maleRoom.push_back("Sasha");

 

fimaleRoom.push_back("Nastya");

fimaleRoom.push_back("Alena");

fimaleRoom.push_back("Sveta");

 

for_each(maleRoom.begin(), maleRoom.end(), printMan);

reverse(maleRoom.begin(), maleRoom.end());

cout << "Males in reverse order " << endl;

for_each(maleRoom.begin(), maleRoom.end(), printMan);

maleRoom.swap(fimaleRoom);

cout << "Now in male room are fimales: " << endl;

for_each(maleRoom.begin(), maleRoom.end(), printMan);

return 0;

}

void printMan(string man)

{

cout << man << endl;

}

Предикаты

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

#include <iostream>

#include <strstream>

#include <string>

#include <vector>

#include <algorithm>

#include <functional>

 

using namespace std;

 

class Man;

ostream& operator << (ostream& os, Man& man);

 

class Man

{

string sex;

string name;

int age;

public:

Man()

{}

Man(string name, string sex, int age)

{

this ->name = name;

this ->sex = sex;

this ->age = age;

}

int GetAge()

{

return this ->age;

}

void SetAge(int age)

{

this ->age = age;

}

string GetName()

{

return this ->name;

}

void SetName(string name)

{

this ->name = name;

}

string GetSex()

{

return this ->sex;

}

void SetSex(string sex)

{

this ->sex = sex;

}

void PrintInfo()

{

cout << (*this);

}

};

 

ostream& operator << (ostream& os, Man& man)

{

os << " - - - - - Info: - - - - - " << endl;

os << "My name is: " << man.GetName() << endl;

os << "I am " << man.GetAge() << " years old " << endl;

os << "I am " << man.GetSex() << endl;

os << " - - - - - End of Info - - - - - " << endl;

return os;

};

 

class ManLess

{

public:

bool operator ()(Man& man1, Man& man2)

{

if (man1.GetAge() < man2.GetAge())

{

return false;

}

else

{

return true;

}

};

};

 

bool ManOlderThan23(Man& man)

{

if (man.GetAge() > 23)

{

return true;

}

else

{

return false;

}

};

 

class ManOlderThan

{

int m_age;

public:

ManOlderThan(int age)

{

m_age = age;

};

bool operator ()(Man& man)

{

if (man.GetAge() > m_age)

{

return true;

}

else

{

return false;

}

};

};

 

int main()

{

// create 3 men

Man man1("Dima", "male", 23);

Man man2("Sasha", "male", 30);

Man man3("Sergey", "male", 32);

vector<Man> programmers;

programmers.push_back(man1);

programmers.push_back(man2);

programmers.push_back(man3);

 

// find and print all programmers older than 23

cout << "Find all programmers older than 23 " << endl;

vector<Man>::iterator p =

find_if(programmers.begin(), programmers.end(),

ManOlderThan23);

while (p!= programmers.end())

{

cout << (*p);

p++;

}

// here is the same in more flexible way:

cout << "Find all programmers older than 23 " << endl;

p = find_if(programmers.begin(), programmers.end(), ManOlderThan(23));

for_each(p, programmers.end(), mem_fun_ref(&Man::PrintInfo));

cout << "Sorted list of programmers: " << endl;

sort(programmers.begin(), programmers.end(), ManLess());

for_each(programmers.begin(), programmers.end(), mem_fun_ref(&Man::PrintInfo));

return 0;

}

На первый взгляд, этот пример выглядит довольно запутанно, но на самом деле все очень просто. Первое, что мы делаем, это включаем упреждающее объявление класса Man, оно необходимо нам для того, чтобы, в свою очередь, использовать его в упреждающем объявлении перегруженного оператора << для нашего класса Man. Теперь мы можем использовать его внутри метода класса Man. Сам класс Man не представляет из себя ничего необычного - это обычный бизнес - класс, описывающий человека.

Далее описывается предикат - функтор LessMan, необходимый для сортировки членов нашего вектора. Он принимает два параметра типа Man. Он будет использован для сортировки в порядке убывания по возрасту программистов. ManOlderThan23 - это предикат - функция, которая отбирает всех программистов старше 23 лет. После этого мы определяем точно такой же предикат - функтор ManOlder с возможностью устанавливать минимальный возраст человека в момент его создания. Такой подход гораздо гибче предыдущего.

После входа в функцию main () мы создаем вектор programmers и заполняем его программистами: Дима, Саша и Сергей. Далее мы находим и распечатываем всех программистов старше 23 лет двумя способами, после этого сортируем и распечатываем весь список наших программистов в порядке убывания по возрасту.

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

Еще одной особенностью этого кода является то, что мы получаем указатель на функцию класса с помощью mem_fun_ref. Как видим, иногда это бывает очень полезно. Для того, чтобы воспользоваться этой возможностью, необходимо включить #include <functional>.

Заключение

Достоинство STL - это то, что библиотека действительно является кроссплатформенной. И это не пустая декларация, как происходит со многими другими технологиями. Я думаю, что существует больше платформ, не поддерживающих Java, чем компиляторов C++ для этих же платформ, не поддерживающих STL. Конечно, не существует абсолютной гарантии, что она встроена абсолютно во все компиляторы C++. Например, некоторые компиляторы для мобильных устройств и микроконтроллеров не включают эту библиотеку. Это обусловлено тем, что она является относительно неэффективной в плане использования памяти, поскольку оптимизирована для обеспечения максимальной скорости. В мобильных устройствах, как известно, самый дорогой ресурс - это память, в то время как на вашем PC сегодня его в избытке. Поэтому иногда вам придется писать шаблонные классы, похожие на классы STL, самостоятельно для того, чтобы например перенести приложение, работающее под Windows или Linux на мобильное устройство.