Шаблоны функций и функциональные объекты

Шаблон класса обобщает данные, шаблон функции – алгоритм. Из этого выросла вся стандартная библиотека алгоритмов: sort, find, accumulate работают с любыми типами и любыми контейнерами, не зная о них ничего.

Синтаксис и вывод типов

template <typename T>
const T& Max(const T& a, const T& b) {
    return a > b ? a : b;
}

std::cout << Max(3, 7);           // T = int, выведен из аргументов
std::cout << Max(3.5, 1.2);       // T = double
std::cout << Max<double>(3, 1.2); // T задан явно

Главное отличие от шаблона класса: аргументы можно не указывать – компилятор выведет их из типов фактических параметров.

Вывод работает по точному совпадению и неявных преобразований не делает:

Max(1, 2.0);          // ошибка: T выводится и как int, и как double
Max<double>(1, 2.0);  // ок: тип задан, аргументы преобразуются

Если типы разные по существу, объявляют два параметра:

template <typename T, typename U>
void CopyN(T* dst, const U* src, size_t count) {
    for (size_t i = 0; i < count; ++i) {
        dst[i] = src[i];      // преобразование U → T выполнит присваивание
    }
}

int ints[] = {1, 2, 3, 4};
double doubles[4] = {};
CopyN(doubles, ints, 4);      // T = double, U = int

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

Перегрузка шаблонов

Шаблоны перегружаются между собой и с обычными функциями:

template <typename T>
void Print(const T& value);              // общий случай

template <typename T>
void Print(const std::vector<T>& v);     // более специфичный

void Print(const std::string& s);        // обычная функция

Правило разрешения: обычная функция побеждает шаблон при равном качестве совпадения, а среди шаблонов выбирается более специализированный.

Print(std::string("hi"));           // обычная функция
Print(std::vector<int>{1, 2});      // второй шаблон: он специфичнее
Print(42);                          // первый шаблон

Функциональные объекты

Алгоритму часто нужно передать не данные, а поведение – например, критерий сравнения. В C++ это делается через объект с перегруженным operator():

struct Less {
    bool operator()(int a, int b) const { return a < b; }
};

Less less;
if (less(10, 20)) { /* ... */ }     // выглядит как вызов функции

Заменим объект на функцию с тем же именем – место вызова не изменится:

bool less(int a, int b) { return a < b; }

if (less(10, 20)) { /* ... */ }     // ни строчки не поменялось

Имена одинаковые, а типы разные: у первого – класс Less, у второго – указатель на функцию. Шаблон это различие стирает:

template <typename T, typename Compare>
void Sort(T* first, T* last, Compare comp);

int m[10] = {5, 3, 9, 1, 7, 2, 8, 0, 6, 4};

Sort(m, m + 10, Less());     // функтор
Sort(m, m + 10, less);       // функция

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

Функтор обычно быстрее указателя на функцию. Его тип известен на этапе компиляции, поэтому operator() встраивается прямо в цикл; вызов по указателю встроить труднее. Разница между std::sort и qsort из C – в основном именно эта.

Функтор может хранить состояние, чего функция не умеет:

struct GreaterThan {
    explicit GreaterThan(int bound) : bound_(bound) {}

    bool operator()(int value) const { return value > bound_; }

private:
    int bound_;
};

auto count = std::count_if(v.begin(), v.end(), GreaterThan(10));

Лямбда-выражения

С C++11 функтор чаще всего не пишут руками – его порождает компилятор:

int bound = 10;

auto count = std::count_if(v.begin(), v.end(),
                           [bound](int value) { return value > bound; });

Лямбда – ровно тот же безымянный класс с operator(), а [bound] перечисляет, что попадёт в его поля. Захват [&] берёт по ссылке, [=] – по значению, [] не захватывает ничего.

Лямбда с захватом по ссылке не должна пережить то, что захватила. Сохранили её в поле класса или вернули из функции – и ссылка на локальную переменную становится висячей ровно так же, как обычная. Для лямбды, которая живёт дольше выражения, захватывайте по значению.

Обобщение по контейнеру

Алгоритмы стандартной библиотеки не знают о контейнерах вообще – они работают с парой итераторов:

template <typename Iterator, typename Compare>
Iterator MinElement(Iterator first, Iterator last, Compare comp) {
    if (first == last) {
        return last;
    }

    Iterator best = first;
    for (Iterator it = ++first; it != last; ++it) {
        if (comp(*it, *best)) {
            best = it;
        }
    }

    return best;
}

Требования к Iterator – только ++, *, !=. Им удовлетворяет и обычный указатель, и итератор std::vector, и итератор std::list. Одна функция – все контейнеры.

Наш класс Array тоже подойдёт, если у него будут begin() и end():

template <typename T>
class Array {
public:
    T* begin() { return data_; }
    T* end()   { return data_ + size_; }

    const T* begin() const { return data_; }
    const T* end()   const { return data_ + size_; }
};

Array<int> a(10, 0);
std::sort(a.begin(), a.end());
for (int value : a) { /* range-for тоже заработает */ }

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