Д. Вандевурд, Н.М. Джосаттис - Шаблоны C++. Справочник разработчика (2003) (1160769), страница 62
Текст из файла (страница 62)
В результате реализации такого цикла получаем приведенную ниже метапрограмму. // тека/вс1гс3.)трр №1йпг)ей Я()НТ НРР №с)еййпе Я()НТ НРР // Первичный шаблон, предназначенный для итерационного // вычисления вЧгг(И). гетр1аге <1пг и, 1пк 1=1> с1авв ЯЧгс ( рцЬ11с: епша ( гевц1Г = (1*1<И) 7 ЯЧгв<И,1+1>::гевц1Г : 1 )/ // Частичная специализация, предназначенная для завершения // процесса рекурсии Сетр1аке <йпс И> с1авв ЯЧгк<И, И> ( рц)з11с: епша ( гевц1Г = И ); №епбй№ // Я()НТ НРР Цика осуществляется путем использования переменной 1 в шаблоне ЯЧгс<И,1>. До тех пор пока логическое выражение 1*1<И остается истинным, переменной гевц1С присваивается значение выражения ячгс<и,1+1>, в котором реаяизуется следующая итерация.
В противном случае переменной гевц1г присваивается значение переменной 1. Например, если нужно вычислить значение ЗЧгс<16>, сначала вычисляется яцгс<1б, 1>. Таким образом, в начале итерации значение так называемой нереиенной индукции 1 равно единице. далее, поскольку 1*1<И, переходим к следующей итерации. вычисляя ЯЧгс<И, 1+1>:: гевц1с. Как только значение выражения 1*1 станет равным илн превысит и, значение переменной 1 объявляется результатом 17.4. Применение переменных индукции 335 )т)ожет возникнуть вопрос о том, зачем нужна специализация шаблона, завершающая процесс рекурсии.
Казалось бы, первый шаблон рано или поздно найдет результирующее значение переменной 1, благодаря чему рекурсия, по-видимому, окончится. На самом деле это не так, и причиной, как и раньше, является эффект инстанцирования обеих ветвей оператора ?:, который обсуждался в предыдущем разделе.
Таким образом, в процессе вычисления выражения Яс)гг< 4 > будет осуществляться несколько инстанцирований шаблонов. ° Этап 1: геви1С = (1*1<4) ? Яс(ге<4,2>::геви1С 1 ° Этап 2: гевп1с = (1*1<4) ? (2*2<4) ? Яаке<4,3>::геви1с 2 1 ° Этап 3: гевп1с = (1*1<4) ? (2*2<4) ? (3*3<4) ? Яцгг<4,4>::гевп1с 3 2 ° Этап 4: геви1С = (1*1<4) ? (2*2<4) ? (3*3<4) ? 4 3 2 1 Несмотря на то что результат найден на втором этапе, инстанцированне шаблонов осуществляется компилятором до тех пор, пока рекурсия не завершится в специализации шаблона. Если не задать специализацию, компилятор будет продолжать инстанцирование, пока не исчерпает свои внутренние ресурсы.
Как и раньше, проблема решается с помощью шаблона 1йТ)зепп1ве. // тека/вс(гг4.)трр ()Нпс)ег Я()ПТ НРР Иеййпе Я()1(Т НРР ()Тпс1пс)е "1Ш~епе1ве.)зрр" // Шаблон, в котором переменной гевп1С // присваивается аргумент шаблона сешр1асе<1пс ы> с1авв т/а1ие ( рпЬ11с: Глава 17. Метапрограммы 336 епшп ( геви1с = Ы )> // Шаблон для итерационного вычисления вцгг(Н) Сешр1аке <1пе Н, 1пе 1=1> с1авв Яс)гк ( риЬ11с: // Инстанцирование следующего шага или результата Гурейей Гурепаше 1ЙТЬепЕ1ве< (1*1<И), Яс)гг<Н, 1+1>, 1/а1це<1> >:гйеви1СТ // епшп ( геви1Г = ЯХТ::геви1Г ФепЖЙ //Я()ЕТ НРР В качестве завершающего критерия используется шаблон Ча1ие<>, который возвращает значение аргумента шаблона в геви1г.
Как и раньше, с помощью шаблона 16ТЬепЕ1ве<> удается уменьшить количество инстанцирований, которое становится пропорциональным не Н, а 1ойз(Н). Это весьма существенное сокращение затрат в процессе работы метапрограммы. Что касается компиляторов, в которых количество инстанцирований шаблонов ограничено, то с их помощью новая версия программы сможет вычислять квадратные корни из больших чисел, чем предыдущая. Если компилятор, например, поддерживает до 64 вложенных инстанцирований шаблонов, то максимальное число, из которого можно вычислить квадратный корень, равно не 64 (как двя предыдущей реализации алгоритма), а 4096. Вывод "итеративного" шаблона Ясге будет выглядеть так: ЯЧге<16>::гевц1Г < 4 Яоге<25>::геви1Г = 5 Ясгг<42>::геви1Е = 7 Яс)гс<1»::гевц1Е = 1 Заметим, что для простоты рассмотренная выше реализация выдает округленное к большему целое значение квадратного корня (результат вычисления квадратного кори~ из 42 равен не 6, а 7).
17.5. Полнота вычислений Рассмотренные примеры шаблонов Роы3<> и ясгс<> продемонстрировали, что шаблонные метапрограммы могут содержать: 17.6. Рекурсивное инстанцирование и рекурсивные аргументы шаблона 337 ° переменные состояния (параметры шаблона) ° циклические конструкции, реализуемые с помощью рекурсии; ° конструкции, осуществляющие выбор пути с помощью условных выражений или специализаций; ° арифметические операции с целыми числами.
Если нет ограничений на количество рекурсивных инстанцирований шаблонов и количество переменных состояния, то этих элементов достаточно для вычисления почти всего, что поддается вычислению. Однако воплощение алгоритмов с помощью шаблонов может оказаться не таким удобным„как "обычное" программирование. Более того, инстанцирование шаблонов, как правило, требует существенных затрат ресурсов компилятора.
При этом рекурсивное инстанцирование большого количества шаблонов значительно замедляет работу компилятора и даже может стать причиной того, что возможности вычислительных ресурсов компьютера будут исчерпаны. Согласно рекомендациям стандарта для языка программирования С++, компилятор должен иметь возможность осуществить как минимум 17 уровней рекурсивных инстанцирований, однако это не является жестким требованием.
При интенсивном применении шаблонного программирования этот предел может оказаться далеко не достаточным. Таким образом, на практике к применению шаблонного программирования следует относиться крайне осторожно. Однако есть ситуации, когда такой метод является незаменимым инструментом программиста. В частности, иногда рекурсивные шаблоны могут быть "спрятаны" внутри более традиционных, что позволяет добиться более производительной реализации алгоритма. 17.6. Рекурсивное инстанцирование и рекурсивные аргументы шаблона Рассмотрим приведенный ниже рекурсивный шаблон. севр1аке<пурепаве Т, Сурецаве д> впкисс роиЬ11ху (); севр1апе<йпсИ> вккисл ТкоиЬ1е ( куреней роиЬШу<сурепаве ТкоиЫе<В)-1>:: 7 опдТуре, сурепаве ТкоиЫе<в(-1>:: 7 опдТуре> 1 опдТуре з кевр1апе<> всгцск ТгопЫе<0> Пурес(ей с)оцЬ1е т.опдтуре; Творе<10>::топдТуре оисп| Глава 17.
Метапрограммы 338 Инструкция ТгоиЬ1е< 10 >:: Ьопдтуре не только инициирует рекурсивное инстанцирование шаблонов ТгоиЬ1е<9>, ТгоиЬ1е<8>, ..., ТгоиЬ1е<0>, но и инстанцирует структуру )зоиЬ11йу, что приводит к быстрому усложнению определения типа. Скорость роста сложности продемонстрирована в табл.
17.1. Таблица 17.1. Усложнение обьянлення типа ТгоиЬ1е<нэ з з 1.опдТуре Имя типа Определение типа ТгоиЬ1е < 0 >::?,опдтуре с1оиЬ1е ТгоиЫе<1>::1опдТуре ВоиЬШу<доиЫе, <1оиЫе> ТгоиЫе<2 >:: Ьопдтуре ноиЫ1гу<ЭоиЬШу<с1оиЫе, <1оиЫе>, роиЬШу<доиЫе, с1оиЫе» ТгоиЫе<3 >:: Ьопдтуре ЭоиЫТгу<РоиЫййу<1ЗоиЬШу<боиЫе, <1оиЫе>, )зоиЫ1йу<доиЫе, боиЫе», <1зоиЬШу<доиЫе, <1оиЫе >, ГЗоиЫНу<боиЫе, сгоиЬ1е» > Как видно из этой таблицы, сложность описания типа выражения ТгоиЫе<Н>:: 1 опдТуре с увеличением Н растет по закону 2".
Вообще говоря, в такой ситуации компилятор несет даже большую нагрузку, чем при рекурсивном инстанцировании шаблонов, в котором не принимают участия рекурсивные аргументы шаблона. Одна из возникающих в таких случаях проблем состоит в том, что компилятор сохраняет представление скорректированного имени типа. В этом скорректированном имени определенным образом закодирована точная специализация шаблона. В ранних версиях компиляторов С++ применялась кодировка, в которой длина была (грубо) прямо пропорциональна длине тела шаблона. Для шаблона ТгоиЬ1е<10>:: Ьопдтуре в таких компиляторах пришлось бы затратить более 10000 символов.
В более новых компиляторах С++ принимается во внимание, что в современных программах на С++ довольно часто встречаются вложенные шаблоны, и с учетом этого в них используется более компактная кодировка. Это способствует существенному снижению темпов роста объема кодировки для имен (например, для типа ТгоиЬ1е<10>::1опдТуре потребуется всего несколько сотен символов). При прочих равных условиях рекурсивное инстанцнрование шаблонов предпочтительнее организовать так, чтобы аргументы шаблона не были рекурсивно вложенными.
17.7. Метапрограммы для развертывания циклов Одно из первых практических применений метапрограммирования состояло в развер тывании циклов при выполнении числовых расчетов. Ниже рассматривается завершенный пример, в котором производятся эти вычисления. В приложениях, осуществляющих числовые расчеты, зачастую обрабатываются л-мерные массивы, или векторы. Одна из типичных операций в таких расчетах — так на- 17.7. Метапрограммы для развертывания циклов 339 зываемое скалярное произведение. Скалярным произведением двух векторов а и Ь назы- вается сумма попарных произведений всех компонентов обоих векторов. Например, если у каждого из векторов по три компонента [т.е. в соответствующих им одномерных мас- сивах по три элемента), то их скалярное произведение определяется по формуле а[О) *ЫО]+а[1] *Ь[1]+а[2] *Ь[2]; // мега/1оор1.Ьрр ()Ьйпс)ей ЬООР1 НРР ()деййпе ЬООР1 НРР еетр1аее <еурепаве т> Тп11пе Т с)ос ргобисг(1пс Жв, Т* а, Т* Ы ( т геви1Е = Т(); аког(1пе 1 = О; 1 < с)1пп ++1) ( геви1с += а[1]*Ь[1]; ) гесигп геви1Ы ()епс)1й // ЬООР1 НРР Вызовем зту функцию в приведенном ниже фрагменте программы.
// п~ееа/1оор1.срр ()1пс1ис)е <Ьовггеат> ((Тпс1ис)е "1оор1.Ьрр" Ьпг пайп() ( Тпс а[3) = ( 1, 2, 3); Тпс Ь[3] = [ 5, б, 7)р всс)::соиг « "Йог ргос)исе(З,а,Ы «с)ог. ргос)исс (3, а, Ы всс)>,соиг « "с)ос ргобисс(З,а,а) « с)ог,ргос)иск(З,а,а) ) « '1п « '~п' В результате получим следующее: с)ос ргос)исс(З,а,Ь)= 38 с)ог ргос)иск(З,а,а)= 14 Обычно в математической библиотеке содержится функция, предназначенная для вы- числения скалярного произведения.
Рассмотрим приведенную ниже простейшую реали- зацию этой процедуры. Глава 17. Метапрограммы Результат правильный, однако он достигается слишком длинным путем, который нежелателен при разрабогке серьезных высокопроизводительных приложений. Чтобы достичь оптимальной производительности, недостаточно даже объявить функцию встраиваемой. Проблема в том, что компиляторам обычно лучше удается оптимизировать циклы, в которых выполняется большое количество итераций, а в данном случае такой метод непроизводительный. Намного лучше было бы непосредственно расписать этот цикл как а [О) «Ы 0) +а [1) *Ь [1) +а [2) *Ь [2) Конечно, если в процессе работы программы время от времени нужно вычислить одно-два скалярных произведения, то производительность функции йот ргойцсс () не играет сушественной роли.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
