Библиотека BOOST C++: свойства типов

English Главная Карта STL BOOST C++ Loki Примеры Метапрограммирование

by John Maddock and Steve Cleary

Это черновой вариант статьи, которая опубликована в октябрьском выпуске Dr Dobb's Journal

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

Рассмотрим следующий пример: при работе с символьными строками, одной из распространенных операций является определение длины строки с нулевым конечным символом. Очевидно, что можно написать обобщенный код для выполнения этой задачи, но оказывается, что есть гораздо более эффективные методы. К примеру, библиотека функций C содержит функции strlen и wcslen, которые обычно написаны на ассемблере, и при условии некоторой аппаратной поддержки могут быть значительно быстрее, чем обобщенные версии, написанные на C++. Авторы стандартной библиотеки C++ учли это, и абстрагировали соответствующие свойства типов char и wchar_t в класс char_traits. Обобщенный код, работающий с символами, может просто использовать char_traits<>::length для определения длины строки с терминирующим нулем, что работает при условии наличия специализаций шаблона char_traits с наиболее подходящими методами для типов символов.

Свойства типов (type traits)

Класс char_traits является классическим примером коллекции специфичных для типа свойств, собранной внутри одного класса - то, что Натан Майерс (Nathan Myers) назвал baggage class[1]. В библиотеке свойств типов Boost C++ , мы[2] реализовали набор специальных классов свойств, каждый их которых инкапсулирует единственное свойство, определенное для типа в языке C++; к примеру, является ли тип указателем или ссылкой? Или имеет ли тип пустой (trivial) конструктор, или квалификатор const? Классы свойств типов имеют унифицированный дизайн: каждый класс имеет единственное поле value, константу времени компиляции, которая получает значение true если тип имеет определенное свойство, и false в противном случае. Как будет показано, эти классы могут быть использованы в обобщенном программировании для определения свойств заданного типа и выполнения оптимизации, которая применима к данному типу.

Библиотека свойств типов также содержит набор классов, которые выполняют некоторые преобразования типов: к примеру, они могут убрать квалификатор const самого верхнего уровня. Каждый класс, который выполняет преобразование, содержит единственный член (объявление типа через typedef) type, который является результатом преобразования. Все классы свойств типов объявлены в пространстве имен boost. Для краткости, квалификатор пространства имен пропускается в большинстве приводимых далее примеров кода.

Реализация

Число содержащихся в библиотеке свойств типов отдельных классов слишком велико, чтобы приводить здесь их полную реализацию - смотрите исходные коды библиотеки в Boost - однако, большинство реализация содержат повторяющийся код, так что далее мы опишем общую схему реализации этих классов. Начнем с вероятно самого простого типа в библиотеке - is_void<T>. Этот шаблонный класс содержит объявление члена value, который получает значение true только если T является типом void.

template <typename T> 
struct is_void
{ static const bool value = false; };

template <> 
struct is_void<void>
{ static const bool value = true; };

Здесь мы определили первоначальную версию шаблонного класса is_void, и создали полную специализацию для случая, когда T является типом void. В то время как полная специализация шаблонного класса является важным методом, иногда необходимо реализовать решение, которое является наполовину полностью обобщенным решением и наполовину полной специализацией. Это как раз тот случай, для которого стандарт предусматривает частичную специализацию шаблона класса. В качестве примера, рассмотрим шаблонный класс boost::is_pointer<T>: здесь нам нужна исходная версия, которая обрабатывает все случаи, когда T не является указателем, и частичную специализацию для случаев, когда T является указателем:

template <typename T> 
struct is_pointer 
{ static const bool value = false; };

template <typename T> 
struct is_pointer<T*> 
{ static const bool value = true; };

Синтакс для частичной специализации немного запутан и его описание может само по себе потребовать целой статьи; как и для полной специализации, для реализации частичной специализации класса сначала необходимо сначала определить исходный шаблон. Частичная специализация содержит дополнительный список параметров <…> после имени класса. В этом списке задаются параметры частичной специализации; они задают типы, которые будут привязаны к частичной специализации, а не к исходному шаблону. Правила для определения того, что может появиться в частичной специализации, несколько замысловаты, но в качестве упрощенного правила можно запомнить следующее. Если можно записать две перегруженные функции в виде:

