Joseph Stack - 20 days ago 11
C++ Question

# Defining and searching sets on correlated orders in C++

I have a collection of

`n`
objects. Each object has 2 numeric attributes
`A`
and
`B`
.
I know that orders on
`A`
and
`B`
are fully correlated:
`obj1.A > obj2.A`
if and only if
`obj1.B > obj2.B`
.

If I implement the collection as a set sorted by
`A`
,
I can support in
`O(log n)`
the following operations:

• insertion

• deletion

• lower_bound on
`A`

But searching
`std::lower_bound`
on attribute
`B`
will be linear because sets do not support RandomAccessIterators.
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`
and
`B`
values. This way I could have
`O(log n)`
for all 4 operations.

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

``````#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