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)).

CodePudding user response：

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.

CodePudding user response：

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.