void foo(T);
void foo(U);

то также можно записать частичную специализацию в виде:

template <typename T>
class c{ /*details*/ };

template <typename T>

class c<U>{ /*details*/ };

Это правило безусловно защищает от ошибок, а также достаточно простое для запоминания и близко к настоящему правилу, полезному в практическом использовании.

В качестве более сложного примера чачтичной специализации рассмотрим класс remove_bounds<T>. Это класс содержит определение единственного члена, объявленного через typedef, type, который представляет тот же тип, что исходный параметр шаблона T, но с удаленными спецификаторами размера массива []. Это пример шаблона свойств, который выполняет преобразование типа:

template <typename T> 
struct remove_bounds
{ typedef T type; };

template <typename T, std::size_t N> 
struct remove_bounds<T[N]>
{ typedef T type; };

Целью создания шаблона remove_bounds было следующее: представьте себе обобщенный алгоритм, которому передается массив как параметр шаблона. С помощью шаблона remove_bounds можно определить исходный тип элементов массива. К примеру, remove_bounds<int[4][5]>::type будет определен как int[5]. Этот пример также показывает, что число параметров шаблона в частичной специализации не обязательно должно равняться числу параметров исходного шаблона по умолчанию. Однако, число параметров, которые заданы после имени класса, должно соответствовать числу параметров (и их типам) в исходном шаблоне по умолчанию.

Оптимизированная версия алгоритма std::copy

В качестве примера того, как могут быть использованы шаблоны классов для свойств типов, рассмотрим алгоритм стандартной библиотеки copy:

template<typename Iter1, typename Iter2>
Iter2 copy(Iter1 first, Iter1 last, Iter2 out);

Очевидно, нетрудно написать обобщенную версию алгоритма copy, которая работает для любых типов итераторов Iter1 и Iter2; однако, существуют случаи, когда алгоритм copy может быть реализован через C функцию memcpy. Для того, чтобы реализовать копирование элементов через вызов memcpy, необходимо соблюдать следующие условия:

Оба итератора Iter1 и Iter2 должны быть указателями.
Как Iter1, так и и Iter2 должны указывать на один и тот же тип - без учета квалификаторов const и volatile.
Тип, на который указывает Iter1, должен иметь тривиальный (trivial) оператор присваивания.

Под тривиальным (trivial) оператором присваивания подразумевается, что тип является либо скаляром[3], или :

Тип не имеет пользовательского оператора присваивания.
Тип не имеет членов класса, которые являются ссылками.
Все базовые классы, и все объекты - члены класса, должны иметь тривиальные операторы присваивания.

Если все эти условия соблюдены, тогда объекты типа могут копироваться с помощью функции memcpy, вместо того, чтобы использовать сгенерированный компилятором оператор присваивания. библиотека свойств типов содержит класс has_trivial_assign, такой, что выражение has_trivial_assign<T>::value получает значение true только в том случае, если T имеет тривиальный оператор присваивания. Этот класс "просто работает" для скалярных типов, но должен быть явно специализирован для классов/структур, которые имеют тривиальный оператор присваивания. Другими словами, если шаблон has_trivial_assign дает неверный ответ, то это будет "безопасный" неверный ответ - что тривиальный оператор присваивания недоступен.

Код для оптимизированной версии copy, использующей функцию memcpy при возможности, дается в листинге 1. Код начинается определением шаблонного класса copier, который получает единственный булевский параметр, и имеет статический метод do_copy, который реализует либо обощенную версию копирования (другими словами, "медленная но надежная версия"). Затем идет специализация для copier<true>: опять-таки она содержит статический метод do_copy, который в данном случае использует функцию memcpy для выполнения оптимизированного копирования.

