template<class UnaryPred>
iterator partition_point(UnaryPred p);
template<class UnaryPred>
const_iterator partition_point(UnaryPred p) const;
It examines the keys in the container, which must be partitioned by bool(p(key)), and returns the end iterator to the first partition (i.e. the first key which bool(p(key)) is false, end() if no such key).
If the keys are not partitioned with respect to bool(p(key)), the behavior is undefined.
It calls p(key) at most O(log(size() + 1)) times.
Following is one of the use cases I've encountered a lot in competitive programming.
We need to process three kinds of queries, starting from an empty set S. (assume everything fits in int)
Q1. Add a point (x, y) to S, assuming that all x coordinates are non-negative and unique for the sake of simplicity. Same for y coordinates.
Q2. Given A, find the point (x, y) with maximum y such that x >= A, or report that there are none
Q3. Given B, find the point (x, y) with maximum x such that y >= B, or report that there are none
We want to do this online. i.e. if the current query is Q2 or Q3, we only get to know queries after answering it.
With this proposal, there's a simple way to solve this in amortized O(log(n)) time for each queries.
// T contains all points (x, y) such that there is no point (z, w) with x < z and y < w
// Clearly, (x, y) not in T cannot be an answer to Q2 or Q3
// The points are maintained in increasing order of x
// By the definition of T, y coordinates are in decreasing order
std::set<std::pair<int, int>> T;
auto Q1 = [&](int x, int y)->void{
auto it = T.lower_bound(std::pair{x, y});
// erase all point (z, w) with z < x and w < y from T
while(it != T.begin() && std::prev(it)->second < y) T.erase(std::prev(it));
// insert (x, y) if no point (z, w) satisfy x < z and y < w
if(it == T.end() || y > it->second) T.insert(it, std::pair{x, y});
};
// Returns (-1, -1) if no answer
auto Q2 = [&](int A)->std::pair<int, int>{
// use the fact that x coordinate is in increasing order
auto it = T.partition_point([&](auto key){ return key.first < A; });
return it == T.end() ? std::pair{-1, -1} : *it;
};
// Returns (-1, -1) if no answer
auto Q3 = [&](int B)->std::pair<int, int>{
// use the fact that y coordinate is in decreasing order
auto it = T.partition_point([&](auto key){ return key.second >= B; });
return it == T.begin() ? std::pair{-1, -1} : *std::prev(it);
};