Find_if是否爲線性集？

Question

我遇到了set :: find不是找到對象的正確方法，因爲我以不同的方式（通過std :: find_if）找到對象，而不是它在集合中的順序。我還沒有找到任何關於如何找到元素的複雜信息。我假設它是線性的，因爲遍歷一個「無序」容器來查找匹配是線性的。

Answer 1

您可以看看here並查看find_if的複雜性是線性的。

這是因爲find_if是一種廣義算法，它不知道它使用的某種類型的容器。所以它不能使用不同容器的特性來增強搜索過程，只是檢查所有元素以找到合適的元素。

Answer 2

是的，它的複雜性是線性的。

迭代器參數是一個InputIterator，它是單向的。唯一可以想象的實現是遍歷每個元素並檢查謂詞。由於謂詞是任意的，因此不可能將算法專用於不同的容器類型，以提高算法的複雜性。

Answer 3

是的，它是線性的。

從這ref：

複雜

最多線性在第一和最後一個之間的距離：預解碼值的每個元素的呼叫，直到找到一個匹配。

在原型爲：

template<class InputIterator, class UnaryPredicate> 
    InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred) 

而且從另一個ref：

複雜

在去年大部分時間 - 謂語的第一應用