Библиотека стандартных шаблонов, для чего предназначена, что включает.
Стандартные шаблоны классов являются мощным инструментом создания программного обеспечения в различных прикладных областях. Библиотекf шаблонов классов входит в стандарт языка. Многие алгоритмы, разработанные в данной библиотеке, прекрасно работают с обычными массивами.
STL состоит из следующих частей: контейнер, алгоритм и итератор.
Контейнер – это способ организации хранения данных, например стек, связный список, очередь. Массив языка С++ в какой-то степени относится к контейнерам. Контейнеры представлены в библиотеке как шаблонные классы, что позволяет быстро менять тип хранимых в них данных.
Алгоритм – это процедуры, применяемые к контейнерам для обработки хранящихся данных. Они представлены как шаблоны функций. Однако эти функции не принадлежат какому-либо классу-контейнеру, они не являются дружественными функциями. Наоборот, это совершенно независимые функции. Это обеспечивает универсальность алгоритмов и позволяет использовать алгоритмы не только к контейнерам, но и к другим типам данных.
Итераторы – обобщенная концепция указателей, они ссылаются на элементы контейнеров. Итераторы – ключевая часть STL, поскольку они связывают алгоритмы с контейнерами. Иногда итераторы называют интерфейсом библиотеки шаблонов.
Контейнеры
Контейнеры представляют собой хранилища данных. При этом не имеет значения, какого типа данные в них хранятся. Это могут быть базовые типы int, float, double, etc, а также типы, объявленные пользователем. Контейнеры STL делятся на две основные категории: последовательные контейнеры и ассоциативные. К последовательным контейнерам относятся векторы, списки и очереди с двусторонним доступом; к ассоциативным контейнерам – множества, мультимножества, отображения и мультиотображения. Кроме того, наследниками последовательных контейнеров выступают стек, очередь и приоритетная очередь.
Методы
Для выполнения простых операций над контейнерами используют методы. Методы проще алгоритмов, применять их можно к большей части классов контейнеров. Некоторые методы перечислены ниже:
size() – возвращает число элементов контейнера;
empty() – возвращает true, если контейнер пуст;
max_size() – возвращает максимально допустимый размер контейнера;
begin() – возвращает итератор на начало контейнера;
end() – возвращает итератор на последнюю позицию в контейнере;
rbegin() – возвращает реверсивный итератор на конец контейнера;
rend() – возвращает реверсивный итератор на начало.
Алгоритмы
Алгоритм – это функция, которая производит некоторое действие над элементами контейнера. В стандарте языка С++ алгоритм – независимая шаблонная функция, применимая даже к обычным массивам. Рассмотрим отдельные методы на примерах.
Алгоритм find(). Этот алгоритм ищет первый элемент в контейнере, значение которого равно указанному. Общий формат метода следующий: find(beg, end, val), где beg – итератор (указатель) первого значения, которое нужно проверить; end – итератор последней позиции; val – искомое значение.
#include<iostream>
#include<algorithm>
using namespace std;
int arr[] = {11, 22, 33, 44, 55, 66, 77, 88, 99, 0};
int main()
{
setlocale(0,"RUS");
int *ptr;
ptr = find(arr, arr+10, 55);
cout << " Первый объект со значением 55 найден в позиции: " << (ptr-arr) << endl;
system("pause");
return 0;
}
Для использования алгоритмов необходимо подключить файл algorithm. В рассмотренном примере в качестве контейнера выступает обычный массив, в котором ищется число 55. Начало поиска – элемент с нулевым индексом, окончание – указатель на единицу больший, чем указатель на последний элемент. Подобный подход носит название «значение после последнего». Результатом работы программы будет число 4. Если в контейнере нет искомого значения, программа выдаст указатель на следующий элемент после последнего. Для рассмотренного примера это будет число 10.
Следующий фрагмент демонстрирует пример использования метода find для контейнера типа vector.
vector<int> v;
for(int i = 1; i <= 100; i++)
{
v.push_back(i*i);
}
if(find(v.begin(), v.end(), 49) != v.end())
{
cout <<" Число 49 найдено в списке квадратов натуральных чисел, не превосходящих 100 " << endl;
}
else
{
cout <<" число 49 не найдено "
}
Диапазон поиска определяется с помощью методов begin и end.
Задание 5. Продемонстрировать работу алгоритма find() для следующих последовательных контейнеров: список (list), очередь с двусторонним доступом (deque) и стек (stack). В программе необходимо подключить соответствующие заголовочные файлы.
Алгоритм count(). Этот алгоритм подсчитывает, сколько элементов в контейнере имеют данное значение. Его формат подобен формату алгоритма find. Рассмотрим фрагмент программного кода, использующего алгоритм count().
int arr[] = {11, 22, 33, 22, 55, 22, 77, 22, 99, 0};
int main()
{
setlocale(0,"RUS");
int n = count(arr, arr+10, 22);
cout << " Число 22 встречается " << n << " раз(а) " << endl;
system("pause");
return 0;
}
Результатом алгоритма count() будет число вхождений искомого элемента или число 0, если искомый элемент не входит в данный контейнер.
Задание 6. Продемонстрировать работу алгоритма count() для последовательных контейнеров: список (list), очередь с двусторонним доступом (deque) и стек (stack).
Алгоритм search(). Алгоритм search() оперирует одновременно с двумя контейнерами. Он отыскивает некоторую последовательность, входящую в один контейнер в другом контейнере. Формат алгоритма следующий: search(beg, end, sbeg, send), где beg – начало первого контейнера, end – конец первого контейнера, sbeg – начало второго контейнера, send – конец второго контейнера. Результатом работы алгоритма будет позиция, начиная с которой обнаружено совпадение. Если совпадения не обнаружено, необходимо обеспечить вывод соответствующего сообщения. Следующий фрагмент показывает пример работы алгоритма.
int arr1[] = {11, 24, 33, 11, 22, 33, 22, 66, 77, 8};
int arr2[] = {11, 22, 33};
int main()
{
setlocale(0,"RUS");
int *ptr;
ptr = search(arr1, arr1+10, arr2, arr2+3);
if(ptr == arr1+10) cout << " Совпадений нет ";
else cout << " Совпадения в позиции " << (ptr-arr1) << endl;
system("pause");
return 0;
}
Несложно заметить, что результатом данного примера будет число 3, так как совпадение двух массивов начинается с элемента со значением 11 первого массива, имеющего индекс 3.
Важно заметить, что параметрами алгоритма search() не обязательно должны быть контейнеры одного и того же типа. Второй параметр в этом случае играет роль маски. В этом состоит универсальность библиотеки STL.
Задание 7. Объявить классы Person и Student, имеющие поля Name, Age, идентифицирующие имя и возраст человека и студента. В каждом из классов предусмотреть поля, характерные для его типов, например для класса Student таким полем может быть Ball, а для класса Person – поле Prof, идентифицирующее профессию человека. Объявить два контейнера типа vector, в одном из которых находятся объекты типа Person, а во втором – объекты типа Student. Используя алгоритм search(), определить последовательность значений, заданных контейнером Student, попадающих в контейнер Person. Сравнение проводить по значениям полей Name. Показать пример работы алгоритма count() на заданных контейнерах, в качестве критерия поиска можно использовать поля Ball типа Student, подсчитывающего число студентов, сдавших последнюю сессию на 4 и на 5. Для класса Person критерием выбора может быть величина оклада.
Алгоритм sort(). Этот алгоритм сортирует элементы контейнера в порядке их увеличения. Следующий пример показывает возможность использования алгоритма сортировки для целочисленных контейнеров, например, для последовательности символов.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef unsigned int UINT;
vector<char> arr_char;
int main()
{
arr_char.push_back('T');
arr_char.push_back('E');
arr_char.push_back('G');
arr_char.push_back('L');
arr_char.push_back('A');
arr_char.push_back('Z');
arr_char.push_back('K');
arr_char.push_back('W');
sort(arr_char.begin(), arr_char.end());
for(UINT j=0; j < arr_char.size(); j++)
cout<< arr_char[j] << ' ';
cout<< endl;
setlocale(0,"RUS");
system("pause");
return 0;
}
Алгоритм sort() имеет два параметра, идентифицирующие начало и конец сортируемого контейнера. В данном примере начало, и конец последовательности получаются как результат работы соответствующих методов.
Алгоритм merge(). Этот алгоритм работает с тремя контейнерами, объединяя два из них в третий. Рассмотрим пример использования этого алгоритма.
#include<iostream>
#include<algorithm>
usingnamespacestd;
int arr1[] = {2, 3, 4, 6, 8};
int arr2[] = {1, 3, 5};
int dest[8];
int main()
{
setlocale(0,"RUS");
merge(arr1, arr1+5, arr2, arr2+3, dest);
for(int i=0; i<8; i++)
cout<< dest[i] << ' ';
cout<< endl;
system("pause");
return 0;
}
Задание 8. Используя алгоритм merge() объединить два вектора и списка в результирующие контейнеры.
Функциональные объекты
Многие алгоритмы для своей работы требуют функциональные объекты. Функциональным объектом считается объект шаблонного класса, в котором есть единственный метод – перегруженная операция вызова функции – (). Рассмотрим пример использования алгоритма sort с функциональным объектом, позволяющим отсортировать последовательность в порядке убывания.
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
double ddata[] = {38.44, 64.22, -9.345, 0.453, 8.01, 23};
int main()
{
setlocale(0,"RUS");
sort(ddata, ddata+6, greater<double>() );
for(int j=0; j<6; j++)
cout<< ddata[j] << ' ';
cout<< endl;
system("pause");
return 0;
}
Функциональным объектом здесь является метод greater<double>(), который сортирует последовательность по убыванию. Обычно алгоритм sort() сортирует по возрастанию.
Функциональные объекты могут успешно работать только со стандартными типами данных С++ или с классами, в которых определены (перегружены) операторы <, <=, >, >= , ==, etc. Проблему можно обойти, определив собственную функцию для функционального объекта. Следующий пример показывает это.
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
char *Names[] = { "Петя", "Маша", "Дима", "Вова", "Вася", "Филимон"};
bool alpha(char *n1, char *n2)
{
return(strcmp(n1,n2)<0) ? true : false;
}
int main()
{
setlocale(0,"RUS");
sort(Names, Names+6, &alpha);
for(int i=0; i<6; i++)
cout<< Names[i] << ' ';
cout<< endl;
system("pause");
return 0;
}
Здесь вместо функционального объекта выступает функция boolalpha(), которая сравнивает две строки, используя стандартную функцию strcmp(). Наличие оператора взятия адреса перед именем функции alpha() не обязательно. Это скорее дань традициям языка С.
Задание 9. Используя собственные функции как функциональные объекты, показать пример их применения к спискам, очередям с двусторонним доступом.
Задание 10. Самостоятельно изучить последовательные контейнеры: векторы, списки и очереди с двусторонним доступом, а также алгоритмы и методы для работы с ними. Показать примеры их использования.
Итераторы
Для обращения к элементам обычного массива используют операцию индексирования [] или обращение через указатель. Использовать указатели к более сложным контейнерам затруднительно. Во-первых, элементы контейнера могут храниться в памяти не последовательно, а сегментировано. Методы доступа к ним существенно усложняются. Нельзя просто инкрементировать указатель для получения следующего значения. Во-вторых, при добавлении или удаления элементов из середины контейнера, указатель может получить некорректное значение.
Одним из решений проблемы является создание класса «умных» указателей – итераторов. Объект такого класса является оболочкой для методов, оперирующих с обычными указателями. Для них перегружены операции ++ и *, адекватно работающих даже в том случае, когда элементы сегментированы в памяти.
Итераторы играют важную роль в STL. Они определяют какие алгоритмы использовать к каким контейнерам. По категориям различают следующие виды итераторов: входные, выходные, прямые, двунаправленные и случайного доступа.
Работа с итераторами
(Доступ к данным. Вставка данных)
В контейнерах с итераторами произвольного доступа (векторах, очередях с двусторонним доступом) итерация осуществляется с помощью оператора []. Однако к спискам эту операцию применить нельзя. Рассмотрим пример работы со списками через итераторы.
#include<iostream>
#include<algorithm>
#include<list>
using namespace std;
int main()
{
// доступ к данным
double arr[] = {2.33, 44.32, -6.54, .8};
list<double> doubleList;
for(int i=0; i<4; i++)
doubleList.push_back(arr[i]);
list<double> ::iterator iter = doubleList.begin();
for(iter=doubleList.begin(); iter!=doubleList.end(); iter++)
cout<< *it++ << ' ';
cout<< endl;
// вставкаданных
list<int> intList(5);
list<int> ::iterator it;
int data = 0;
for(it=intList.begin(); it!=intList.end(); it++)
*it = data += 2;
it = intList.begin();
while(it !=intList.end())
cout<< *it++ << ' ';
cout<< endl;
system("pause");
return 0;
}
Объявление итераторов в данной программе:
– оператор list<double> ::iteratoriter = doubleList.begin(); – определяет двунаправленный итератор для работы со списком, содержащим вещественные числа, и инициализирует его указателем на начало списка;
– оператор list<int> ::iteratorit; – определяет двунаправленный итератор для списка с целочисленными элементами.
Итераторы для вектора или очереди автоматически делаются с произвольным доступом. Имена итераторов – обычные идентификаторы, подчиняющиеся законам языка. Еще одно важное замечание: обращение к итераторам, например, *it = data += 2; или cout<< *it++ << ' '; осуществляется как к обычным указателям.
Задание 11. Определить вектор, очередь, содержащие элементы стандартного типа (целого, вещественного и т. д.), определить для них итераторы и опробовать алгоритмы и методы работы с ними. Определить класс, состоящий из небольшого числа компонент, сохранить объекты этого класса в очереди. Показать пример использования итераторов при работе с очередью объектов собственного типа.