Time complexity for std::find_if() using set in C++

Question

What is time complexity for std::find_if() function using std::set in C++?

Consider we have the following example:

auto cmp = [&](const pair<int, set<int>>& a , const pair<int, set<int>>& b) -> bool {
    if (a.second.size() == b.second.size()) {
        return a.first < b.first;
    }
    return a.second.size() < b.second.size();
};
set<pair<int, set<int>>, decltype(cmp)> tree(cmp);
...
int value = ...;
auto it = find_if(tree.begin(), tree.end(), [](const pair<int, int> &p) {
    return p.first == value;
});

I know it takes std::find_if O(n) to work with std::vector. Can't see any problems for this function not to work with std::set with time complexity O(log(n)).

`std::find_if` is equal opportunity because it can't take advantage of any special magic from the container. It just goes from iterator to iterator loo king for a match https://en.cppreference.com/w/cpp/algorithm/find#Complexity — user4581301, Nov 09 '22 at 20:45
@user4581301 Make that an answer (it's literally the exact answer). — lorro, Nov 09 '22 at 20:47

score 1 · Answer 1 · answered Nov 09 '22 at 20:50

The complexity for std::find, std::find_if, and std::find_if_not is O(N). It does not matter what type of container you are using as the function is basically implemented like

template<class InputIt, class UnaryPredicate>
constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
{
    for (; first != last; ++first) {
        if (p(*first)) {
            return first;
        }
    }
    return last;
}

Which you can see just does a linear scan from first to last

If you want to take advantage of std::set being a sorted container, then you can use std::set::find which has O(logN) complexity. You can get a find_if type of behavior by using a comparator that is transparent.

`std::find_if` is `O(n)` only, if the amoritized cost of incrementing the iterator and the amortized cost of dereferencing the iterator are both `O(1)`. It's possible to implement containers where this is not the case. — fabian, Nov 09 '22 at 21:17

score 0 · Answer 2 · answered Nov 09 '22 at 20:50

std::find_if is equal opportunity because it can't take advantage of any special magic from the container. It just iterates the container looking for a match, so worst case is always O(N).

See documentation for std::find_if starting at the section on Complexity and pay special attention to the possible implementations.

Note that std::find_if's actual performance will likely be MUCH worse with a set than that of a vector of the same size because of the lack of locality in the data stored.

Time complexity for std::find_if() using set in C++

2 Answers2