Шаблоны: определение и использование. Именованные области

Вид материалаДокументы

Содержание


2. Именованные области
3. Стандартная библиотека шаблонов stl
Вход. Массивы rates и durations, содержащие скорость и время наполнения лужи. Целое число height содержит глубину лужи.Выход.
Пример входа
Вход. Массивы wins и ties, содержащие информацию о командах. Выход.
Вход. Массив dice, описывающий положение игральных кубиков после броска. Выход.
Вход. Массив чисел toss.Выход.
Пример выхода
Пример входа
Вход. Целые числа objWidth и objLength – размеры объекта, массивы boxWidth и boxLength, содержащие размеры коробок.Выход.
Пример входа
Пример выхода
Вход. Массив чисел a и величина искомой разности n.Выход.
Указания к решению упражнений
Упражнение 4.2. [Топкодер, SRM 194, Soccer].
Упражнение 4.3. [Топкодер, SRM 315, RosePetals].
Упражнение 4.5. [Топкодер, SRM 217, FuelConsumption].
Упражнение 4.7. [Топкодер, SRM 322, DerivativeSequence].
Подобный материал:
ЗАНЯТИЕ 6


1. Шаблоны: определение и использование.

2. Именованные области. Оператор расширения видимости. Директива using.

3. Стандартная библиотека шаблонов (STL). Алгоритмы. Контейнеры. Итераторы.

4. Векторы. Конструкторы. Вставка-удаление элементов. Использование итераторов для доступа к элементам.

5. Задачи.

ссылка скрыта: SRM 193 (SwimmingPool), SRM 194 (Soccer), SRM 212 (YahtzeeScore), SRM 217 (FuelConsumption), SRM 253 (ObjectPacking), SRM 315 (RosePetals), SRM 322 (DerivativeSequence).


1. ШАБЛОНЫ


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


template определение функции;

template определение функции;


Оба определения идентичны. Можно использовать как ключевое слово class, так и typename.


Например, в С можно создать перегруженную функцию вычисления модуля abs:


int abs(int n)

{

return n < 0 ? -n : n;

}

double abs(double n)

{

return n < 0 ? -n : n;

}


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


#include

template 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 Type max (Type a, Type b)

{

return (a > b ? a : b);

}


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


имя функции <тип> (параметры)


Функцию max можно вызвать следующим образом:


int i = max(7,76);


Разнотиповые аргументы передавать функции max запрещается. Можно определить шаблон функции , которая может принимать разнотиповые приводимые аргументы:


template Type1 max (Type1 a, Type2 b)

{

return (a > b ? a : b);

}


Тогда функцию max можно вызвать одним из следующих способов:


int i = max(7,76);

int i = max(7,76);


2. ИМЕНОВАННЫЕ ОБЛАСТИ


namespace

Именованные области (namespace) позволяют объединять глобальные классы, объекты, функции под одним именем. Другими словами они позволяют разбивать глобальное пространство на области, в каждой из которых действуют свои объекты.

Определяются именованные области следующим образом:


namespace <идентификатор>

{

<тело именованной области>

}


Тело именованной области может содержать множество классов, объектов и функций. Например:


namespace ivan

{

int a,b;

}


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


#include

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

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. Например, аналогом библиотек , в STL будут , .

Для подключения стандартной библиотеки шаблонов следует воспользоваться директивой:

using namespace std;



#include

void main (void)

{

std::cout << "Hello, world!\n";

}


#include

using namespace std;

void main (void)

{

cout << "Hello, world!\n";

}

#include

void main (void)

{

std::printf("Hello, world!\n");

}

#include

using namespace std;

void main (void)

{

printf("Hello, world!\n");

}


Библиотека STL содержит пять основных видов компонентов:
  1. алгоритм (algorithm): определяет вычислительную процедуру.
  2. контейнер (container): управляет набором объектов в памяти.
  3. итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера.
  4. функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами.
  5. адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.


Контейнерами называются часто встречающиеся способы организации данных: динамические массивы, списки, очереди, стеки.


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


Итератор - это указатель, который может двигаться по элементам контейнера. Итераторы играют такую же роль, как индекс у элемента массива. Через индекс массива мы можем получить некоторый элемент массива, и через итератор мы можем получить некоторый элемент контейнера.


4. ВЕКТОРЫ


Вектором называется последовательность объектов с прямым доступом. Поддерживает константное время вставки-удаления элемента из конца последовательности и линейное время вставки-удаления из середины или начала. Количество элементов вектора изменяется динамически, управление памятью совершается автоматически. Для использования векторов следует включить библиотеку:

