Навигация
Главная »  Новости 

Как правильно скопировать массив и при чем тут SFINAE


Источник: habrahabr
kibergus
Копировать элементы из одного контейнера в другой? Нет ничего проще, универсальный алгоритм помещается в 5 строк:
template OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) { while(first != last) *result++ = *first++; return result; } 
Возможно вы узнали реализацию std::copy с cplusplus.com. Почему же реализация std::copy из GNU STL занимает 139 строк? Давайте разберемся.
STL - это самая базовая библиотека, используемая всеми нормальными программами на C++. Поэтому она должна предоставлять максимально эффективные реализации алгоритмов. Причем эффективные во многих смыслах:
  • Скорость выполнения
  • Размер генерируемого компилятором кода
  • Потребление памяти
  • Скорость компиляции
Скорость выполненияКод можно сделать более быстрым, если учитывать особенности типов, которыми инстанциируется шаблон. Например, если тип имеет тривиальный конструктор копирования, его можно копировать побайтно. И если объекты лежат в непрерывной области памяти, вместо многократного вызова конструктора можно использовать старую добрую C функцию memmove, которая может задействовать векторные команды процессора, копирующие данные особенно быстро. Обратите внимание, что реализация std::copy не может использовать memcpy, так как memcpy работает только на не перекрывающихся областях памяти.
Таким образом, мы хотим написать две реализации std::copy: одну быструю, для тривиально копируемых типов, а другую универсальную, для всех остальных. SFINAEИ тут на помощь приходит приём, известный как "substitution failure is not an error". Если при подстановке шаблонных параметров получается некорректное выражение, это не является ошибкой. Компилятор должен проигнорировать шаблон и продолжить поиск. Важно, что в случае шаблонной функции некорректное выражение должно обнаружиться не в теле функции, когда конкретный шаблон уже выбран и продолжать поиск некуда, а в её прототипе. Самый простой способ это сделать - использовать std::enable_if.

std::enable_if

Сам по себе enable_if очень прост. Это шаблон от интегральной константы и типа. Если константа истинна, то он содержит объявление вложенного типа с именем type, в противном случае он пуст.
    // Define a nested type if some predicate holds. // Primary template. /// enable_if template struct enable_if { };  // Partial specialization for true. template struct enable_if { typedef _Tp type; }; 
Тип
std::enable_if<условие, Type>::type
будет определен и иметь тип Type, но только если условие истинно. Используют его вот так:
// Компилятор всегда проигнорирует этот шаблон template std::enable_if::type get_t() {return T();}  // А этот будет инстанциирован template std::enable_if::type get_t() {return T();} 

type traits

