`std::find()` 是否短路？

Question

考虑我有一个std::vector这样的，它的内容是std::strings 和{"a","b","c"}。如果我要执行std::find()寻找"a"，它会在迭代结束后停止"a"（即短路）还是继续到最后？

std::vector<std::string> vec;
vec.insert(vec.begin(), "a");
vec.insert(vec.begin(), "b");
vec.insert(vec.begin(), "c");

哪个更快？

std::find(vec.begin(), vec.end(), "a");
std::find(vec.begin(), vec.end(), "c");

Answer 1

查看可能的实现 std::find

template<class InputIt, class T>
constexpr InputIt find(InputIt first, InputIt last, const T& value)
{
    for (; first != last; ++first) {
        if (*first == value) {  // if the condition met
            return first;       // ---> here returns the iterator
        }
    }
    return last;
}

一旦找到匹配项，它将停止迭代。

Answer 2

根据这里的描述，是的。

返回范围 [first, last) 中满足特定条件的第一个元素。

复杂性：至多最后 - 谓词的第一次应用

并通过查看其可能的实现方式，说明std::find使用短路

Answer 3

在C ++ 17草案标准定义的行为std::find在[alg.find] （仅相关于所讨论引用使用过载部分）：

template<class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value);

[...]

返回：i范围内[first, last)满足以下相应条件的第一个迭代器：*i == value, [...]。last如果没有找到这样的迭代器，则返回。

复杂性：最多last - first应用相应的谓词。

以前的标准版本，包括 C++03，包含基本相同的措辞。

这里没有任何内容保证元素以任何特定顺序进行搜索，或者std::find一旦找到匹配项就必须停止测试谓词。

但是，由于该函数必须返回满足条件的范围内的第一个迭代器，因此无序测试是没有意义的，因为如果找到匹配项，则无论如何都需要测试所有先前的迭代器是否有较早的匹配项。

一旦找到匹配项，继续应用谓词也是没有意义的，并且标准只要求“最多”应用谓词，就像范围中的元素一样。

因此，任何合理的顺序实现都std::find将按顺序搜索迭代器范围，并在找到匹配项时返回。如果一个实现没有这样做，用户会在他们注意到后立即抱怨。标准库实现者希望他们的代码在可能的情况下运行得很快，而让他们的代码做不必要的工作并没有好处。

我想，如果实现可以利用并行化，如果它知道这不会导致给定类型的数据竞争，并且在这种情况下，搜索可能会检查第一个匹配项之外的迭代器。std::find我不知道是否在任何标准库中为问题中的非并行重载实现了这样的东西。