Joseph Stack - 3 months ago 23

C++ Question

I have a collection of

`n`

`A`

`B`

I know that orders on

`A`

`B`

`obj1.A > obj2.A`

`obj1.B > obj2.B`

If I implement the collection as a set sorted by

`A`

I can support in

`O(log n)`

- insertion
- deletion
- lower_bound on
`A`

But searching

`std::lower_bound`

`B`

I know that I could define my own implementation of binary trees (ex: red-black or AVL) that would store in each node both the

`A`

`B`

`O(log n)`

Is there a simpler (higher level) approach to support efficiently the 4 operations (search on both attributes, insertion and deletion)?

Answer

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