Чтобы все описанное выше имело смысл, нужно иметь константы, зависящие от типа. Они называются type traits. Это шаблонные структуры, у которых есть статическое константное публичное свойство value, принимающее значение true или false, в зависимости от типа, которым инстанциирован шаблон. Некоторые из них описаны с помощью частичной специализации шаблона, некоторые реализуются самим компилятором, а некоторые построены как выражения над другими type traits. Специальная реализация std::copyДобавим перед универсальной реализацией вот такую:
template // В gcc 4.5 нет std::is_trivially_copiable, поэтому используется более сильное условие //inline typename std::enable_if::value, T*>::type inline typename std::enable_if::value, T*>::type copy(T* first, T* last, T* result) {  const ptrdiff_t num = last - first; memmove(result, first, sizeof(T) * num); return result + num; } 
Если copy будет вызван с тремя указателями на тривиально копируемый тип, то компилятор применит эту оптимизированную реализацию. В противном случае, этот шаблон будет проигнорирован и будет использована универсальная версия.
В реальной библиотеке все немного сложнее, потому что стандартом зафиксировано, что std::copy имеет два шаблонных параметра. Если программист явно их укажет, то все равно надо выбрать оптимизированный вариант. Поэтому различные реализации описаны под служебными именами, а в самом std::move находится код, выбирающий наиболее подходящую реализацию. Вот значительно упрощенный вариант:
#include  #include   // Внимание: этот файл собирается только C++11. // В C++03 нет необходимых type_traits (по крайней мере в публичном интерфейсе)  // Вспомогателльный класс с двумя частичными специализациями. // Если is_simple, то применяется memmove, а итераторы считаются указателями. // В противном случае применяется общий алгоритм. template struct __do_copy; // Обратите внимание на название, начинающееся с _. Такие названия зарезервированы // стандартом для внутреннего использования компилятором и стандартной библиотекой. // Никогда не используйте такие названия с своих программах, в том числе для приватных // членов класса. Тут оно использовано так как приводится упрощенная реализация std::copy  template<> struct __do_copy { // Реализация для тривиально копируемых типов // Эта функция для внутреннего пользования, поэтому не содержит никаких проверок // что memmove действительно применим. template static inline OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result) { typedef typename std::iterator_traits::value_type ValueType; const std::ptrdiff_t num = last - first; memmove(result, first, sizeof(ValueType) * num); return result + num; } };      template<> struct __do_copy { // Универсальная реализация template static inline OutputIterator do_copy(InputIterator first, InputIterator last, OutputIterator result) { while(first != last) *result++ = *first++; return result; } };  // Вспомогательная trait структура для сравнения равенства типов // В публичном интерфейсе STL её нет template struct are_same : public std::false_type {}; template struct are_same: public std::true_type {};  template inline InputIterator copy( InputIterator first, InputIterator last, OutputIterator result) { // Без typename копмилятор не может понять, является value_type типом // или, скажем, свойством. Они синтаксически неразличимы. typedef typename std::iterator_traits::value_type ValueTypeI; typedef typename std::iterator_traits::value_type ValueTypeO;  const bool is_simple = ( std::is_trivial::value && std::is_pointer::value && std::is_pointer::value && are_same::value);  // Выбираем подходящую реализацию return __do_copy::do_copy(first, last, result); } 
Кроме того, в GNU STL применяется еще одна оптимизация: для итераторов случайного доступа применяется цикл for с вычислением количества итераций. Компилятор умеет разворачивать такие циклы, увеличивая быстродействие программы. Размер генерируемого кодаОбратите внимание, что шаблон, приведенный в начале статьи, для каждого нового типа будет генерировать полностью новый код. Второй же шаблон вырождается в одно вычитание и одно сложение указателей, а реализация memmove общая для всех типов. То есть помимо ускорения программы, уменьшается её размер. Аналогичные трюки могут применяться в контейнерах: части, не зависящие от хранимого типа выносятся из шаблона и используют общую реализацию. Например, в реализации std::list шаблонная структура, хранящая данные, не содержит ничего кроме самих данных. Ссылки на соседей и операции над ними реализованы в базовом не шаблонном классе, от которого она наследуется. Используйте библиотечные функцииМораль этой статьи проста: используйте алгоритмы, предоставляемые стандартной библиотекой как можно чаще. Это делает ваши программы эффективнее, понятнее и гибче
Эффективнее потому, что разработчики стандартных библиотек могут применять оптимизации, которые вы не можете позволить себе в обычном коде. Вы же не готовы писать и поддерживать несколько реализаций копирования объектов под десяток платформ? У прикладного программиста на это нет времени.
Понятнее потому, что вы можете писать короткий высокоуровневый код, оперируя примитивами, знакомыми вашим коллегам.
Гибче потому, что вам не надо делать преждевременных оптимизаций и потому, что вы используете более общие алгоритмы, чем вы бы написали сами. P.S.Обратите внимание, что std::copy знает, что result не находится между start и finish, но использует функцию memmove, которая вынуждена это проверить и выбрать направление копирования (от начала к концу или от конца к началу). Можно было сделать чуть более оптимальную реализацию, но тогда бы разработчики STL должны были бы поддерживать специальные релизации под каждую из поддерживаемых архитектур. На это уже тратят свое время разработчики glibc. Дублировать эту работу никому не надо.

 

 Создание окна мастера (исходники).
 Партнерство с компьютером. Человеко-машинные целеустремленные системы..
 Cisco меняет требования для письменных экзаменов.
 Порядок моделирования(SADT).
 Продукт Business Objects объявлен финалистом конкурса 2007 г. на присуждение престижной награды.


Главная »  Новости 

© 2017 Team.Furia.Ru.
Частичное копирование материалов разрешено.