Следует ли предпочитать алгоритмы STL над ручными свертками?

Ответ 1

Это зависит от:

• Требуется ли высокая производительность.
• Читаемость цикла
• Является ли алгоритм сложным

Если цикл не является узким местом, и алгоритм прост (например, for_each), то для текущего стандарта С++ я предпочел бы ручную петлю для удобочитаемости. (Локализация логики является ключом.)

Однако теперь, когда С++ 0x/С++ 11 поддерживается некоторыми основными компиляторами, я бы сказал, используя алгоритмы STL, потому что теперь они позволяют лямбда-выражения - и, следовательно, локальность логики.

Ответ 2

Я собираюсь пойти против зерна здесь и заявить, что использование алгоритмов STL с функторами делает код намного легче понять и поддерживать, но вы должны сделать это правильно. Вы должны уделять больше внимания читаемости и ясности. В частности, вы должны получить право именования. Но когда вы это сделаете, вы можете получить более чистый, понятный код и смену парадигмы в более мощные методы кодирования.

Давайте возьмем пример. Здесь у нас есть группа детей, и мы хотим установить их "Foo Count" на некоторое значение. Стандартный метод for-loop, итератор:

for (vector<Child>::iterator iter = children.begin();
    iter != children.end();
    ++iter)
{
    iter->setFooCount(n);
}

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

for_each(children.begin(), children.end(), SetFooCount(n));

Ничего себе, это точно говорит о том, что нам нужно. Вам не нужно это выяснять; вы сразу же знаете, что его настройка "Foo Count" каждого ребенка. (Было бы еще понятнее, если бы нам не понадобилась ошибка .begin()/.end(), но вы не можете иметь все, и они не проконсультировались со мной при создании STL.)

Конечно, вам нужно определить этот магический функтор SetFooCount, но его определение довольно условно:

class SetFooCount
{
public:
    SetFooCount(int n) : fooCount(n) {}

    void operator () (Child& child)
    {
        child.setFooCount(fooCount);
    }

private:
    int fooCount;
};

В целом его больше кода, и вам нужно посмотреть другое место, чтобы узнать, что именно делает SetFooCount. Но поскольку мы назвали это хорошо, 99% времени мы не должны смотреть на код для SetFooCount. Мы предполагаем, что он делает то, что он говорит, и нам нужно только посмотреть на строку for_each.

Мне действительно нравится, что использование алгоритмов приводит к сдвигу парадигмы. Вместо того, чтобы рассматривать список как совокупность объектов и делать вещи для каждого элемента списка, вы считаете список как сущность первого класса, и вы работаете непосредственно с самим списком. Цикл for-loop выполняет итерацию по списку, вызывая функцию-член для каждого элемента, чтобы установить Foo Count. Вместо этого я выполняю одну команду, которая устанавливает Foo Count каждого элемента в списке. Его тонкий, но когда вы смотрите на лес вместо деревьев, вы получаете больше энергии.

Итак, с небольшим мыслей и тщательным наименованием, мы можем использовать алгоритмы STL, чтобы сделать более чистый, понятный код и начать думать на менее гранулированном уровне.

Ответ 3

std::foreach - это код, который заставлял меня проклинать STL несколько лет назад.

