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