А. Александреску - Современное проектирование на C++ (1119444), страница 19
Текст из файла (страница 19)
Структура туредснопбтгчст используется в обобщенной реализациц обратного вызова, описанной в главе 5. Время индексированного доступа к элементам списка типов прямо пропорционачьно размеру списка. Для списка значений этот метод неэффективен (по этой причине в классе зтб::1чзт не определена функция орегатогЦ). Однако ддя списков типов время тратится на этапе компиляции и его объем не имеет большого значения.' 3.7. П0ИСК ЭЛЕМЕИта Как найти нужный тип в списке типов? Попробуем реализовать алгоритм 1пдехоб, вычисляющий индекс типа в списке. Если тип не найден, результатом будет некоторое фиксированное число, например -1. Этот алгоритм представляет собой классическую рекурсивную реализацию линейного поиска.
1пдехор Входные данные: список типов тьз'зт, тип т Резульгпапы внутренняя статическая константа ча1це Если список тьз зт состоит из единственного типа нц11туре, то значение ча)це равно — 1. Иначе, если в голове списка тьч'зт находится тип т, то значение ча1це равно О. Иначе вычислить результат алгоритма тпс(ела, применяя его к хвосту списка т1ззт и типу т, и присвоить его переменной тенр. Если значение тенр равно -1, то значение ча1це равно -1. Иначе значение ча1це равно 1 плюс гевр. Алгоритм тпбехое относительно прост. Особое внимание уделяется перелаче значение ча1це ("тип не найден") в качестве результата. Последняя ветвь алгоритма (вычисление значения ча1це в зависимости от значения тенр) представляет собой операцию нал числами и выполняется с помощью условного оператора?:. Ниже приводится реализация алгоритма. тенр1ате <с1азз тьззт, с1азз т> зтгцст тпдехот; тенр1ате <с1азв т> зтгцст тпдехор<нц11туре, т> ( епцн ( ча1це = -1 ); тевр1ате <с1азз т, с1авв та11> зтгцст тпбехог<туре1чзт<т, та(1>, т> ' На самом деле при разработке больших проектов зто не совсем так.
Возможна ситуация, по крайней мере теоретически, когда сложные манипуляции со списками типов смогут сушественно замедлить компиляцию программы. В любом случае программа, содержашая очень длинный список типов, либо очень долго выполняется (и тогда лучше смириться с долгой компиляцией), янбо является слишком сложной (н тогда ее следует разработать заново). 78 Часть!. Методы ( епив( иа1ие О ); тевр1асе <с1азз иеад, с1аьа та)1, с1азз т> зтгист 1пдехоГ<туре1звт<неад, та11>, т> ( рг1иате: епив ( тевр = 1пдехоб<таз1„ т>: гиа1ие ); риб))с: епив ( иа1ие тевр = -1 ? -1: 1 е севр ); )' 3.8. Добавление элемента Нам нужно иметь возможность добавлять в список типов новый тип или список типов. Поскольку модификация списка типов невозможна, будем выполнять "возврат по значению", создавая новый список типов, содержащий результат. дррепд Входные данные. "список типов ть1зт, тип или список типов т Результат: определение внутреннего типа аеаи1т Если список тазах состоит из единственного типа ни11туре и параметр т является типом ии11туре, то класс аези1т является типом ии11туре.
Иначе, если список тсз зт состоит из единственного типа ни11туре и параметр т является отдельным типом (а ие списком типов), то класс аеаи1т является списком, состоящим из единственного элемента т. Иначе, если список тсз зт состоит из единственного типа ии11туре и параметр т является списком типов, то класс аеаи1т является типом т.
Иначе, если список тй зт ие состоит из единственного типа ии11туре, то класс аеаи1т является списком типов, головой которого является тип т~Л зт:: неад, а хвостом — результат добавления списка т к элементу тьз зт:: та)1 в качестве хвоста. Этот алгоритм естественно выражается следующим кодом. севр1ате <с1азз тьззт, с1азз т> ьсгисс дррепд; тевр1ате <> зтгист дррепд<ии11туре, ни11туре> гуредеТ ни11туре кези1т; севр1ате <с!ааа т> зсгисг дррепд<ни11туре, т> суредеб турепвт Цт) яеви1т; тевр1ате <с1азв иеад, с1азз та)1> зтгисс аррепд<ни11туре, туре1)зт<неад, таз!» ( туредеГ туре1)зт<иеад, та)1> аеви1с; Глава 3.
Списки типов севр1асе <с1азз неад, с1азз та11, с1азз т> зсгцсс лррепд<туре11зс<неад, та11>, т> ( суреде1 туре11зс«неад, сурепаее лррепд<таз1, т>::аезц1с> аезц1с; Обратите внимание на то, как последняя частично специализированная версия структуры дррепд рекурсивно конкретизирует шаблон лррепд, передавая ему хвост списка и добавляемый тип. Теперь для типов и списков типов определена униФицированная операция лррепд. Например, приведенный ниже оператор определяет список, состояший из всех числовых типов со знаком, предусмотренных в языке С++. суредеб лррепд<51дпедтпседга1з, ттясс15Т З(т1оас, доцб1е, 1опд доцб1е)>::аезц1с 51дпедтурез; 3.9. Удаление элемента Рассмотрим теперь обратную операцию — удаление элемента из списка типов.
У нас есть две возможности: удалить только первое вхождение или удалять все вхождения данного типа в списке. Изучим только первый вариант. агаве Входные данные: список типов тьсзс, тип т Результалм определение внутреннего типа аезц1с Если список тс1зс состоит из единственного типа нц11туре„ то класс аезц1с является типом нц11туре, Иначе, если тип т совпадает с типом ть1зс::неад, то класс аеьц1с является типом тсз зс::таз1.
Иначе класс яезц1с является списком типов, голова которого является типом ТС1зс:: неад, а хвостом — результат применения алгоритма агаве к хвосту ть1зс:та11 с параметром т. Вот как выглядит этот алгоритм на языке С++. севр1асе <с1азз тсззс, с1азз т> зсгцсс агаве; сеер1асе <с1азз т> // Специализация 1 зсгцсс агазе<нц11туре, т> суреде1 нц11туре аезц1с; // Специализация 2 сеер1асе <с1азз т, с1аьв та11> зсгцсс агазе<Туре11зс<т, та11>, Т> ( суредеб та11 аезц1с; севр1асе <с1азз неад, с1азз та11, с1азз т > // Специализация 3 80 Часть!. Методы зтгист егазе<туре1!зт<неад, та)1>, т> ( туребеЕ туре1ззт<неад„ турепаве егазе<та)1, т>::вези!т> яези1т; Как и для класса турелт, для этого шаблонного класса не предусмотрен вариант по умолчанию. Это означает, что класс Егазе можно конкретизировать только определенными типами. Например, выражение егазе<доиЫе, 1пт> вызовет ошибку компиляции, поскольку для него не существует ни одного соответствия.
Кроме того, необходимо, чтобы первый параметр шаблонного класса егазе был списком типов. Используя определение класса 51пдедтурез, можно записать следующее. // класс 5ове51дпебтурез содержит эквивалент класса // туреьтвт 6(зздпеб сваг, зпогт зпт, зпт, 1опд зпт, // боиЫе, !опд доиЫе) туребеЕ егазе<5здпебтурез, Лиат>::яези1т 5ове5)дпебтурез; Рассмотрим рекурсивный алгоритм удаления элементов.
Шаблон егазел11 удаляет все вхождения типа в список типов. Его реализация аналогична классу егазе, за одним исключением. При обнаружении типа, подлежащего удалению, алгоритм не останавливается, а продолжает искать и удалять соответствующие элементы из хвоста списка, рекурсивно применяя самого себя. тевр!ате <с1ааа теззт, с1аьа т> зтгист егазел11; тевр!ате <с1аза т> зтгист егазел11<ни11туре, т> ( туребеФ ни11туре яези1т; тевр1ате <с1ааа т, с1аз та!1> зтгист егазел!1<Туре11зт<т, та!1>, т> ( // проходит вниз по списку, удаляя заданный тип туребеФ турепаве егазел11<таз1, т>::яези1т яези1т; тевр1ате <с1ааа неаб, с1азз таз 1, с1азз т> зтгист егазел11<туре1ззт<неад, та!1>, т> ( // проходит по списку, удаляя заданный тип туребеЕ туре1ззт<неад турепаве Егазел11<та11, т>::яези1т> яези1т; 3.10.
Удаление дубликатов Важной операцией над списками типов является удаление дубликатов. Ее цель— трансформировать список типов так, чтобы каждый тип в списке встречался лишь один раз. Например, из списка туееьт5Т 6(нтбдет, виттоп, избдет, техтезе1б, 5сго11ваг, виттоп) нужно получить список Глава 3. Списки типов 81 ттяегт»т 6(и1ддег, вцггоп, техгг1е1д, »сго11ваг) Эта процедура немного сложнее, однако, как легко догадаться, нам поможет класс ега»е. нооор1з саге» Входные данные: список типов тг1»г Результат: определение внутреннего типа яе»ц1г Если список тг1»г состоит из единственного типа нн11туре„ то класс яе»ц1г является типом ни11туре.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
