Шаблоны. Именованные области. Стандартная библиотека шаблонов (STL). Векторы.

Михаил Медведев

[к списку лекций]

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

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

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

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

5. Задачи.

http://www.topcoder.com/tc: SRM 193 (SwimmingPool), SRM 194 (Soccer), SRM 212 (YahtzeeScore), SRM 217 (FuelConsumption), SRM 253 (ObjectPacking), SRM 315 (RosePetals), SRM 322 (DerivativeSequence).

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;

Библиотека STL содержит пять основных видов компонентов:

1.    алгоритм (algorithm): определяет вычислительную процедуру.

2.    контейнер (container): управляет набором объектов в памяти.

3.    итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера.

4.    функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами.

5.    адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

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

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

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

4. ВЕКТОРЫ

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

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

#include <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 будем обозначать тип “ссылка”. Следующие методы созданы для работы с вектором:

Пример 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");

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

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

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

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

Пример 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");

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

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

Выход. Площадь поперечного разреза лужи.

Пример входа

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

3

0

1

Упражнение 4.2. [Топкодер, SRM 194, Soccer]. В футболе за победу команда получает 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, содержащие информацию о командах.

Выход. Наибольшее количество очков, заработанное одной командой в лиге.

Пример входа

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

14

145

105

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

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

Класс: RosePetals

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

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

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

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

Пример входа

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

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<int> toss)

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

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

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

Пример входа

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

5

6

10

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

Класс: FuelConsumption

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

                             vector<int> consumptions, int fuel)

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

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

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

Пример входа

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

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<int> boxWidth, vector<int> boxLength)

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

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

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

Пример входа

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

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}. Формально, последовательностью разностей для {a₁, a₂, …, a_k} будет {b₁, b₂, …, b_k-1}, где b_i = a_i+1 – a_i.

Разностью 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<int> derSeq(vector<int> a, int n)

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

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

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

Пример входа

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

{1,-3, 6, -10}

{-4, 9, -16}

{-38}

{0, 0, 0, 0, 0}

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

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

#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. [Топкодер, SRM 194, Soccer]. Для каждой команды вычисляем полученное количество очков в лиге. Среди набранного количества очков каждой командой находим наибольшее значение.

#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;

  }

};

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

#include <cstdio>

#include <vector>

using namespace std;

class RosePetals{

public:

  int getScore(vector<int> 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 <cstdio>

#include <vector>

using namespace std;

class YahtzeeScore

{

public:

  int maxPoints(vector<int> 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 <cstdio>

#include <vector>

using namespace std;

class FuelConsumption{

public:

  double maximalDistance(vector<int> velocities, vector<int> 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 <cstdio>

#include <vector>

using namespace std;

class ObjectPacking

{

public:

  int smallBox(int objWidth, int objLength,

               vector<int> boxWidth, vector<int> 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 <cstdio>

#include <vector>

using namespace std;

class DerivativeSequence{

public:

  vector<int> derSeq(vector<int> 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;

  }

};

[к списку лекций]