Различие в поведении C++ между оператором if, устанавливающим условие в true, и / или условием в цикле

Question

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

//original form
bool addedFacts = false;
for (X x: xs) {
    addedFacts = addedFacts || set.insert(x).second;
}
//modified form
bool addedFacts = false;
for (X x: xs) {
    if (set.insert(x).second) {
        addedFacts = true;
    }
}

Мне эти две структуры кода кажутся логически эквивалентными. Есть ли причина, почему кто-то выполняет правильно, а другой - неправильно / неэффективно? Вот наглядный пример возникшей проблемы:

#include <iostream>
#include <set>
#include <vector>

using std::set;
using std::vector;
using std::cout;
using std::endl;

const int CAP = 100;

class Rule {
public:
    int factor;
    Rule(int factor) {
        this->factor = factor;
    }
    bool evaluateInefficient(set<int>& facts) {
        vector<int> data;
        bool addedFacts = false;
        for (int fact : facts) {
            data.push_back(fact);
        }
        for (int datum : data) {
            int newFact = datum * factor;
            if (newFact < CAP) {
                addedFacts = addedFacts || facts.insert(newFact).second;
            }
        }
        return addedFacts;
    }
    bool evaluate(set<int>& facts) {
        vector<int> data;
        bool addedFacts = false;
        for (int fact : facts) {
            data.push_back(fact);
        }
        for (int datum : data) {
            int newFact = datum * factor;
            if (newFact < CAP) {
                if (facts.insert(newFact).second) {
                    addedFacts = true;
                }
            }
        }
        return addedFacts;
    }
};

int doublyInefficient(vector<Rule>& rules) {
    set<int> facts;
    facts.insert(1);
    bool addedFacts = true;
    int passes = 0;
    while (addedFacts) {
        passes++;
        addedFacts = false;
        for (Rule rule : rules) {
            addedFacts = addedFacts || rule.evaluateInefficient(facts);
        }
    }
    return passes;
}

int singlyInefficient(vector<Rule>& rules) {
    set<int> facts;
    facts.insert(1);
    bool addedFacts = true;
    int passes = 0;
    while (addedFacts) {
        passes++;
        addedFacts = false;
        for (Rule rule : rules) {
            addedFacts = addedFacts || rule.evaluate(facts);
        }
    }
    return passes;
}

int efficient(vector<Rule>& rules) {
    set<int> facts;
    facts.insert(1);
    bool addedFacts = true;
    int passes = 0;
    while (addedFacts) {
        passes++;
        addedFacts = false;
        for (Rule rule : rules) {
            if (rule.evaluate(facts)) {
                addedFacts = true;
            }
        }
    }
    return passes;
}

int main(int argc, char* argv[]) {
    //build the rules
    vector<Rule> rules;
    rules.push_back(Rule(2));
    rules.push_back(Rule(3));
    rules.push_back(Rule(5));
    rules.push_back(Rule(7));
    rules.push_back(Rule(11));
    rules.push_back(Rule(13));
    //Show three different codes that should (in my mind) take the same amount of passes over the rules but don't
    cout << "Facts populated after " << doublyInefficient(rules) << " passes through the Rules." << endl;
    cout << "Facts populated after " << singlyInefficient(rules) << " passes through the Rules." << endl;
    cout << "Facts populated after " << efficient(rules) << " passes through the Rules." << endl;
    getchar();
}

Я получаю следующий вывод при работе в режиме отладки и выпуска (32-разрядная версия) в Visual Studio 2017. Насколько мне известно, код не оптимизирован.

Facts populated after 61 passes through the Rules.
Facts populated after 17 passes through the Rules.
Facts populated after 7 passes through the Rules.

Answer 1

Разница возникает из-за оценки короткого замыкания: рассмотрим выражение в форме (expr1 || expr2), Короткое замыкание означает, что если expr1 оценивает trueвыражение expr2 не будет оцениваться вообще (см. этот стандартный черновой вариант C++, ephasis - мой):

5.15 Логический оператор ИЛИ

|| оператор группы слева направо. Оба операнда контекстуально преобразуются в bool (пункт [conv]). Он возвращает true, если любой из его операндов равен true, и false в противном случае. В отличие от |, || гарантирует оценку слева направо; более того, второй операнд не оценивается, если первый операнд оценивается как true.

Следовательно, в вашем выражении addedFacts || set.insert(x).secondот точки, где addedFacts становится true первый раз, выражение set.insert(x).second больше не будет казнен. Я полагаю, что это "неправильное" поведение, так как ваш set не будет содержать соответствующие xтогда.

Answer 2

addedFacts = addedFacts || set.insert(x).second;

а также

if (set.insert(x).second) {
    addedFacts = true;
}

Это определенно не то же самое. Первый блок кода эквивалентен:

if (!addedFacts) {
    addedFacts = set.insert(x).second;
}

!addedFacts проверка имеет большое значение.