Для того, чтобы завершить реализацию шаблонного класса, необходима такая версия copy, которая будет вызывать copier<true>::do_copy, если использование memcpy является безопасным, и в противном случае вызывает copier<false>::do_copy для выполнения "обобщенного" копирования. Это то, что делает версия в листинге 1. Чтобы понять, как работает код, взгляните на реализацию copy и разберитесь сначала с двумя определениями типов (typedefs) v1_t и v2_t. Они используют std::iterator_traits<Iter1>::value_type для того, чтобы выяснить, на какой тип указывают итераторы, и затем передают результат в другой шаблонный класс свойств типов remove_cv, который удаляет квалификаторы const и volatile самого верхнего уровня: это позволяет сравнить два типа буз учета квалификаторов const или volatile. Затем, copy объявляет перечисление с именем can_opt, которая становится параметром шаблона для copier - объявление ее здесь как константы сделано только ради удобства - эта величина может быть прямо передана в класс copier. Значение can_opt вычисляется путем проверки, что все условия справедливы:

во-первых, оба итератора указывают на один и тот же тип - используется шаблонный класс свойств типов is_same.
далее, оба итератора являются истинными указателями - используется шаблонный класс is_pointer, описанный выше.
наконец, тип, на который указывают итераторы, имеет тривиальный оператор присваивания - используется шаблонный класс has_trivial_assign.

Наконец, мы можем использовать значение can_opt как параметр шаблона copier - версия copy теперь адаптируется к передаваемым ей шаблонным параметрам и использует функцию memcpy при возможности, во всех же иных случаях используется обобщенное копирование.

Стоит ли овчинка выделки?

Часто можно слышать, что "ранняя (premature) оптимизация является корнем проблем" [4]. Так что следует спросить: не была ли наша оптимизация ранней? Результаты сравнения времени выполнения (timings) нашей версии алгоритма copy с обычной реализацией copy показаны в таблице 1.

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

Если Вы используете правильный алгоритм для выполнения работы с самого начала, тогда оптимизация не потребуется; в некоторых случаях memcpy является как раз правильным алгоритмом.
Если компонент планируется повторно использовать множеством людей, тогда оптимизации могут быть полезными там, где они бессмысленны для единичных случаев - другими словами, вероятность того, что оптимизация будет необходима, значительно повышается. К примеру, важно добиться высокой оценки реализации хранилища данных; в данном случае не имеет смысла стандартизировать алгоритм, если пользователи не станут им пользоваться по той причине, что существуют более эффективные, лучше оптимизированные версии.

Таблица 1: Время, необходимое для копирования 1000 элементов с использованием copy<const T*, T*> (в микросекундах)

Версия	Тип T	Время
"оптимизированная" версия copy	char	0.99
обычная версия copy	char	8.07
"оптимизированная" версия copy	int	2.52
обычная версия copy	int	8.02

Версия std::pair для хранения ссылок

Оптимизированная версия copy показывает, как свойства типов могут быть использованы для принятия решений по оптимизации на этапе компиляции. Другим важным применением свойств типов является возможность компиляции кода, который в противном случае не мог бы быть скомпилирован без использования большого количества частичных специализаций. Это становится возможным благодаря передаче частичной специализации в классы свойств типов. Наш пример такой формы применения это реализация класса pair, который может хранить ссылки [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) { }
};

В текущей версии класс pair не может хранить ссылки, потому что конструктор должен будет получать ссылку на ссылку, что в настоящее время невозможно [7]. Рассмотрим, какими должны быть параметры шаблона для того, чтобы позволить классу pair хранить не-ссылочные типы, ссылки и константные ссылки:

тип T1	тип аргумента для конструктора инициализирования
T	const T &
T &	T &
const T &	const T &

Небольшая фамильярность с классами свойств типов позволяет нам сконструировать единое отображение, позволяющее определить тип параметра из типа хранимого класса. Классы свойств типов предоставляют преобразование add_reference, которое добавляет ссылку к типу, эсли это не ссылка.

