I have a collection of
n
A
B
A
B
obj1.A > obj2.A
obj1.B > obj2.B
A
O(log n)
A
std::lower_bound
B
A
B
O(log n)
An example of what I rambled about in my comments:
#include <set>
#include <iostream>
namespace test {
struct test {
int A;
int B;
};
bool operator< (test const& lhs, test const& rhs) {
return lhs.A < rhs.A;
}
struct test_B { double B; };
bool operator< (test const& lhs, test_B const& rhs) {
return lhs.B < rhs.B;
}
bool operator< (test_B const& lhs, test const& rhs) {
return lhs.B < rhs.B;
}
}
int main() {
std::set<test::test, std::less<void>> example {
{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}
};
std::cout << example.lower_bound<test::test_B>({3.5})->B;
return 0;
}
c++14 allows for sets to call lower_bound
on anything they can compare against their key. Now, all I did was create a wrapper type that is comparable to my original structure, but it looks at the B
value. Effectively, I made set::lower_bound
look at B
instead of A
as it does by default.
Since your numeric keys are correlated, I suspect you'd get the promised set performance of lower_bound
.
You can take a look at it here