C++ стиль написания алгоритмов

В очередной раз не знаю с чего начать пост, поэтому скажу прямо. Мне хочеться рассказать о правилах написания C++ кода. Нет, речь пойдет не о Style Guide'ах, а о «правильном» написании некоторых вещей.

К сожалению, сложно объяснить, что я имею ввиду под словом "правильный". Среди python программистов широко распространено слово pythonic, которое означает, что код написан в стиле python (со всеми достоинствами этого языка), а не, например, в стиле процедурных языков. То есть, это означает, что для прохода по контейнерам используется цикл for each, а не цикл с доступом по индексу. Вот под словом «правильный» я понимаю именно такой подход — подход написания кода в стиле C++.

Для примера рассмотрим уже заезженную функцию бинарного поиска с рекурсивным вызовом (не смотря на то, что бинарный поиск уже реализован в stl). К примеру, перед программистом стала задача проверить вхождение некоторого элемента в упорядоченный массив. Первое, что придет в голову начинающему программисту — это решить проблему в лоб и написать что-то типа такого:

bool binary_search(const int* arr, int size, int key)
{
    // element not found
    if (size == 0)
        return false;
    // check for the desired element
    int half = size / 2;
    if (key == arr[half])
        return true;
    // recursive call
    if (key < arr[half])
        return binary_search(arr, half, key);
    return binary_search(arr + half + 1, size - half - 1, key);
}

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

Более продвинутый новичок вспомнит о шаблонах и напишет следующий код:

template<class T>
    bool binary_search(const T* arr, int size, T key)
    {
        // element not found
        if (size == 0)
            return false;
        // check for the desired element
        int half = size / 2;
        if (key == arr[half])
            return true;
        // recursive call
        if (key < arr[half])
            return binary_search(arr, half, key);
        return binary_search(arr + half + 1, size - half - 1, key);
    }

Ну что же, уже неплохою Во всяком случае, функция будет работать для разнообразных массивов, элементами которого служат типы с определенными операторами сравнения == и <.

Часто подобная реализации пишется не для массива, а для некоторого контейнера: программист считает себя крутым, передает контейнер и ему уже не нужно передавать размер. Несмотря на то, что тип контейнера будет шаблонным, зачастую в коде все равно существует привязка к типу контейнера. Это либо индексный доступ, либо использование push_front/push_back/etc. Специфичных функций-членов класса у каждого контейнера хватает.

Но такой подход я не назвал бы правильным с точки зрения C++. Этот язык куда более гибкий, мощный и предоставляет широкие средства для написания кода. Поэтому, подобные алгоритмы (алгоритмы, работающие с некоторыми диапазонами: массивы, контейнеры) лучше реализовывать в стиле STL: с аргументами в виде итераторов, задающих последовательность. Выглядеть это будет примерно так:

template<class IT, class KEY>
    bool binary_search(IT first, IT last, KEY key)
    {
        // element not found
        if (first == last)
            return false;
        // check for the desired element
        IT half = first;
        std::advance(half, std::distance(first, last) / 2);
        if (key == *half)
            return true;
        // recursive call
        if (key < *half)
            return binary_search(first, half, key);
        return binary_search(++half, last, key);
    }

Казалось бы - всё отлично! Функция работает как для массива, так и для вектора, листа, множества и других контейнеров :) Но, как известно, нет предела совершенству. Данную функцию можно усовершенствовать тем, что передавать предикаты. Например, предикат упорядочивания - сравнивающий два элемента. Таким образом, бинарный поиск будет применим к последовательностям упорядоченным не по оператору <, а по некоторому предикату (что в реальных проектах встречается весьма не редко). Но и текущего варианта будет вполне достаточно для того, чтобы считать код хорошим и правильным с точки зрения философии C++. :)

Что отсюда нужно вынести? А нужно вынести следующее:

  • если алгоритм обобщенный, писать для него шаблон;
  • последовательность задавать итераторами, а не передачей контейнера или массива;
  • последовательность должна задаваться началом и элементом, следующим за последним [first, last);
  • использовать функции STL для работы с итераторами, дабы обеспечить максимальную переносимость алгоритма (например advance/distance);
  • вообще максимально возможно использовать STL, а не придумывать велосипеды!