тип T1	тип const T1	тип add_reference<const T1>::type
T	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, однако это потребовало бы три частичные специализации плюс исходный шаблон. Свойства типов позволяют определить единственный исходный шаблон, который самонастраивается таким образом, чтобы соответствовать этим частичным специализациям, вместо применения грубой силы для написания всех трех специализаций. Применение свойств типов таким способом позволяет программисту передавать частичную специализацию классам свойств типов, что приводит в итоге к коду, который проще сопровождать и понимать.

Заключение

Мы надеемся, что в данной статье нам удалось объяснить, что же такое свойства типов. Более законченный список доступных классов можно найти в документации BOOS C++ вместе с другими примерами использования. Шаблоны делают возможным использовать преимущества повторного использования кода, которое дает обобщенное программирование; к счастью данная статья показывает, что обобщенное программирование вовсе не должно сводиться к наименьшему общему делителю, и что шаблоны могут быть и оптимальными и обобщенными (generic).

Благодарности

Авторы хотели бы поблагодарить Beman Dawes и Howard Hinnant за их полезные комментарии во время подготовки данной статьи.

Литература

Nathan C. Myers, C++ Report, June 1995.
The type traits library is based upon contributions by Steve Cleary, Beman Dawes, Howard Hinnant and John Maddock: it can be found at www.boost.org.
A scalar type is an arithmetic type (i.e. a built-in integer or floating point type), an enumeration type, a pointer, a pointer to member, or a const- or volatile-qualified version of one of these types.
This quote is from Donald Knuth, ACM Computing Surveys, December 1974, pg 268.
The test code is available as part of the boost utility library (see algo_opt_examples.cpp), the code was compiled with gcc 2.95 with all optimisations turned on, tests were conducted on a 400MHz Pentium II machine running Microsoft Windows 98.
John Maddock and Howard Hinnant have submitted a "compressed_pair" library to Boost, which uses a technique similar to the one described here to hold references. Their pair also uses type traits to determine if any of the types are empty, and will derive instead of contain to conserve space -- hence the name "compressed".
This is actually an issue with the C++ Core Language Working Group (issue #106), submitted by Bjarne Stroustrup. The tentative resolution is to allow a "reference to a reference to T" to mean the same thing as a "reference to T", but only in template instantiation, in a method similar to multiple cv-qualifiers.
For those of you who are wondering why this shouldn't be const-qualified, remember that references are always implicitly constant (for example, you can't re-assign a reference). Remember also that "const T &" is something completely different. For this reason, cv-qualifiers on template type arguments that are references are ignored.

Listing 1

namespace detail{

template <bool b>
struct copier
{
   template<typename I1, typename I2>
   static I2 do_copy(I1 first, 
                     I1 last, I2 out);
};

template <bool b>
template<typename I1, typename I2>
I2 copier<b>::do_copy(I1 first, 
                      I1 last, 
                      I2 out)
{
   while(first != last)
   {
      *out = *first;
      ++out;
      ++first;
   }
   return out;
}

template <>
struct copier<true>
{
   template<typename I1, typename I2>
   static I2* do_copy(I1* first, I1* last, I2* out)
   {
      memcpy(out, first, (last-first)*sizeof(I2));
      return out+(last-first);
   }
};

}

template<typename I1, typename I2>
inline I2 copy(I1 first, I1 last, I2 out)
{
   typedef typename 
    boost::remove_cv<
     typename std::iterator_traits<I1>
      ::value_type>::type v1_t;

   typedef typename 
    boost::remove_cv<
     typename std::iterator_traits<I2>
      ::value_type>::type v2_t;

   enum{ can_opt = 
      boost::is_same<v1_t, v2_t>::value
      && boost::is_pointer<I1>::value
      && boost::is_pointer<I2>::value
      && boost::
      has_trivial_assign<v1_t>::value 
   };

   return detail::copier<can_opt>::
      do_copy(first, last, out);
}

последняя правка: 07.05.2005

библиотека BOOST C++ http://www.boost.org
перевод Elijah Koziev www.solarix.ru