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

Question

假设我有一个 std::vector，它的内容是 std::string 和 {"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

根据描述 here，是的。

Returns the first element in the range [first, last) that satisfies specific criteria.

Complexity: At most last - first applications of the predicate

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

Answer 3

C++17 标准草案在 [alg.find] 中定义了 std::find 的行为（仅与引用问题中使用的重载相关的部分）：

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

[...]

Returns: The first iterator i in the range [first, last) for which the following corresponding conditions hold: *i == value, [...]. Returns last if no such iterator is found.

Complexity: At most last - first applications of the corresponding predicate.

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

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

然而，由于函数必须 return first 迭代器在满足条件的范围内，乱序测试没有意义，因为如果找到匹配项，无论如何都需要测试所有先前的迭代器以查找更早的匹配项。

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

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

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

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

Does `std::find()` short circuit?

c++

iterator

vector

c++03