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.
