Defining and searching sets on correlated orders in C++

Question

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)?

Answer 1

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

Defining and searching sets on correlated orders in C++

Sign up