Я не могу сказать, если это лучше, но мне больше нравится иметь код моего цикла под преамбулой цикла. Для меня это сильное требование . И конструктор std::foreach не позволит мне этого (как ни странно, для явных версий Java или С# для меня это классно, насколько мне известно... Поэтому я думаю, это подтверждает, что для меня местность тела цикла очень важно).

Таким образом, я буду использовать foreach только в том случае, если есть только уже читаемый/понятный алгоритм, который можно использовать с ним. Если нет, нет, я не буду. Но, по-моему, это вопрос вкуса, поскольку я, возможно, стараюсь понять и научиться разбирать все это...

Обратите внимание, что люди с повышением, по-видимому, чувствовали себя одинаково, поскольку они написали BOOST_FOREACH:

#include <string>
#include <iostream>
#include <boost/foreach.hpp>

int main()
{
    std::string hello( "Hello, world!" );

    BOOST_FOREACH( char ch, hello )
    {
        std::cout << ch;
    }

    return 0;
}

Смотрите: http://www.boost.org/doc/libs/1_35_0/doc/html/foreach.html

Ответ 4

Это действительно единственное, что ошибался Скотт Мейерс.

Если есть реальный алгоритм, который соответствует тому, что вам нужно сделать, тогда, конечно, используйте алгоритм.

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

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

Как уже упоминалось, все это изменится, когда лямбда-выражения станут гражданами первого класса.

Ответ 5

Цикл for является обязательным, алгоритмы являются декларативными. Когда вы пишете std::max_element, его очевидное, что вам нужно, когда вы используете цикл для достижения того же самого, это не обязательно так.

Алгоритмы также могут иметь небольшое преимущество производительности. Например, при перемещении std::deque, специализированный алгоритм может избежать лишнего проверки того, будет ли данное приращение перемещать указатель на границу блока.

Однако сложные выражения функтора быстро отображают вызовы алгоритмов, которые нечитабельны. Если явный цикл является более читаемым, используйте его. Если вызов алгоритма может быть выражен без десятиэтажных выражений привязки, во что бы то ни стало от него предпочтение. Читаемость более важна, чем производительность здесь, потому что такая оптимизация - это то, что Кнут так хорошо приписывает Хоару; вы сможете использовать другую конструкцию без проблем, как только осознаете ее узкое место.

Ответ 6

Это зависит, если алгоритм не принимает функтора, тогда всегда используйте версию алгоритма std. Это проще для вас, чтобы написать и сделать более понятным.

Для алгоритмов, которые принимают функторы, обычно нет, до использования С++ 0x lambdas. Если функтор мал и алгоритм является сложным (большинство из них не являются), то может быть лучше использовать алгоритм std.

Ответ 7

Я большой поклонник алгоритмов STL в принципе, но на практике это просто слишком громоздко. К тому времени, когда вы определите классы функтора/предиката, две линии для цикла могут превратиться в 40 + строк кода, которые неожиданно 10 раз сложнее понять.

К счастью, в С++ 0x все проще получить тонну, используя лямбда-функции, auto и новый синтаксис for. Оформить заказ Обзор С++ 0x в Википедии.

Ответ 8

Я бы не использовал для этого жесткое и быстрое правило. Есть много факторов, которые следует учитывать, например, часто вы выполняете определенную операцию в своем коде, это всего лишь цикл или "фактический" алгоритм, зависит ли алгоритм от большого контекста, который вам нужно передать вашей функции?

Например, я бы не добавил что-то вроде

for (int i = 0; i < some_vector.size(); i++)
    if (some_vector[i] == NULL) some_other_vector[i]++;

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

Существует множество других примеров, где использование алгоритмов STL имеет большой смысл, но вам нужно принимать индивидуальные решения.

Ответ 9

Я думаю, что алгоритм алгоритма STL является субоптимальным, и его следует избегать, потому что использование инструментария STL напрямую (для алгоритмов) может дать очень небольшой прирост производительности, но, безусловно, будет стоить удобочитаемость, ремонтопригодность и даже бит writeability, когда вы изучаете, как использовать инструменты.

Насколько эффективнее стандарт для цикла над вектором:

int weighted_sum = 0;
for (int i = 0; i < a_vector.size(); ++i) {
  weighted_sum += (i + 1) * a_vector[i];  // Just writing something a little nontrivial.
}

чем использовать конструкцию for_each или пытаться вставить это в вызов для накопления?

Вы можете утверждать, что процесс итерации менее эффективен, но для каждого из них каждый также вводит вызов функции на каждом шаге (который можно смягчить, пытаясь встроить функцию, но помните, что "inline" - это только предложение компилятор - он может его игнорировать).

В любом случае разница небольшая. По моему опыту, более 90% кода, который вы пишете, не критичны по производительности, но критически важны для кодера. Сохраняя вашу петлю STL буквально встроенной, она очень читаема. Существует меньше возможностей для поездки, для себя или будущих сопровождающих. Если это в вашем руководстве по стилю, то вы сохраняете некоторое время обучения для ваших кодеров (признайте это, научившись правильно использовать STL, в первый раз задействованы несколько моментов). Этот последний бит - это то, что я подразумеваю под ценой записи.

Конечно, есть некоторые особые случаи - например, вы действительно можете захотеть, чтобы функция for_each разделялась на повторное использование в нескольких других местах. Или это может быть один из тех немногих высокопроизводительных критических разделов. Но это особые случаи - исключения, а не правило.

Ответ 10

IMO, следует избегать множества стандартных библиотечных алгоритмов, таких как std:: for_each, в основном из-за недостатка лямбда-вопросов, упомянутых другими, но также и потому, что существует такая вещь, как неуместное скрытие деталей.

Конечно, скрытие деталей в функциях и классах является частью абстракции, и вообще абстракция библиотеки лучше, чем изобретать колесо. Но ключевой навык с абстракцией - это знать, когда это делать - и когда этого не делать. Чрезмерная абстракция может повредить читаемость, ремонтопригодность и т.д. Хорошее суждение приходит с опытом, а не из негибких правил - хотя вы должны изучать правила, прежде чем научиться их нарушать, конечно.

OTOH, стоит подумать о том, что многие программисты используют С++ (и до этого C, Pascal и т.д.) в течение длительного времени. Старые привычки умирают тяжело, и есть эта вещь, называемая когнитивный диссонанс, который часто приводит к оправданиям и рационализации. Не переходите к выводам, хотя - по крайней мере, так же вероятно, что ребята из стандартов виновны в диссонансе после принятия решения.

Ответ 11

Я думаю, что большой фактор - уровень комфорта для разработчиков.

Возможно, верно, что использование transform или for_each - это правильная вещь, но это не более эффективно, а рукописные петли не являются по своей сути опасными. Если разработчику понадобится полчаса, чтобы написать простой цикл, вместо половины дня, чтобы получить синтаксис для transform или for_each, и переместите предоставленный код в объект функции или функции. И тогда другим разработчикам нужно будет знать, что происходит.

Новый разработчик, вероятно, будет лучше всего использовать, научившись использовать transform и for_each, а не ручные манипуляции, поскольку он сможет использовать их последовательно без ошибок. Для остальных из нас, для которых пишущие петли являются второй натурой, лучше всего придерживаться того, что мы знаем, и более подробно ознакомиться с алгоритмами в наше свободное время.

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

Ответ 12

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

Оказывается, что простые необработанные циклы могут быть значительно быстрее, чем их альтернативы на основе алгоритмов, даже с оптимизацией -O3. Я лично весьма обеспокоен этим фактом, потому что у нас есть инструменты статического анализа кода, такие как cppcheck безответственно поощряющие использование алгоритмов std:: вместо сырых циклов, не говоря уже о различных других онлайн-статьях, ошибочно хвалящих использование алгоритмов STL.

Я наткнулся на эту ошибку после проведения статического анализа моего проекта с CppCheck. Он сообщил мне следующую ошибку стиля в моем коде:

(style) Consider using std::find_if algorithm instead of a raw loop. [useStlAlgorithm]

Моя оригинальная функция была такой:

INSTANCE *MANAGER::instance_find(long long id) const {
    size_t iHash = static_cast<size_t>(id) % MAX_KEY_HASH;
    std::vector<INSTANCE *> &row = instances[iHash];

    // CppCheck recommends replacing this with an algorithm:
    for (INSTANCE *ins : row) {
        if (ins && ins->id == id) return ins;
    }

    return (inactive_instances.count(id) > 0 ?
            inactive_instances.at(id) : nullptr);
}

Приведенный выше код должен был работать в течение 130 мс, чтобы найти ~ 57 миллионов экземпляров.

Затем я заменил его предложенным алгоритмом std::find_if:

INSTANCE *MANAGER::instance_find(long long id) const {
    size_t iHash = static_cast<size_t>(id) % MAX_KEY_HASH;
    std::vector<INSTANCE *> &row = instances[iHash];

    auto found = std::find_if(row.begin(), row.end(),
        [&](INSTANCE *ins) {
            return ins && ins->id == id;
        }
    );

    if (found != row.end()) return *found;

    return (inactive_instances.count(id) > 0 ?
            inactive_instances.at(id) : nullptr);
}

И снова проведя тот же тест, лучший результат, который я смог получить, составил 187 мс, чтобы найти эти 57 миллионов экземпляров. Так что даже с оптимизацией -O3 алгоритм STL замедлит ваш код на 40%. Это довольно большое дело для функций, которые должны называться A LOT.

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

INSTANCE *MANAGER::instance_find(long long id) const {
    size_t iHash = static_cast<size_t>(id) % MAX_KEY_HASH;
    std::vector<INSTANCE *> &row = instances[iHash];

    INSTANCE *found = nullptr;
    for (INSTANCE *ins : row) {
        if (ins && ins->id == id) found = ins;
    }

    if (found) return found;

    return (inactive_instances.count(id) > 0 ?
            inactive_instances.at(id) : nullptr);
}

При выполнении приведенного выше кода лучший результат, который мне удалось получить, составил 164 мс, чтобы найти эти 57 миллионов экземпляров. Как вы можете видеть, алгоритм STL все еще медленнее примерно на 14%, чем неработающая версия необработанного цикла.

В разработке игр (где я нахожусь), на самом деле нет оправдания для такого поведения, и мне грустно видеть безрассудно продвигаемые алгоритмы STL в Интернете. Над ними действительно должна быть большая красная метка, которая часто делает ваш код медленнее, не принося никакой практической пользы.

Что касается инструментов статического анализа кода, таких как CppCheck, я надеюсь, что эта информация в конечном итоге дойдет до них, и они что-то с этим сделают. Инструмент статического анализа кода не должен навязывать пользователям религиозный уклон его создателей. Кто хотел бы получать предупреждения стиля для использования пробелов вместо вкладок? Никто. То же самое относится и к алгоритмам STL.