Ниже приведена обновленная версия статьи «С++ Тип признаков» Джона Маддока и Стива Клири, которая появилась в октябре 2000 года в выпуске Dr Dobb's Journal.
Генерическое программирование (код написания, который работает с любым типом данных, удовлетворяющим набору требований) стало методом выбора для предоставления многоразового кода. Тем не менее, есть времена в генерическом программировании, когда «генерика» просто недостаточно хороша - иногда различия между типами слишком велики для эффективной генерической реализации. Это когда техника признаков становится важной - путем инкапсулирования тех свойств, которые должны быть рассмотрены на основе типа по типу внутри класса признаков, мы можем минимизировать количество кода, который должен отличаться от одного типа к другому, и максимизировать количество общего кода.
Рассмотрим пример: при работе с строками символов одна общая операция состоит в том, чтобы определить длину пустой строки. Очевидно, что можно написать общий код, который может это сделать, но оказывается, что есть гораздо более эффективные методы: например, функции C-библиотеки strlen и wcslen, как правило, написаны в ассемблере, и при соответствующей аппаратной поддержке может быть значительно быстрее, чем общая версия, написанная на C++. Авторы стандартной библиотеки C++ поняли это и абстрагировали свойства char и wchar_t в класс char_traits. Генерический код, который работает с строками символов, может просто использовать char_traits<::длина для определения длины пустой строки, безопасной в том, что специализации char_traits будут использовать наиболее подходящий для них метод.
Класс char_traits является классическим примером коллекции специфических свойств типа, обернутых в один класс - то, что Натан Майерс назвал классом багажа[1]. В библиотеке типа Boost мы[2] написали набор очень специфических классов черт, каждая из которых инкапсулирует одну черту из системы типа C++; например, является типом указателя или эталонным типом? Или у типа есть тривиальный конструктор или конст-квалификатор? Классы типов имеют единый дизайн: каждый класс наследует от типа True_type, если тип имеет указанное свойство и наследует от false_type в противном случае. Как мы покажем, эти классы могут быть использованы в генерическом программировании для определения свойств данного типа и введения оптимизации, которые подходят для этого случая.
Библиотека типов также содержит набор классов, которые выполняют определенную трансформацию по типу; например, они могут удалить конст верхнего уровня или летучий квалификационный отбор из типа. Каждый класс, который выполняет преобразование, определяет один тип-член type, что является результатом трансформации. Все классы типовых атрибутов определяются внутри пространства имен boost; для краткости квалификационный параметр namespace-qualification опущен в большинстве представленных образцов кода.
Существует слишком много отдельных классов, содержащихся в библиотеке типов, чтобы дать полную реализацию здесь - см. исходный код в библиотеке Boost для полных деталей - однако, большая часть реализации в любом случае довольно повторяется, поэтому здесь мы просто дадим вам вкус для того, как некоторые из классов реализуются. Начиная с, возможно, самого простого класса в библиотеке, is_void<T> наследует от true_type только если T является void.
template <typename T>
struct is_void : public false_type{};
template <>
struct is_void<void> : public true_type{};
Здесь мы определяем первичную версию класса шаблонов is_void, и предоставляем полную специализацию, когда T является void. Хотя полная специализация класса шаблонов является важным методом, иногда нам нужно решение, которое находится на полпути между полностью общим решением и полной специализацией. Именно в этой ситуации комитет по стандартам определил частичную специализацию шаблона. В качестве примера рассмотрим класс boost::is_pointer<T>: здесь нам нужна первичная версия, которая обрабатывает все случаи, когда T не является указателем, и частичная специализация для обработки всех случаев, когда T является указателем:
template <typename T>
struct is_pointer : public false_type{};
template <typename T>
struct is_pointer<T*> : public true_type{};
Синтаксис для частичной специализации несколько аркан и может легко занять статью в своем собственном праве; как полная специализация, для того, чтобы написать частичную специализацию для класса, вы должны сначала объявить основной шаблон. Частичная специализация содержит дополнительные <...> после названия класса, которое содержит частичные параметры специализации; они определяют типы, которые будут связываться с этой частичной специализацией, а не с шаблоном по умолчанию. Правила того, что может появиться в частичной специализации, несколько запутаны, но как правило, если вы можете юридически написать две функции перегрузки формы:
void foo(T);
void foo(U);
Затем вы также можете написать частичную специализацию формы:
template <typename T>
class c{ };
template <typename T>
class c<U>{ };
Это правило ни в коем случае не является глупым, но разумно просто запомнить и закрыть достаточно, чтобы фактическое правило было полезным для повседневного использования.
В качестве более сложного примера частичной специализации рассмотрим класс remove_extent<T>. Этот класс определяет один типdef-член type, который является тем же типом, что и T, но с любыми удаленными границами верхнего уровня; это пример класса признаков, который выполняет преобразование по типу:
template <typename T>
struct remove_extent
{ typedef T type; };
template <typename T, std::size_t N>
struct remove_extent<T[N]>
{ typedef T type; };
Цель remove_extent заключается в следующем: представьте общий алгоритм, который передается типу массива в качестве параметра шаблона, remove_extent предоставляет средство определения основного типа массива. Например, remove_extent<int[4][5]>::type будет оцениваться по типу int[5]. Этот пример также показывает, что количество параметров шаблона в частичной специализации не должно соответствовать количеству в шаблоне по умолчанию. Однако количество параметров, которые появляются после названия класса, должно соответствовать количеству и типу параметров в шаблоне по умолчанию.
В качестве примера того, как можно использовать классы признаков типа, рассмотрим стандартную копию алгоритма библиотеки:
template<typename Iter1, typename Iter2>
Iter2 copy(Iter1 first, Iter1 last, Iter2 out);
Очевидно, что нет никаких проблем с написанием общей версии копии, которая работает для всех типов итераторов Iter1 и Iter2; однако, есть некоторые обстоятельства, когда операция копирования может наилучшим образом быть выполнена по вызову memcpy. Для реализации копии в терминах memcpy необходимо выполнить все следующие условия:
- Оба типа итератора
Iter1 и Iter2 должны быть указателями.
- Как
Iter1, так и Iter2 должны указывать на один и тот же тип - исключая конусы и летучие квалифицеры.
- Тип, на который указывает
Iter1, должен иметь оператора тривиальной уступки.
По тривиальному оператору присваивания мы имеем в виду, что этот тип является либо скалярным типом[3], либо:
- Тип не имеет оператора назначения, определенного пользователем.
- Тип не имеет каких-либо членов данных, которые являются ссылками.
- Все базовые классы и все объекты-члены должны иметь операторов тривиальных уступок.
Если все эти условия выполнены, то тип может быть скопирован с помощью memcpy, а не с помощью оператора назначения, сгенерированного компилятором. Библиотека типов предоставляет класс has_trivial_assign, так что has_trivial_assign<T>:: Значение верно только в том случае, если T имеет тривиальный оператор назначения. Этот класс «просто работает» для типов скаляров, но должен быть явно специализирован для типов классов/структур, которые также имеют тривиальный оператор уступки. Другими словами, если has_trivial_assign дает неправильный ответ, он даст «безопасный» неправильный ответ - что тривиальное назначение не допустимо.
Код для оптимизированной версии копии, которая использует memcpy, где это уместно, приведен в примеры. Код начинается с определения функции шаблона do_copy, которая выполняет «медленную, но безопасную» копию. Последний параметр, переданный этой функции, может быть либо true_type, либо false_type. После этого существует перегрузка do_copy, которая использует memcpy: на этот раз итераторы должны фактически указывать на один и тот же тип, а конечный параметр должен быть true_type. Наконец, версия copy звонит do_copy, проходя has_trivial_assign< value_type>() в качестве конечного параметра: это отправит в оптимизированную версию, где это уместно, иначе она будет называть «медленную, но безопасную версию».
В этих столбцах часто повторялось, что «предыдущая оптимизация является корнем всего зла» [4]. Поэтому вопрос должен быть задан: была ли наша оптимизация преждевременной? Чтобы представить это в перспективе, сроки для нашей версии копии по сравнению с обычной общей копией[5] показаны в таблице 1.
Очевидно, что оптимизация имеет значение в этом случае; но, если быть справедливым, сроки загружаются, чтобы исключить эффекты пропуска кэша - без такого точного сравнения между алгоритмами становится сложно. Однако, возможно, мы можем добавить пару оговорок к правилу преждевременной оптимизации:
- Если вы используете правильный алгоритм для работы в первую очередь, то оптимизация не потребуется; в некоторых случаях memcpy - правильный алгоритм.
- Если компонент будет повторно использоваться во многих местах многими людьми, то оптимизация может быть полезной там, где они не были бы таковы для одного случая - другими словами, вероятность того, что оптимизация будет абсолютно необходима где-то, когда-то намного выше. Как ни важно, воспринимаемая ценность реализации акций будет выше: нет смысла стандартизировать алгоритм, если пользователи откажутся от него на том основании, что есть лучшие, более оптимизированные версии.
Table 1.1. Time taken to copy 1000 elements using `copy<const T*, T*>` (times
in micro-seconds)
|
Версия
|
T T
[ORIG_END] --> |
Время
|
"Оптимизированная" копия |
char |
0,99 |
Обычная копия |
char |
8.07 |
"Оптимизированная" копия |
int |
2.52 |
Обычная копия |
int |
8.02 |
Оптимизированный пример копирования показывает, как черты типа могут быть использованы для выполнения решений по оптимизации в компиляционное время. Другое важное использование признаков типа - позволить коду компилировать, что в противном случае не будет делать этого, если не будет использована чрезмерная частичная специализация. Это возможно путем делегирования частичной специализации классам признаков типа. Наш пример для этой формы использования - это пара, которая может содержать ссылки [6].
Во-первых, рассмотрим определение std::pair, опустив операторов сравнения, конструктора по умолчанию и конструктора шаблонов для простоты:
template <typename T1, typename T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(const T1 & nfirst, const T2 & nsecond)
:first(nfirst), second(nsecond) { }
};
Теперь этот «парик» не может содержать ссылки, поскольку он в настоящее время стоит, потому что конструктор потребует ссылки на ссылку, которая в настоящее время является незаконной [7]. Давайте рассмотрим, какими должны быть параметры конструктора для того, чтобы позволить «паре» содержать непрофильные типы, ссылки и постоянные ссылки:
Table 1.2. Required Constructor Argument Types
|
Тип T1
|
Тип параметра для инициализации конструктора
|
T T
[ORIG_END] --> |
const T & |
T & |
T & |
const T & |
const T & |
Небольшое знакомство с классами признаков типа позволяет нам построить единое картирование, которое позволяет определить тип параметра от типа содержащегося класса. Классы признаков типа обеспечивают трансформацию add_reference, которая добавляет ссылку на ее тип, если это уже не ссылка.
Table 1.3. Using add_reference to synthesize the correct constructor type
|
Тип T1
|
Тип const T1
|
Тип add_reference<const T1>::type
|
T T
[ORIG_END] --> |
const T |
const T & |
T & |
T & [8] |
T & |
const T & |
const T & |
const T & |
Это позволяет нам создать первичное определение шаблона для pair, которое может содержать неконечные типы, типы ссылок и постоянные типы ссылок:
template <typename T1, typename T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(boost::add_reference<const T1>::type nfirst,
boost::add_reference<const T2>::type nsecond)
:first(nfirst), second(nsecond) { }
};
Добавьте обратно в стандартные операторы сравнения, конструктор по умолчанию и конструктор копии шаблонов (которые все одинаковы), и у вас есть std::pair, который может содержать ссылки типов!
Это же расширение могло бы быть сделано с использованием частичной специализации шаблона pair, но для специализации pair таким образом потребуется три частичных специализации, плюс основной шаблон. Тип признаков позволяет нам определить один основной шаблон, который автоматически корректирует себя на любую из этих частичных специализаций, вместо грубой части специализации. Использование типовых признаков в этом виде позволяет программистам делегировать частичную специализацию классам признаков типа, что приводит к коду, который легче поддерживать и легче понять.
Мы надеемся, что в этой статье мы смогли дать вам некоторое представление о том, какие тип-трассы все. Более полный список доступных классов находится в документации для повышения, а также дополнительные примеры с использованием признаков типа. Шаблоны позволили использовать C++, чтобы использовать преимущества повторного использования кода, которое приносит генерическое программирование; надеюсь, эта статья показала, что генерическое программирование не должно опускаться до самого низкого общего знаменателя, и что шаблоны могут быть оптимальными, а также общими.
Авторы хотели бы поблагодарить Beman Dawes и Howard Hinnant за их полезные комментарии при подготовке этой статьи.
- Nan C. Myers, C++ Report, June 1995.
- Библиотека черт типа основана на вкладе Стива Клири, Beman Dawes, Howard Hinnant и John Maddock: ее можно найти на www.boost.org.
- Тип скаляра представляет собой арифметический тип (т.е. встроенный целочисленный или плавающий тип), тип перечисления, указателем, указателем для члена или конструкционно-квалифицируемой версией одного из этих типов.
- Это цитата из Дональда Кнута, ACM Computing Surveys, декабрь 1974, pg 268.
- Испытательный код доступен как часть библиотеки повышения полезности (см. algo_opt_examples.cpp), код был составлен с gcc 2.95 со всеми включенными оптимизированиями, тесты были проведены на 400MHz Pentium II машина под управлением Microsoft Windows 98.
- Джон Маддок и Говард Хиннант представили в Boost библиотеку «compressed_pair», которая использует технику, аналогичную описанной здесь, чтобы иметь ссылки. Их пара также использует черты типа, чтобы определить, являются ли какие-либо из типов пустыми, и будет происходить вместо того, чтобы содержать для сохранения пространства - отсюда и название «сжато».
- На самом деле это проблема с Рабочей группой по базовому языку C++ (проблема #106), представленной Bjarne Stroustrup. Предварительное решение состоит в том, чтобы позволить «ссылку на ссылку на T» означать то же самое, что и «ссылка на T», но только в мгновенных шаблонах, в методе, аналогичном нескольким квалификационным данным.
- Для тех из вас, кто задается вопросом, почему это не должно быть конкретизировано, помните, что ссылки всегда имплицитно постоянны (например, вы не можете переназначить ссылку). Помните также, что " констант T & " - это нечто совершенно иное. По этой причине Cv-qualifiers на шаблонных аргументах типа, которые являются ссылками, игнорируются.