#include


Для создания экземпляра вектора можно воспользоваться одним из следующих конструкторов:


Конструктор

описание конструктора

vector()

Создание пустого вектора

vector(size_type n)

создание вектора из n элементов

vector(size_type n, const T& t)

создание вектора из n копий t

vector(const vector&)

Копирующий конструктор


Пример 4.1. Рассмотрим работу конструкторов векторов на примерах.

Создание пустого вектора v (массива нулевой длины, не содержащего ни одного элемента):

vector v;

Создание вектора v длины 10:

vector v(10);

Создание вектора v длины 10, все элементы которого равны 5:

vector v(10,5);

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

int m[] = {1,2,3,4,5};

vector v(m,m+5);

Для создания еще одного вектора u с элементами 3, 4, 5 можно воспользоваться конструктором копированием интервала:

vector u(&v[2],&v[5]);

или

vector 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 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");


Пример 4.3. Рассмотрим программу, которая создает и выводит содержимое вектора.


#include

#include

using namespace std;


int v[] = {1, 2, 3, 4, 5}, i;

vector u(v+1,v+5);


int main(void)

{

for(i = 0; i < u.size(); i++)

printf("%d ",u[i]);

return 0;

}


Следующая таблица описывает методы вставки и удаления элементов вектора:

метод

описание метода

void push_back(const T& x)

вставка элемента x в конец вектора

void pop_back()

удаление последнего элемента


Итератором называется указатель на объект. Создается итератор следующим образом:

имя_шаблона<тип>::iterator имя_итератора


Класс vector имеет следующие встроенные итераторы:

итератор

описание итератора

const_iterator begin() const

указатель на начало вектора

const_iterator end() const

указатель на конец вектора


Пример 4.4. Занесем в вектор v числа 4, 10, 1. Выведем элементы вектора v при помощи итератора iter.


vector v;

vector::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.5. Занесем в вектор v квадраты натуральных чисел от 1 до 10. Удалим из вектора значения 16, 25, 36, 49.


vector 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. [Топкодер, SRM 193, SwimmingPool]. Имеется лужа некоторой формы, имеющей определенную глубину. Известно, что поперечный разрез лужи одинаков на всех глубинах. Массив rates содержит скорость наполнения лужи в определенные интервалы времени, durations[i] содержит время, в течении которого лужа наполнялась со скоростью rates[i]. За все интервалы времени, указанные в durations, лужа наполнилась до высоты height. Необходимо определить площадь поперечного разреза лужи.


Класс: SwimmingPool

