I'm trying to figure out the following problem.
Suppose I have the following container in C++:
std::set<std::pair<int, int> > my_container;
This set (dictionary) is sorted with respect to the order <
on std::pair<int, int>
, which is the lexicographic order. My task is to find any element in my_container
that has the first coordinate equal to, say x
, and return the iterator to it. Obviously, I don't want to use find_if
, because I need to solve this in logarithmic time.
I would appreciate any advice on how this can be done
You can use lower_bound
for this:
auto it = my_container.lower_bound(std::make_pair(x, std::numeric_limits<int>::min());
This will give you an iterator to the first element e
for which e < std::pair(x, -LIMIT)
does not hold.
Such an element either has its first component > x
(in which case there's no x
in the set), or has the first component equal to x
and is the first such. (Note that all second components are greater than or equal to std::numeric_limits<int>::min()
by definition).
You could use std::set::lower_bound to get the lower and upper limits of the range like this:
#include <set>
#include <iostream>
// for readability
typedef std::set<std::pair<int, int> > int_set;
void print_results(const int_set& s, int i)
{
// first element not less than {i, 0}
int_set::const_iterator lower = s.lower_bound(std::make_pair(i, 0));
// first element not less than {i + 1, 0}
int_set::const_iterator upper = s.lower_bound(std::make_pair(i + 1, 0));
for(int_set::const_iterator iter = lower; iter != upper; ++iter)
std::cout << iter->first << ", " << iter->second << '\n';
}
int main()
{
int_set s;
s.insert(std::make_pair(2, 0));
s.insert(std::make_pair(1, 9));
s.insert(std::make_pair(2, 1));
s.insert(std::make_pair(3, 0));
s.insert(std::make_pair(7, 6));
s.insert(std::make_pair(5, 5));
s.insert(std::make_pair(2, 2));
s.insert(std::make_pair(4, 3));
print_results(s, 2);
}
Output:
2, 0
2, 1
2, 2
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With