А. Александреску - Современное проектирование на C++ (1119444), страница 20
Текст из файла (страница 20)
Иначе применить алгоритм нооцр1зсаге» к списку тг1»г::та11, получив временный список г1; применить алгоритм Ега»е к списку тг1»г::неад, получив в результате список г2. Класс яе»н1г — это список типов, голова которого является списком тг1»г::неад, а хвост — списком г2. Вот как этот алгоритм переводится на язык С++. геяр1аге <с1а»» тг1»г> »ггисг нооцр11саге»„ геар1аге <> »ггцсг нооир11саге»<но11туре> ( гуредет нц11туре'яе»ц1г; генр1аге <с1а»» неад, с1а»» тат1> »ггисг нооир11саге»< туре11»г<неад, та11» ( рг1чаге: гурег)ет гурепаее нооир11саге»<та)1>::яе»ц1г г1; гуредет гурепаие Ега»е<г2, Неад>::яе»н1г г2; рцб11 : гурег)ет туре11»г<неад, г2> яе»и1г; ); Почему мы воспользовались алгоритмом ега»е, имея в своем распоряжении алгоритм Ега»ел11? Ведь мы хотим удалить все дубликаты данного типа, не правда ли? Ответ заключается в том, что алгоритм ега»е применяется «осле рекурсивного вызова алгоритма нооцр1т саге».
Это означает, что мы удаляем из списка тип, у которого уже нет дубликата, поэтому в списке останется по крайней мере один экземпляр данного типа. Это довольно интересный пример рекурсивного программирования. 3.11. Замена элемента Иногда вместо удаления нужно заменить какой-то элемент в списке типов. Как мы увидим в разделе 3.12, замена одного типа другим представляет собой важную строительную конструкцию для многих сложных идиом. Допустим, что нам нужно заменить тип т типом о в списке типов тг1»г. яер1асе Входные данные: список типов тг1»г, тип т (подлежаший замене) и тип и (замена) Результат: определение внутреннего типа яе»ц1г Часть Е Методы Если список ть! зс состоит из единственного типа ни11туре, то класс яези1с является типом нц11туре. Иначе, если голова списка ть1вс является типом т, то класс яевц1с прелставляет собой список типов, у которого голова является типом ц, а хвостом служит список ть!5с::та!1.
Иначе класс яевц1с представляет собой список типов, у которого голова является списком ть! зс:: неад, а хвостом служит результат применения алгоритма яер1асе к списку т1з зс и параметрам т и О. Вот как выглядит код этого рекурсивного алгоритма. севр1асе <с1аза ть!зс, с1азз т, с1азз ц> всгцсс яер1асе; севр1асе <с1ааа т, с1азз ц> зсгцсс яер1асе<нц11туре, т, ц> ( суредеГ нц11туре яезц1с; севр1асе <с1азз т, с1аьа та!1, с1азз и> зсгцсс яер1асе<туре1!зс<т, таз1>, т, ц> ( суредеГ туре1!зс<ц, таз1> яезц1с; севр1асе <с1азз неад, с1азз та!1, с1аза т, с1азз ц> зсгисс яер1асе<туре1ззс<неад, таз 1>, т, ц> ( суреде1 туре1!зс<неад, сурепаве яер1асе<та!1, т, ц>::яезц1с яезц1с; ); Алгоритм яер1асел11 легко получить, изменив вторую специализацию так, чтобы в ней алгоритм рекурсивно применялся к списку таз1.
3.12. Частично упорядоченные списки типов Допустим, нам нужно упорядочить список типов по отношению наследования. Например, мы бы хотели, чтобы производные типы предшествовали базовым. Пусть мы имеем иерархию классов, изображенную на рис. 3.!. Предположим„что у нас есть список типов ттрвьтвт 4(и!ддес, всго11ваг, вцссоп, агарп!свистов) Наша задача — преобразовать его следуюшим образом; ттявьтвт 4(всго11ваг, вгарп!свистов, вцссоп, н!ддес) Следовательно,нам нужно переставить производные классы вперед, оставив порядок следования классов одинакового уровня (зйз!!пд) прежним. На первый взгляд эта задача кажется надуманной, однако она имеет большое практическое значение. Просмотр упорядоченного списка типов, в котором производные типы стоят впереди, соответствует обходу иерархии классов снизу вверх. Ме- 83 Глава 3, Списки типов ханизм двойной диспетчеризации, описанный в главе 11, применяет это важное свойство для распознавания информации о типах.
Рис. 3.!. Простая трархая классов Для упорядочения набора необходима соответствуюшзя функция. У нас уже есть статический механизм распознавания наследования, детально описанный в главе 2 Напомним, по в нашем распоряжении есть удобный макрос 5црдявцвсьл55(т, ц), возврашаюший значение тгце, если класс ц является производным от класса т. Мы просто объединим механизм распознавания наследования со списками типов.
Применение к спискам типов полноценного алгоритма сортировки невозможно, поскольку ч нас нет отношения полной упорядоченности между типами. По этой причине для классов невозможно создать эквивалент оператора сравнения орегатог<. Следовательно, нам придется использовать особенный алгоритм, переставляюший производные классы вперед и не изменяюший отношения между другими классами. пег1чедтоягопт Входные данные: список типов ть15т Резульснасн: определение внутреннего типа яезп1т Если список тьз зт состоит из единственного типа нц11туре то класс яезц1т является типом нп11туре.
Иначе найти в списке ть15т::таз1 класс самого нижнего уровня, произволный от класса тьз зт:: неад. Сохранить его во временной переменной тпемозтпегз чей. Заменить класс тпемозтпегзчед в списке тьззт::таз1 списком тьз зт:: неад, получив в результате список ш Сконструировать результат в виде списка типов, головой которого является класс тлемозтпегз чей, з хвостом — список ц Во время применения этого алгоритма к списку типов производные типы перемешаются на вершину, а базовые типы заталкиваются на дно.
В этом описании нет одной детали — алгоритма обнаружения производного класса самого нижнего уровня в заданном списке типов. Поскольку макрос 50Реявцвсьл55 84 Часть!. Методы во время компиляции порождает булевское значение, лля решения этой залечи оказывается полезным небольшой шаблонный класс 5е1есс (также описанный в главе 2). Напомним, что этот шаблонный класс выбирает один из двух типов в зависимости от значения булевской константы. Алгоритм тпемозтоегзчед получает на вход список типов и тип вазе, а возврашает — наиболее ~лубоко вложенный класс, производный ат типа вазе„находяшийся в списке (или, возможно, сам класс вазе, если производных типов в списке нет).
мозсоегтчед Входные данные: списактипов тьззс,тип т Резулынавм определение внутреннего типа вези!с Если список ттз зт состоит из единственного типа ни11туре то класс певи!с является типом т. Иначе применить алгоритм мозсоегзчед к списку тьззт::таз! и типу вазе. Получить тип сапН дате. Если тип ттззс:: неад является производным от типа сапН дате, то результатом является тип тьтзс:: неад. Иначе результатом является тип сапН дате.
Реализация алгоритма мозтоегзчед выглядит следуюшим образом. севр1ате <с1азз ттззт, с1ава т> зсгисс мозсоегзчед; севр1ате <с1авв т> всгисс мозтоегзчед<ни11туре, т> ( суредеГ т леви!с; тевр1асе <с)азз неад, с1аьв таз1, с1азз т> зсгисс мозтоегзчед<туре1ззс<неад, таз1>, т> рг1часе: суредеХ сурепаве мозсоегзчед<таз1, т>::вези!с сапНдате; риЫзс: туредеУ сурепаве 5е1ест« 5ирея50всьд55(сапндасе, неад), неад, сапдздате>: ваези!с яези1с; Алгоритм оегзчедтоегопс использует алгоритм мозсоегзчед в качестве элементарного алгоритма. Вот его реализация.
тевр1асе <с1авв т> зсгист оегзчедтогогопс; севр1ате<> зтгист оегтзчедтоггопт<ми11туре> суреде1 ни!!туре яези1т; тевр1ате <с1азз неад, с1аьв та(1> зтгист оег(чедтосгапт< туре11зс<неад, та!1» 85 Глава 3. Списки типов ргтчате: туреде1 турепаее мозгрегт'чед<тат'1, неад>:гйезц1т т)темозтоегт'чед; туреде1 турепаее яер1асе<тат1, т!темозгпегтчед, неад>::яевц1т ь; рцЫ те: гуреде1 туре1!зт<т)темозтпегтчед, ь> везц1г! Эта сложная манипуляция со списком типов обладает замечательной силой.
Преобразование пег1чедторгопг эффективно автоматизирует обработку типов, которую иначе пришлось бы долго и тщательно реализовывать вручную. Это напоминает автоматическую поддержку параллельных иерархий классов, не так ли? 3.13. Генерация класса на основе списка типов Если до сих пор списки классов казались интересными, интригующими или даже ужасными, то это только цветочки..В этом разлеле дается определение основных конструкций для генерации кода с помощью списков типов.
Это означает, что мы вообще больше не будем писать программы, а заставим компилятор делать это за нас. Такие конструкции основаны на одной из самых мощных особенностей языка С++, которой нет ни в одном другом языке, — шаблонных шаблонных иараиео(оах (тевр!ате !егор!ате рагаветега). До сих пор манипуляции со списками типов не порождали никакого кола. В результате обработки возникал новый список типов, типы или числовые статические константы (как в классе Еепят)т). Перейдем к изучению процесса генерации реального кода, т.е. к тем сущностям, которые оставляют свой след в скомпилированном коде.
Объекты списков типов и здесь не нужны. Они не имеют никакого значения во время выполнения программы и никаких функциональных возможностей. При работе со списками типов особо важна возможность генерировать код на основе списка типов. Прикладные программисты иногда лолжны наполнять класс каким-то кодом— сигнатурами виртуальных функций, объявлениями переменных или реализациями функций. Способ этого заполнения определяется списком типов. Попытаемся автоматизировать этот процесс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