Метод: int area(vector rates, vector 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


Упражнение 4.2. [Топкодер, SRM 194, Soccer]. В футболе за победу команда получает 3 очка, за ничью 1 очко, за проигрыш – 0. Массивы wins и ties содержат информацию об играх, проведенных футбольными командами в лиге: wins[i] равно числу выигранных матчей i - ой командой, ties[i] равно числу матчей, сведенных i - ой командой вничью. Необходимо найти команду с наибольшим количеством очков.


Класс: Soccer

Метод: int maxPoints(vector wins, vector 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


Упражнение 4.3. [Топкодер, SRM 315, RosePetals]. Бросаются пять игральных кубиков, стороны которых пронумерованы числами от 1 до 6:



В задаче следует подсчитать суммарное количество точек вокруг центральной точки каждой выпавшей грани. Это напоминает подсчет лепестков роз. Если грань не имеет центральной точки (2, 4, 6), то число лепестков равно нулю. Остальные три грани 1, 3 и 5 имеют центральную точку и количество их лепестков соответственно равно 0, 2 и 4.


Класс: RosePetals

Метод: int getScore(vector dice)

Ограничения: dice содержит 5 чисел от 1 до 6.


Вход. Массив dice, описывающий положение игральных кубиков после броска.


Выход. Количество лепестков в выпавшей конфигурации.


Пример входа

dice

{1, 2, 3, 2, 1}

{4, 4, 5, 6, 5}

{2, 2, 2, 2, 2}


Пример выхода

2

8

0


Упражнение 4.4. [Топкодер, SRM 212, YahtzeeScore]. Рассмотрим подсчет очков в игре яте. Бросаются 5 кубиков, на гранях которых расположены числа от 1 до 6. Игрок называет некоторое число. Активными считаются кубики, на которых выпало это число. Игрок получает количество очков, равных сумме чисел, выпавших на активных кубиках. Например, пусть на кубиках выпали значения {2, 2, 3, 5, 4}. Если игрок назовет 2, то активными будут первый и второй кубики, сумма очков на которых равна 4. Если игрок назовет 5, то получит 5 очков (имеется один кубик с 5 очками).

По заданному массиву toss, содержащему выпавшие значения на 5 кубиках, необходимо определить наибольшее количество очков, которое может получить игрок.


Класс: YahtzeeScore

Метод: int maxPoints(vector toss)

Ограничения: toss содержит в точности 5 чисел, 1  toss[i] 6.


Вход. Массив чисел toss.


Выход. Наибольшее количество очков, которое может получить игрок.


Пример входа

toss

{2, 2, 3, 5, 4}

{6, 4, 1, 1, 3}

{5, 3, 5, 3, 3}


Пример выхода

5

6

10


Упражнение 4.5. [Топкодер, SRM 217, FuelConsumption]. Необходимо совершить путешествие на машине с ограниченным количеством горючего. Известно количество горючего, потребляемое автомобилем при разных скоростях. Необходимо определить максимальное расстояние, которое можно проехать при оптимальном выборе скорости движения.


Класс: FuelConsumption

Метод: double maximalDistance(vector velocities,

vector consumptions, int fuel)

Ограничения: 2  velocities[i]  250, 1000  consumptions [i]  20000, 100  fuel  50000, массив velocities не содержит одинаковых элементов.


Вход. Два целочисленных массива velocities, consumptions и исходное количество топлива fuel в миллилитрах. consumptions[i] содержит количество литров, потребляемое автомобилем в течение одного часа при движении со скоростью velocities[i].


Выход. Максимальное расстояние, которое может проехать автомобиль. Скорость автомобиля должна быть постоянной на всем участке движения.


Пример входа

velocities

consumptions

fuel

{100}

{10000}

10000

{70, 80, 90, 100, 60, 110}

{4000, 4000, 4000, 4000,

4000, 4000}

40000

{5, 10, 20, 40, 80}

{1000, 2500, 6250,

9000, 18000}

47832


Пример выхода

100.0

1100.0

239.16


Упражнение 4.6. [Топкодер, SRM 253, ObjectPacking]. Имеется несколько коробок прямоугольной формы. Ширина i - ой коробки задается в ячейке boxWidth[i], длина – в boxLength[i]. Задан объект прямоугольной формы, ширина которого равна objWidth, а длина objLength. Необходимо найти коробку с наименьшей площадью, в которую можно поместить объект. Объект можно вращать на 0, 90, 180 или 270 градусов.


Класс: ObjectPacking

Метод: int smallBox(int objWidth, int objLength,

vector boxWidth, vector boxLength)

Ограничения: boxWidth и boxLength имеют одинаковую длину и содержат от 1 до 50 чисел, 1  objWidth[i], objLength[i], objWidth, objLength 1000.


Вход. Целые числа objWidth и objLength – размеры объекта, массивы boxWidth и boxLength, содержащие размеры коробок.


Выход. Наименьшая площадь коробки, в которую можно поместить объект. Если объект нельзя поместить ни в одну из имеющихся коробок, вернуть -1.


Пример входа

objWidth

objLength

boxWidth

boxLength

7

3

{3}

{7}

5

8

{6,9,3}

{7,4,5}

17

5

{19,10,12,40}

{12,20,15,5}

1

10

{9,1,10}

{10,6,4}


Пример выхода

21

-1

200

40


Упражнение 4.7. [Топкодер, SRM 322, DerivativeSequence]. В массиве a задана последовательность, состоящая из k элементов. По ней можно найти последовательность, состоящую из разностей соседних элементов. Например, из последовательности {5, 6, 3, 9, -1} можно получить {6-5, 3-6, 9-3, -1-9} = {1, -3, 6, -10}. Формально, последовательностью разностей для {a1, a2, …, ak} будет {b1, b2, …, bk-1}, где bi = ai+1ai.

Разностью n - го порядка для последовательности a будет такая последовательность, которая будет получена применением выше описанного правила n раз. Например, для вычисления разности второго порядка для {5, 6, 3, 9, -1} следует произвести преобразования:

{5, 6, 3, 9,-1} -> {1, -3, 6,-10} -> {-3-1, 6-(-3), -10-6} = {-4, 9, -16}

По заданной последовательности a требуется найти ее n - ую разность.


Класс: DerivativeSequence

Метод: vector derSeq(vector a, int n)

Ограничения: a содержит от 1 до 20 элементов, -100  a[i]  100, 0  n  k -1.


Вход. Массив чисел a и величина искомой разности n.


Выход. n - ая разность последовательности a.


Пример входа

a

n

{5,6,3,9,-1}

1

{5,6,3,9,-1}

2

{5,6,3,9,-1}

4

{4,4,4,4,4,4,4,4}

3


Пример выхода

{1,-3, 6, -10}

{-4, 9, -16}

{-38}

{0, 0, 0, 0, 0}


УКАЗАНИЯ К РЕШЕНИЮ УПРАЖНЕНИЙ


Упражнение 4.1. [Топкодер, SRM 193, SwimmingPool]. Вычисляем объем воды, которой наполнилась лужа. Разделив полученный объем на высоту, получим площадь поперечного разреза лужи.


#include

#include

using namespace std;


class SwimmingPool

{

public:

int area(vector rates, vector durations, int height)

{

int i, vol = 0;

for(i = 0; i < rates.size(); i++)

vol += rates[i] * durations[i];

return vol / height;

}

};


Упражнение 4.2. [Топкодер, SRM 194, Soccer]. Для каждой команды вычисляем полученное количество очков в лиге. Среди набранного количества очков каждой командой находим наибольшее значение.


#include

#include

using namespace std;


class Soccer

{

public:

int maxPoints(vector wins, vector ties)

{

int i, max = 0;

for(i = 0; i < wins.size(); i++)

if (wins[i] * 3 + ties[i] > max) max = wins[i] * 3 + ties[i];

return max;

}

};


Упражнение 4.3. [Топкодер, SRM 315, RosePetals]. Заведем массив petals, в котором petals[i] содержит количество лепестков грани с числом i. Проходим по массиву dice и суммируем количество лепестков, грань с числом dice[i] содержит petals[dice[i]] лепестков.


#include

#include

using namespace std;

class RosePetals{

public:

int getScore(vector dice)

{

int i, res, petals[] = {0,0,0,2,0,4,0};

for(res = i = 0; i < 5; i++) res += petals[dice[i]];

return res;

}

};


Упражнение 4.4. [Топкодер, SRM 212, YahtzeeScore]. Очевидно, что игрок будет называть число от 1 до 6. Для каждого такого названого числа подсчитаем сумму очков, которое он бы получил. Среди всех найденных сумм очков найдем наибольшую.


#include

#include

using namespace std;


class YahtzeeScore

{

public:

int maxPoints(vector toss)

{

int i, j, s, max;

for(max = 0, i = 1; i <= 6; i++)

{

for(s = j = 0; j < 5; j++)

if (toss[j] == i) s += i;

if (s > max) max = s;

}

return max;

}

};


Упражнение 4.5. [Топкодер, SRM 217, FuelConsumption]. Скорость движения автомобиля должна равняться такому velocities[i], для которого отношение d = velocities[i] / consumptions[i] является наибольшим. Отношение d равно расстоянию, которое можно проехать на одном литре бензина. Максимальное расстояние, которое может проехать автомобиль, равно fuel * d.


#include

#include

using namespace std;


class FuelConsumption{

public:

double maximalDistance(vector velocities, vector consumptions,

int fuel)

{

double d = 0;

for(int i = 0; i < velocities.size(); i++)

if (1.0 * velocities[i] / consumptions[i] > d)

d = 1.0 * velocities[i] / consumptions[i];

return fuel * d;

}

};

Упражнение 4.6. [Топкодер, SRM 253, ObjectPacking]. Пусть ширина текущей коробки равна W, длина – L. Объект с размерами objWidth и objLength можно поместить в коробку, если выполняется условие

(W >= objWidth) && (L >= objLength)

или

(W >= objLength ) && (L >= objWidth)

Перебираем все коробки, проверяем, можно ли в них поместить имеющийся объект. Если можно – то вычисляем площадь коробки. Находим наименьшую площадь такой коробки.


#include

#include

using namespace std;


class ObjectPacking

{

public:

int smallBox(int objWidth, int objLength,

vector boxWidth, vector boxLength)

{

int W, L, i, res = 1000000000;

for(i = 0; i < boxWidth.size(); i++)

{

W = boxWidth[i]; L = boxLength[i];

if (((W >= objWidth) && (L >= objLength)) ||

((W >= objLength ) && (L >= objWidth)))

if (W * L < res) res = W * L;

}

return (res == 1000000000) ? -1:res;

}

};


Упражнение 4.7. [Топкодер, SRM 322, DerivativeSequence]. Задача решается моделированием процесса вычисления разностей.


#include

#include

using namespace std;


class DerivativeSequence

{

public:

vector derSeq(vector a, int n)

{

int i;

while(n--)

{

for(i = 0; i < a.size(); i++) a[i] = a[i+1] - a[i];

a.erase(a.end() - 1);

}

return a;

}

};