Общее оглавление

Введение

Стандартная библиотека C++ предоставляет ряд шаблонных функций, предназначенных для работы с диапазонами данных, заданными итераторами. Эти функции известны как “алгоритмы (STL)” и определены в двух заголовочных файлах: algorithm и numeric. Список стандартных алгоритмов можно найти, например, здесь или здесь.

Данная лабораторная работа посвящена алгоритму inner_product.

Простые примеры

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

template <class It1, class It2>
bool equal(It1 from1, It1 to1, It2 from2)
{
  while (from1 != to1)
  {
    if (*from1 != *from2)
      return false;
    ++from1;
    ++from2;
  }
  
  return true;
}

Однако писать такую функцию не требуется — она уже есть в Стандартной библиотеки (функция equal в заголовочном файле algorithm).

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

Мы могли бы изменить наш код, заменив != на >=, но стандартный вариант equal допускает ещё один необязательный параметр — компаратор, которым здесь можно воспользоваться:

template <class It1, class It2>
bool each_smaller(It1 from1, It1 to1, It2 from2)
{
  return std::equal(from1, to1, from2, std::less<>{});
}

int test_each_smaller()
{
  int a[] { 1, 2, 3, 4, 5 },
      b[] { 2, 3, 4, 5, 6 },
      c[] { 2, 3, 4, 6, 2 };

  if (!each_smaller(std::begin(a), std::end(a), std::begin(b)))
    return 1;
  if (each_smaller(std::begin(a), std::end(a), std::begin(c)))
    return 2;
  return 0;
}

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

Пока это легко: достаточно использовать логическое отрицание, чтобы привести квантор существования к квантору всеобщности. Проверим, что первая последовательность не “больше или равна” второй поэлементно:

template <class It1, class It2>
bool exists_smaller(It1 from1, It1 to1, It2 from2)
{
  return !std::equal(from1, to1, from2, std::greater_equal<>{});
}

А если ещё изменить задачу и спросить “сколько элементов в первой последовательности меньше соответствующих элементов во второй последовательности”? Для решения этой задачи функция equal уже не является подходящим инструментом. Однако есть функция более общего характера, с помощью которой можно решить данную задачу — inner_product (“скалярное произведение”, определена в заголовочном файле numeric).

Обобщённое скалярное произведение принимает два функтора: аналог умножения (применяется к элементам входных последовательностей попарно) и аналог сложения (применяется к результатам умножения).

Итак, с помощью inner_product можно посчитать количество меньших элементов:

template <class It1, class It2>
size_t count_smaller(It1 from1, It1 to1, It2 from2)
{
  return std::inner_product(from1, to1, from2,
    size_t(0), // начальное значение суммы
  std::plus<size_t>{}, std::less<>{});
}

int test_count_smaller()
{
  int a[] { 1, 2, 5, 4, 5 },
      b[] { 2, 3, 4, 5, 6 },
      c[] { 1, 3, 4, 6, 2 };

  if (count_smaller(std::begin(a), std::end(a), std::begin(b)) != 4)
    return 1;
  if (count_smaller(std::begin(a), std::end(a), std::begin(c)) != 2)
    return 2;
  return 0;
}

При желании, легко определить equal через inner_product. (Но это неразумно. Почему?)

И, если вспомнить о лабораторной работе 9, то косинусный коэффициент двух векторов через inner_product “в лоб” записывается так:

template <class NT>
NT cos(const vector<NT> &a, const vector<NT> &b)
{
  if (b.size() < a.size())
    return cos(b, a);
  return inner_product(begin(a), end(a), begin(b), NT(0))
   / (sqrt(inner_product(begin(a), end(a), begin(a), NT(0)))
    * sqrt(inner_product(begin(b), end(b), begin(b), NT(0))));
}

Задание

Пусть многоугольник задан последовательностью значений x-координат вершин и последовательностью y-координат вершин (в порядке соединения вершин рёбрами).

Написать функцию, принимающую эти две последовательности и вычисляющую площадь многоугольника с помощью известной формулы, используя inner_product.

Общее оглавление

Кувшинов Д.Р. © 2016