CODEWITHSUNDEEP
c++stlc++14
jma
jma

Reputation: 3779

Searching std::map in O(n) for a partial key

I have a (C++ 14) map

using MyTuple = tuple<A, B, C>;
map<MyTuple, MyData>

where MyTuple has the obvious operator<() that compares first A, then B, then C.

I want to do an O(ln N) search for keys that match some constant (a, b). Obviously if any are present they will be consecutive. So basically I want

map<MyTuple, MyData> my_map = GetMyData();
tuple<A, B> my_key = make_tuple(a, b);
auto iter = my_map.lower_bound_if([my_key](const MyTuple& key) {
    if (get<0>(my_key) == get<0>(key) &&
        get<1>(my_key) == get<1>(key)) {
        return true;
    }
    return false;
});
while( /* iter.first is still an (a,b) */) {
    // Do something with iter.
    // Increment iter.
}

But there's no function map::lower_bound_if and yet map::find and map::lower_bound take a full MyTuple. I could (hackishly) find a value of C that is lower than anything in my data, though this is fragile over time. I could write the function myself though it would likely be dependent on my current local implementation of std::map.

Have I missed an obvious solution?

Update

The solution, which I've accepted, was to use partial key mathing in the compare function (transparent operator functors), which are new since C++14 and took me longer than I care to admit to understand. This article was a good mental ice breaker and this SO question was good once I understood.

The basic insight is to consider a set of objects sorted on some key that is part of the object. For example, a set of employees with the sort key being employee.id. And we'd like to be able to search on employee or on the integer id. So we make a struct of bool operator()() that encompasses the various ways we might want to compare. And then overload resolution does the rest.

In my case, this meant that I could provide the strict total ordering I needed to make my code work but also provide a comparator that only imposes a partial ordering which I only use for lower_bound() lookups. Because the extra comparator doesn't provide a strict total ordering, it would not be suitable for, say, find() unless we meant "find one of".

As an aside, I realised after posing my question that it was a bit daft in a way. I wanted an O(ln n) lookup but wanted to use a different sort function. That can't be guaranteed to work: it depends on me providing a sort function that really does provide an ordering that is a sub-ordering of the strict total ordering. If I did otherwise, it would clearly fail. And so this is why there's no O(ln n) function find_if(), because that can only be linear.

Indeed, the technique of transparent operator functors is clever but does depend on the programmer providing no worse than a subordering.

Upvotes: 2

Views: 720

Answers (3)

Gem Taylor
Gem Taylor

Reputation: 5613

One approach is to put "any value you like" for C, use lower_bound, and be aware that the values you are looking for might be before the lower_bound, as well as after, so you might need to do some operator-- to find the first one, just as you would use operator++ to find the last one? The number of operations in order to find the range in advance does not change, but there is an in-advance overhead if you wanted to iterate over them and test for the end of <A,B> on the fly.

Obviously, it would be convenient, but not necessary, if that C was a "hacky" value that compared as the lowest possible C, as that would make the backward search faster, but we have mitigated your risk of fragility?

Another option would be to make your own container that is a map of maps. The outer map would be indexed by <A,B> and the inner map indexed by < C >.

You could then add your own methods to implement a whole-map indexing and iteration using <A,B,C>; and use the existing <A,B> methods to either return the inner map when indexed, or return your iterators as results for lower_bound and upper_bound, that can then be used as a range for all <A,B,allC>.

Upvotes: 1

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726579

In c++14 you can use the overload to search on a partial key:

struct CompareFirstTwo {
    using is_transparent = void;
    bool operator()(const tuple<A, B, C>& lhs, const tuple<A, B, C>& rhs) const ...
    bool operator()(const tuple<A, B>& lhs, const tuple<A, B, C>& rhs) const ...
    bool operator()(const tuple<A, B, C>& lhs, const tuple<A, B>& rhs) const ...
};

Use the comparator above in a call to equal_range to ignore the third field in the tuple.

Upvotes: 5

Jeffrey
Jeffrey

Reputation: 11410

If you have an order such that x {xa, xb, xc} is always < than y {ya, yb, yc} when f(xa, xb) (and conversely for >), it becomes easy. Consider it as "sort by A and B first".

Then you just need to know your maximal and minimal C value.

Search between lower_bound(a, b, MIN_C) and upper_bound(a, b, MAX_C). Alternatively, as suggested in the comments

A map of tuple<A, B> to map of C to MyData? – Vlad Feinstein

would work.

Upvotes: 0

Related Questions