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

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

Comments