Источник: habrahabr
kibergus
Копировать элементы из одного контейнера в другой? Нет ничего проще, универсальный алгоритм помещается в 5 строк:
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) {
while(first != last) *result++ = *first++;
return result;
}
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// Компилятор всегда проигнорирует этот шаблон
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;
}
В реальной библиотеке все немного сложнее, потому что стандартом зафиксировано, что 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);
}
Размер генерируемого кода
Обратите внимание, что шаблон, приведенный в начале статьи, для каждого нового типа будет генерировать полностью новый код. Второй же шаблон вырождается в одно вычитание и одно сложение указателей, а реализация memmove общая для всех типов. То есть помимо ускорения программы, уменьшается её размер. Аналогичные трюки могут применяться в контейнерах: части, не зависящие от хранимого типа выносятся из шаблона и используют общую реализацию. Например, в реализации std::list шаблонная структура, хранящая данные, не содержит ничего кроме самих данных. Ссылки на соседей и операции над ними реализованы в базовом не шаблонном классе, от которого она наследуется.Используйте библиотечные функции
Мораль этой статьи проста: используйте алгоритмы, предоставляемые стандартной библиотекой как можно чаще. Это делает ваши программы эффективнее, понятнее и гибче.Эффективнее потому, что разработчики стандартных библиотек могут применять оптимизации, которые вы не можете позволить себе в обычном коде. Вы же не готовы писать и поддерживать несколько реализаций копирования объектов под десяток платформ? У прикладного программиста на это нет времени.
Понятнее потому, что вы можете писать короткий высокоуровневый код, оперируя примитивами, знакомыми вашим коллегам.
Гибче потому, что вам не надо делать преждевременных оптимизаций и потому, что вы используете более общие алгоритмы, чем вы бы написали сами.