+ Л Е К Ц І Я 6
1. ШАБЛОНЫ
Шаблоны позволяют определять функции,
которые могут работать с разными типами данных. Шаблоны определяются следующим
образом:
template <class идентификатор> определение функции;
template <typename идентификатор> определение
функции;
Оба определения идентичны. Можно
использовать как ключевое слово class, так и typename.
Например, в С можно создать перегруженную
функцию вычисления модуля abs:
int abs(int n)
{
return n < 0 ? -n : n;
}
double abs(double n)
{
return n < 0 ? -n : n;
}
Используя шаблон, можно создать
единственное определение, которое будет автоматически обрабатывать любой тип
данных:
#include <stdio.h>
template <class T> T abs(T n)
{
return n < 0 ? -n : n;
}
void main (void)
{
double d = abs(-4.55);
int i = abs(-7);
printf("%lf %d\n",d,i);
}
Следующий шаблон
вычисляет максимум двух чисел:
template <class Type> Type max (Type a, Type b)
{
return (a > b ? a : b);
}
Переменная Type может принимать любой тип.
При вызове функции можно указывать явно тип, с которым она будет работать:
имя функции <тип> (параметры)
Функцию max можно вызвать следующим
образом:
int i = max<int>(7,76);
Разнотиповые аргументы передавать функции
max запрещается. Можно определить шаблон функции , которая может принимать
разнотиповые приводимые аргументы:
template <class Type1, class Type2> Type1 max (Type1 a, Type2 b)
{
return (a > b ? a : b);
}
Тогда функцию max можно вызвать одним из
следующих способов:
int i = max(7,76);
int i = max<int,long>(7,76);
2. ИМЕНОВАННЫЕ ОБЛАСТИ namespace
Именованные области (namespace) позволяют
объединять глобальные классы, объекты, функции под одним именем. Другими
словами они позволяют разбивать глобальное пространство на области, в каждой из
которых действуют свои объекты.
Определяются именованные области следующим
образом:
namespace <идентификатор>
{
<тело именованной области>
}
Тело именованной области может содержать
множество классов, объектов и функций. Например:
namespace ivan
{
int a,b;
}
Для доступа к элементам именованной
области извне используется оператор расширения видимости :: . Например, для
доступа к переменной a следует написать: ivan::a.
Следующая программа создает две именованные области, каждая из которых содержит
переменную. Переменные и функции из разных именованных областей могут иметь
одинаковые имена.
#include <iostream.h>
namespace first
{
int var = 5;
}
namespace second
{
double var = 3.1416;
}
void main (void)
{
cout << first::var << endl;
cout << second::var << endl;
}
using namespace
Директива using позволяет ассоциировать
текущее глобальное пространство объектов с именованной областью. После
выполнения команды
using namespace <идентификатор>
можно напрямую иметь доступ ко всем
объектам и функциям именованной области.
#include <iostream.h>
namespace first
{
int var = 5;
}
namespace second
{
double var = 3.1416;
}
void main (void)
{
{
using namespace first;
cout << var << endl;
}
{
using namespace second;
cout << var << endl;
}
}
В случае объявления двух именованных
областей в одном блоке могут возникнуть проблемы из-за идентичности имен.
3. СТАНДАРТНАЯ
БИБЛИОТЕКА ШАБЛОНОВ STL
Стандартная библиотека шаблонов STL (standard
template library) – это набор шаблонов функций и классов в языке С++,
включающий в себя различные контейнеры данных (список, очередь, множество,
отображение, хэш таблица, очередь с приоритетами) и базовые алгоритмы
(сортировка, поиск).
Стандартная библиотека шаблонов является
именованной областью с именем std. При ее использовании включаемые
файлы пишутся без расширения .h, а к некоторым еще добавляется приставка c.
Например, аналогом библиотек <stdio.h>, <limits.h> в STL будут
<cstdio>, <climits>.
Для подключения стандартной библиотеки
шаблонов следует воспользоваться директивой:
using namespace std;
|
#include <iostream>
void main
(void)
{
std::cout << "Hello, world!\n";
}
|
#include <iostream>
using namespace std;
void main
(void)
{
cout
<< "Hello, world!\n";
}
|
Библиотека STL содержит пять основных
видов компонентов:
1. алгоритм (algorithm): определяет вычислительную
процедуру.
2. контейнер (container): управляет набором объектов в
памяти.
3. итератор (iterator): обеспечивает для алгоритма
средство доступа к содержимому контейнера.
4. функциональный объект (function object): инкапсулирует
функцию в объекте для использования другими компонентами.
5. адаптер (adaptor): адаптирует компонент для
обеспечения различного интерфейса.
Контейнерами называются часто
встречающиеся способы организации данных: динамические массивы, списки,
очереди, стеки.
Алгоритмы не
являются частью контейнеров, а образуют отдельную подсистему. Но при этом почти
любой алгоритм может применяться к почти любому контейнеру. Вызывая метод для
некоторого алгоритма, мы вызываем этот метод сам по себе, а не для экземпляра
некоторого класса. Контейнер же, к которому применяется алгоритм, передается в
качестве параметра.
Итератор - это
указатель, который может двигаться по элементам контейнера. Итераторы играют
такую же роль, как индекс у элемента массива. Через индекс массива мы можем
получить некоторый элемент массива, и через итератор мы можем получить
некоторый элемент контейнера.
4. ВЕКТОРЫ
Вектором называется
последовательность объектов с прямым доступом. Поддерживает константное время
вставки-удаления элемента из конца последовательности и линейное
время вставки-удаления из середины или начала. Количество элементов вектора
изменяется динамически, управление памятью совершается автоматически. Для использования
векторов следует включить библиотеку:
#include <vector>
Для создания экземпляра вектора можно
воспользоваться одним из следующих конструкторов:
|
Конструктор
|
описание конструктора
|
|
vector()
|
Создание пустого вектора
|
|
vector(size_type n)
|
создание вектора из n элементов
|
|
vector(size_type n, const T& t)
|
создание вектора из n копий t
|
|
vector(const vector&)
|
Копирующий конструктор
|
Пример 4.1. Рассмотрим работу
конструкторов векторов на примерах.
Создание пустого вектора v (массива
нулевой длины, не содержащего ни одного элемента):
vector<int> v;
Создание вектора v длины 10:
vector<int> v(10);
Создание вектора v длины 10, все элементы
которого равны 5:
vector<int> v(10,5);
Пусть имеется массив чисел m. Для того
чтобы создать вектор v, содержащий эти же числа, следует
воспользоваться копирующим конструктором:
int m[] = {1,2,3,4,5};
vector<int> v(m,m+5);
Для создания еще одного вектора u с
элементами 3, 4, 5 можно воспользоваться конструктором копированием интервала:
vector<int> u(&v[2],&v[5]);
Через reference будем обозначать тип
“ссылка”. Следующие методы созданы для работы с вектором:
|
метод
|
описание метода
|
|
void clear()
|
удаление всех элементов.
Вектор становится пустым
|
|
size_type size() const
|
вычисляет размер вектора
|
|
bool empty() const
|
возвращает истину, если вектор пустой
|
|
reference operator[](size_type n)
|
оператор индексирования, возвращает
n–ый элемент вектора
|
|
reference front()
|
возвращает первый элемент вектора
|
|
reference back()
|
возвращает последний элемент вектора
|
Пример 4.2. Пусть имеется массив
чисел m. Создадим вектор v, скопировав в него данные массива m.
int m[] = {1,2,3,4,5};
vector<int> v(m,m+5);
Выведем размер вектора:
printf("Size: %d\n",v.size());
Выведем первый и последний элементы
вектора:
printf("First: %d, Last: %d\n",v.front(),v.back());
Выведем все элементы вектора, используя
оператор индексирования:
for(int i=0;i<v.size();i++) printf("%d ",v[i]); printf("\n");
Следующая таблица описывает методы вставки
и удаления элементов вектора:
|
метод
|
описание метода
|
|
void push_back(const T& x)
|
вставка элемента x в конец вектора
|
|
void pop_back()
|
удаление последнего элемента
|
Итератором называется
указатель на объект. Создается итератор следующим образом:
имя_шаблона<тип>::iterator
имя_итератора
Класс vector имеет следующие встроенные итераторы:
|
итератор
|
описание итератора
|
|
const_iterator begin() const
|
указатель на начало вектора
|
|
const_iterator end() const
|
указатель на конец вектора
|
Пример 4.3. Занесем в вектор v
числа 4, 10, 1. Выведем элементы вектора v при помощи итератора iter.
vector<int> v;
vector<int>::iterator iter;
v.push_back(4); v.push_back(10); v.push_back(1);
for(iter=v.begin();iter!=v.end();iter++)
printf("%d ",*iter); printf("\n");
Для вставки и удаления элементов внутри
вектора используются методы, аргументами которых выступают итераторы:
|
метод
|
описание метода
|
|
iterator insert(iterator pos,
const
T& x)
|
вставка элемента x в позицию pos
|
|
iterator erase(iterator pos)
|
удаление элемента, на который указывает
итератор pos
|
|
iterator erase(iterator first,
iterator
last)
|
удаление всех элементов, расположенных в промежутке
[first..last]
|
Пример 4.4. Занесем в вектор v
квадраты натуральных чисел от 1 до 10. Удалим из вектора значения 16, 25, 36, 49.
vector<int> v;
for(i=1;i<=10;i++) v.push_back(i*i);
for(i=0;i<v.size();i++) printf("%d ",v[i]); printf("\n");
v.erase(v.begin()+3,v.end()-3);
for(i=0;i<v.size();i++) printf("%d ",v[i]); printf("\n");
Упражнение 4.1. Имеется лужа некоторой формы, имеющей
определенную глубину. Известно, что поперечный разрез лужи одинаков на всех
глубинах. Массив rates содержит скорость наполнения лужи в определенные
интервалы времени, durations[i] содержит время, в течении которого
лужа наполнялась со скоростью rates[i].
За все интервалы времени, указанные в durations, лужа наполнилась до высоты height. Необходимо определить площадь
поперечного разреза лужи.
Класс: SwimmingPool
Метод: int area(vector<int> rates,
vector<int> durations,
int height)
Ограничения: массивы
rates и durations содержат одинаковое количество чисел, 1 £
rates[i],durations[i],height £ 100.
Вход. Массивы rates и durations,
содержащие скорость и время наполнения лужи. Целое число height содержит глубину лужи.
Выход. Площадь поперечного разреза лужи.
Пример входа
|
rates
|
durations
|
height
|
|
{1,2,3,4,5}
|
{5,4,3,2,1}
|
10
|
|
{5,4,3,2,1}
|
{1,2,3,4,5}
|
100
|
|
{100}
|
{1}
|
100
|
Пример выхода
3
0
1
Вычисляем объем воды, которой наполнилась
лужа. Разделив полученный объем на высоту, получим площадь поперечного разреза
лужи.
#include <cstdio>
#include <vector>
using namespace std;
class SwimmingPool
{
public:
int area(vector<int> rates, vector<int> durations, int height)
{
int i,vol=0;
for(i=0;i<rates.size();i++)
vol += rates[i]*durations[i];
return vol / height;
}
};
Упражнение 4.2. В футболе за победу команда получает 3
очка, за ничью 1 очко, за проигрыш – 0. Массивы wins и ties содержат информацию
об играх, проведенных футбольными командами в лиге: wins[i] равно числу выигранных матчей i - ой командой, ties[i]
равно числу матчей, сведенных i - ой
командой вничью. Необходимо найти команду с наибольшим количеством очков.
Класс: Soccer
Метод: int maxPoints(vector<int>
wins, vector<int> ties)
Ограничения: массивы
wins и ties содержат одинаковое
количество чисел, 0 £ wins[i],ties[i] £ 100.
Вход. Массивы wins и ties, содержащие
информацию о командах.
Выход. Наибольшее количество очков, заработанное одной командой в лиге.
Пример входа
|
wins
|
ties
|
|
{1,4,3,0,0}
|
{3,1,5,3,1}
|
|
{12,45,20,17,48,0}
|
{48,10,53,94,0,100}
|
|
{35,0}
|
{0,76}
|
Пример выхода
14
145
105
Для каждой команды вычисляем полученное
количество очков в лиге. Среди набранного количества очков каждой командой
находим наибольшее значение.
#include <cstdio>
#include <vector>
using namespace std;
class Soccer
{
public:
int maxPoints(vector<int> wins, vector<int> ties)
{
int max = 0;
for(int i=0;i<wins.size();i++)
if (wins[i]*3+ties[i] > max) max = wins[i]*3+ties[i];
return max;
}
};
