Обобщенные алгоритмы

Алгоритмы занимают центральное место в обработке данных. Универсальные алгоритмы, работающие с любыми наборами объектов, делают программу и проще, и безопаснее, а возможность влиять на работу алгоритма во время выполнения произвела настоящую революцию в программировании.

В подмножество стандартной библиотеки С++, известное под названием стандартной библиотеки шаблонов (Standard Template Library, STL), была изначально заложена концепция обобщенных алгоритмов - фрагментов кода для обработки последовательностей значений произвольного типа с обеспечением безопасности по отношению к типам. Это делалось для того, чтобы программист мог использовать готовые алгоритмы для решения практически любых задач, и ему не приходилось вручную программировать циклы каждый раз, когда потребуется обработать набор данных. Впрочем, чтобы овладеть всей мощью STL, вам придется изрядно потрудиться. К концу этой главы вы либо начнете относиться к алгоритмам как к привычному рабочему инструменту, либо решите, что разбираться в них слишком хлопотно. Большинство программистов обычно сначала сторонится алгоритмов, но с течением времени начинает все чаще ими пользоваться.

Первый взгляд

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

ление того, как это делается. Проблема как делать? решается раз и навсегда и скрывается в коде алгоритма, готовом к многократному использованию. Рассмотрим пример использования алгоритма сору:

: С06:СоруInts.срр

Копирование последовательности int без явного определения цикла

linclude <algorithm>

linclude <cassert>

linclude <cstddef> Для size t

using namespace std:

int mainO {

int a[] = {10. 20. 30}:

const size t SIZE = sizeof a / sizeof a[0]:

int b[SIZE]:

copy(a. a + SIZE, b):

for (int i = 0: i < SIZE: ++i) assert(a[i] == b[i]): } III:-

Первые два параметра алгоритма сору() определяют интервал входной последовательности - в данном случае это массив а. Интервалы определяются парой указателей. Первый указатель ссылается на первый элемент последовательности, а второй - на элемент в позиции, следующей за последним элементом массива. Поначалу такой способ определения выглядит несколько странно, но это старая и довольно удобная идиома языка С. Например, разность этих двух указателей дает количество элементов в последовательности. Что еще важнее, в реализации сору второй указатель может использоваться как барьер , позволяющий остановить перебор последовательности. Третий аргумент ссылается на начало выходной последовательности (массива b в нашем примере). Предполагается, что выходной массив имеет достаточный размер и сможет вместить копируемые элементы.

Если бы алгоритм сору() умел копировать только целые числа, особой пользы он бы не приносил. Однако этот алгоритм умеет копировать любые последовательности объектов. Например, в следующей программе копируются объекты типа string:

: C06:CopyStrings.cpp Копирование строк linclude <algorithm> linclude <cassert> linclude <cstddef> linclude <string> using namespace std:

int mainO {

string a[] = { read , my , lips }:

const size t SIZE = sizeof a / sizeof a[0]:

string bCSIZE];

copy(a. a + SIZE, b):

assert(equal(a. a + SIZE, b)): } III:-

В этом примере также используется алгоритм equal(), который возвращает true только в том случае, если каждый элемент первого интервала равен соответствующему элементу второго интервала (проверка осуществляется оператором ). В этом примере каждый интервал перебирается дважды: сначала для копирования, потом для сравнения, и при этом программа не содержит ни одного цикла!

Универсальность обобщенных алгоритмов объясняется тем, что они реализованы в виде шаблонов функций. Если вы думаете, что реализация сору() выглядит так, как показано ниже, то вы почти правы:

tempiate<typename Т> void сору(Т* begin. Т* end. Т* dest) { while (begin !- end) *dest++ = *begin++;

Мы говорим почти , потому что соруО обрабатывает интервалы, границы которых определяются любыми объектами, похожими на указатели, например, итераторами. Благодаря такому подходу алгоритм сору() может использоваться для копирования вектора:

: С06:СоруVector.срр

Копирование содержимого вектора

linclude <algorithm>

linclude <cassert>

linclude <cstddef>

linclude <vector>

using namespace std:

int mainO {

int a[] = { 10. 20. 30 }:

const size t SIZE = sizeof a / sizeof a[0]:

vector<int> vKa. a + SIZE):

vector<int> v2(SIZE):

copy(vl.begin(), vl.endO. v2.beginO):

assert(equal(vl.beginO. vl.endO. v2.beginO)): } III:-

Первый вектор vl инициализируется целыми числами из массива а. В определении вектора v2 используется другой конструктор vector, выделяющий память для SIZE элементов, инициализированных нулями (значение по умолчанию для int).

Как и в предыдущем примере с массивом, очень важно, чтобы вектор v2 имел достаточные размеры для размещения копии содержимого vl. Специальная библиотечная функция back inserter() возвращает особый тип итератора, который вставляет элементы вместо их перезаписи. При этом контейнер автоматически выделяет новую память по мере надобности. Благодаря использованию функции back inserter() в следующем примере нам не приходится заранее определять размер выходного вектора v2:

: СОб:InsertVector.срр

Присоединение элементов одного вектора к другому вектору

linclude <algorithm>

linclude <cassert>

linclude <cstddef>

linclude <iterator>

linclude <vector>

using namespace std:

int mainO {

int a[] = { 10. 20. 30 }:

const size t SIZE = sizeof a / sizeof a[0]:

vector<int> vKa. a + SIZE):

vector<int> v2: Вектор v2 пуст

copy (vl. begi n(). vl.endO. back inserter(v2)):

assert(equal(vl.beginO. vl.endO. v2.beginO)): } /:-