Binary search using variadic templates and lambda functions
Consider this,
struct Person {
std::string name;
Person (const std::string& n) : name(n) {}
std::string getName(int, char) const {return name;} // int, char play no role in this
// simple example, but let suppose that they are needed.
} *Bob = new Person("Bob"), *Frank = new Person("Frank"), *Mark = new Person("Mark"),
*Tom = new Person("Tom"), *Zack = new Person("Zack");
const std::vector<Person*> people = {Bob, Frank, Mark, Tom, Zack};
Since it is people
sorted by name, we can do a binary search to find an item people
with a specific name. I want this challenge to look like
Person* person = binarySearch (people, "Tom",
[](Person* p, int n, char c) {return p->getName(n,c);},
[](const std::string& x, const std::string& y) {return x.compare(y) < 0;}, 5, 'a');
therefore the template function binarySearch
can be used in general. I got it working with the following:
#include <iostream>
#include <string>
#include <vector>
#include <functional>
struct Person {
std::string name;
Person (const std::string& n) : name(n) {}
std::string getName(int, char) const {return name;} // int, char play no role in this
// simple example, but let supposes that they are needed.
} *Bob = new Person("Bob"), *Frank = new Person("Frank"), *Mark = new Person("Mark"),
*Tom = new Person("Tom"), *Zack = new Person("Zack");
const std::vector<Person*> people = {Bob, Frank, Mark, Tom, Zack};
template <typename Container, typename Ret>
typename Container::value_type binarySearch (const Container& container, const Ret& value,
std::function<Ret(const typename Container::value_type&, int, char)> f,
std::function<bool(const Ret&, const Ret&)> comp,
typename Container::difference_type low, typename Container::difference_type high,
int n, char c) {
if (low > high)
std::cout << "Error! Not found!\n";
const typename Container::difference_type mid = (low + high) / 2;
const Ret& r = f(container[mid], n, c);
if (r == value)
return container[mid];
if (comp(r, value))
return binarySearch (container, value, f, comp, mid + 1, high, n, c);
return binarySearch (container, value, f, comp, low, mid - 1, n, c);
}
template <typename Container, typename Ret>
typename Container::value_type binarySearch (const Container& container, const Ret& value,
std::function<Ret(const typename Container::value_type&, int, char)> f,
std::function<bool(const Ret&, const Ret&)> comp, int n, char c) {
return binarySearch (container, value, f, comp, 0, container.size() - 1, n, c);
}
int main() {
const Person* person = binarySearch<std::vector<Person*>, std::string>
(people, "Tom", &Person::getName,
[](const std::string& x, const std::string& y) {return x.compare(y) < 0;}, 5, 'a');
std::cout << person->getName(5,'a') << '\n'; // Tom
}
But now, for reasons I don't understand, I cannot replace the specific arguments int, char
with Args...
. You can go and put Args... args
and Args...
where needed in the above code and it won't compile. What's wrong here? How do you complete the final step in generalization? Or should the whole method be changed?
This is what I tried:
template <typename Container, typename Ret, typename... Args>
typename Container::value_type binarySearch (const Container& container, const Ret& value,
std::function<Ret(const typename Container::value_type&, Args...)> f,
std::function<bool(const Ret&, const Ret&)> comp,
typename Container::difference_type low, typename Container::difference_type high,
Args... args) {
if (low > high)
std::cout << "Error! Not found!\n";
const typename Container::difference_type mid = (low + high) / 2;
const Ret& r = f(container[mid], args...);
if (r == value)
return container[mid];
if (comp(r, value))
return binarySearch (container, value, f, comp, mid + 1, high, args...);
return binarySearch (container, value, f, comp, low, mid - 1, args...);
}
template <typename Container, typename Ret, typename... Args>
typename Container::value_type binarySearch (const Container& container, const Ret& value,
std::function<Ret(const typename Container::value_type&, Args...)> f,
std::function<bool(const Ret&, const Ret&)> comp, Args... args) {
return binarySearch (container, value, f, comp, 0, container.size() - 1, args...);
}
int main() {
const Person* person = binarySearch<std::vector<Person*>, std::string> (people, "Tom",
&Person::getName,
[](const std::string& x, const std::string& y) {return x.compare(y) < 0;}, 5, 'a');
std::cout << person->getName(5,'a') << '\n';
}
GCC 4.9.2:
[Error] no matching function for call to 'binarySearch(std::vector<Person*>&, const char [4], main()::__lambda0, main()::__lambda1, int, char)'
template argument deduction/substitution failed:
[Note] 'main()::__lambda0' is not derived from 'std::function<std::basic_string<char>(Person* const&, Args ...)>'
Update: After examining Jakk's solution, I adapted my solution to the following (using earlier principles instead of std :: equal_range):
#include <iostream>
#include <iterator>
template <typename Container, typename T, typename Comparator = std::less<T>>
typename Container::value_type binarySearchRandomAccessIterator (const Container& container, T&& value, Comparator&& compare, typename Container::difference_type low, typename Container::difference_type high) {
if (low > high)
{std::cout << "Error! Not found!\n"; return container[high];}
const typename Container::difference_type mid = (low + high) / 2;
const auto& t = compare.function(container[mid]); // Using 'const T& t' does not compile.
if (t == value)
return container[mid];
if (compare.comparator(t, value)) // 't' is less than 'value' according to compare.comparator, so search in the top half.
return binarySearchRandomAccessIterator (container, value, compare, mid + 1, high);
return binarySearchRandomAccessIterator (container, value, compare, low, mid - 1); // i.e. 'value' is less than 't' according to compare.comparator, so search in the bottom half.
}
template <typename ForwardIterator, typename T, typename Comparator = std::less<T>>
typename std::iterator_traits<ForwardIterator>::value_type binarySearchNonRandomAccessIterator (ForwardIterator first, ForwardIterator last, T&& value, Comparator&& compare) {
ForwardIterator it;
typename std::iterator_traits<ForwardIterator>::difference_type count, step;
count = std::distance(first, last);
while (count > 0) { // Binary search using iterators carried out.
it = first;
step = count / 2;
std::advance(it, step); // This is done in O(step) time since ForwardIterator is not a random-access iterator (else it is done in constant time). But the good news is that 'step' becomes half as small with each iteration of this loop.
const auto& t = compare.function(*it); // Using 'const T& t' does not compile.
if (compare.comparator(t, value)) { // 't' is less than 'value' according to compare.comparator, so search in the top half.
first = ++it; // Thus first will move to one past the half-way point, and we search from there.
count -= step + 1; // count is decreased by half plus 1.
}
else // 't' is greater than 'value' according to compare.comparator, so remain in the bottom half.
count = step; // 'count' and 'step' are both decreased by half.
}
if (compare.function(*first) != value)
std::cout << "Error! Not found!\n";
return *first;
}
template <typename Container, typename T, typename Comparator = std::less<T>> // Actually the version below could be used if Container has a random-access iterator. It would be with the same time complexity since std::advance has O(1) time complexity for random-access iterators.
typename std::enable_if<std::is_same<typename std::iterator_traits<typename Container::iterator>::iterator_category, std::random_access_iterator_tag>::value, typename Container::value_type>::type
binarySearch (const Container& container, T&& value, Comparator&& compare = {}) {
std::cout << "Calling binarySearchWithRandomAccessIterator...\n";
return binarySearchRandomAccessIterator (container, value, compare, 0, container.size() - 1);
}
// Overload used if Container does not have a random-access iterator.
template <typename Container, typename T, typename Comparator = std::less<T>>
typename std::enable_if<!std::is_same<typename std::iterator_traits<typename Container::iterator>::iterator_category, std::random_access_iterator_tag>::value, typename Container::value_type>::type
binarySearch (const Container& container, T&& value, Comparator&& compare = {}) {
std::cout << "Calling binarySearchNonRandomAccessIterator...\n";
return binarySearchNonRandomAccessIterator (std::begin(container), std::end(container), value, compare);
}
template <typename Function, typename Comparator>
struct FunctionAndComparator {
Function function;
Comparator comparator;
FunctionAndComparator (Function&& f, Comparator&& c) : function(std::forward<Function>(f)), comparator(std::forward<Comparator>(c)) {}
};
template <typename Function, typename Comparator = std::less<>>
FunctionAndComparator<std::decay_t<Function>, std::decay_t<Comparator>> functionAndComparator (Function&& f, Comparator&& c = {}) {
return {std::forward<Function>(f), std::forward<Comparator>(c)};
}
#include <string>
#include <vector>
#include <list>
struct Person {
std::string name;
Person (const std::string& n) : name(n) {}
std::string getName (int, char) const {return name;} // int, char play no role in this simple example, but let supposes that they are needed.
} *Bob = new Person("Bob"), *Frank = new Person("Frank"), *Mark = new Person("Mark"), *Tom = new Person("Tom"), *Zack = new Person("Zack");
const std::vector<Person*> peopleVector = {Bob, Frank, Mark, Tom, Zack};
const std::list<Person*> peopleList = {Bob, Frank, Mark, Tom, Zack};
int main() {
Person* tom = binarySearch (peopleVector, "Tom", functionAndComparator([](const Person* p) {return p->getName(5,'a');}, [](const std::string& x, const std::string& y) {return x.compare(y) < 0;}));
if (tom) std::cout << tom->getName(5,'a') << " found.\n";
Person* bob = binarySearch (peopleVector, "Bob", functionAndComparator([](const Person* p) {return p->getName(3,'k');})); // The default comparator, std::less<std::string>, is actually the same as the comparator used above.
if (bob) std::cout << bob->getName(3,'k') << " found.\n";
Person* frank = binarySearch (peopleList, "Frank", functionAndComparator([](const Person* p) {return p->getName(8,'b');}));
if (frank) std::cout << frank->getName(8,'b') << " found.\n";
Person* zack = binarySearch (peopleList, "Zack", functionAndComparator([](const Person* p) {return p->getName(2,'c');}));
if (zack) std::cout << zack->getName(2,'c') << " found.\n";
Person* mark = binarySearch (peopleList, "Mark", functionAndComparator([](const Person* p) {return p->getName(6,'d');}));
if (mark) std::cout << mark->getName(6,'d') << " found.\n";
}
source to share
To my mind
Person* person = binarySearch (people, "Tom",
[](Person* p, int n, char c) {return p->getName(n,c);},
[](const std::string& x, const std::string& y) {return x.compare(y) < 0;}, 5, 'a');
- terrible syntax. Your function binarySearch
is possible for too many things.
But first, what went wrong: your ambiguous error occured because the lambda is not std::function
. It tries to infer the type std::function
from the lambda and fails because they are unrelated types. The ability to lead Args...
from another location does not help.
You can wrap the arguments std::function
in:
template<class T>struct tag{using type=T;};
template<class Tag>using type_t=typename Tag::type;
template<class T>using identity=type_t<tag<T>>;
identity< std::function< whatever... > >
and your code will start compiling (as Args...
output elsewhere). identity<?>
blocks template type inference on that argument, so the compiler no longer tries, but instead infers the type from other arguments.
However, this is not a good decision.
The best solution is to make type f
and c
be f
and c
not convert them to std::function
. This removes the meaningless erase overhead and eliminates the need foridentity<?>
This is still not a good solution, because your template function does a bunch of things, few of them are good. Instead, decompose your operation into simpler tasks, and then put them together:
First, we already have one std::equal_range
, which will be a better binary search engine than any you are likely to write. Writing a function that returns a single item and takes a container seems like a good idea, since working with iterators is annoying.
To get around this, we first write some boilerplate:
namespace adl_aux {
using std::begin; using std::end;
template<class R>
auto adl_begin(R&&)->decltype(begin(std::declval<R>()));
template<class R>
auto adl_end(R&&)->decltype(end(std::declval<R>()));
}
template<class R>
using adl_begin = decltype(adl_aux::adl_begin(std::declval<R>));
template<class R>
using adl_end = decltype(adl_aux::adl_end(std::declval<R>));
template<class R>using iterator_t = adl_begin<R>;
template<class R>using value_t = std::remove_reference_t<decltype(*std::declval<iterator_t<R>>())>;
This allows us to support std::
third-party containers and arrays and iterative containers and ranges. Material adl_
contains depending on the argument list begin
, and end
for us. iterator_t
and value_t
makes SFINAE-friendly definition of the value and type of the range iterator.
Now bin_search
on top of this template:
template<class R, class T, class F=std::less<T>>
value_t<R>* bin_search( R&& r, T&& t, F&& f={} ) {
using std::begin; using std::end;
auto range = std::equal_range( begin(r), end(r), std::forward<T>(t), std::forward<F>(f) );
if (range.first==range.second) return nullptr;
return std::addressof( *range.first ); // in case someone overloaded `&`
}
which returns a pointer to the item t
under the ordering f
Assuming R
sorted under it if it exists and otherwise nullptr
.
The next part is your order:
[](Person* p, int n, char c) {return p->getName(n,c);},
[](const std::string& x, const std::string& y) {return x.compare(y) < 0;}, 5, 'a'
get rid of this first Args...
:
[](int n, char c){
return [n,c](Person* p) {return p->getName(n,c);}
}(5,'a'),
[](const std::string& x, const std::string& y) {return x.compare(y) < 0;}
if you really need to do it on one line then bind directly.
Then we want order_by
:
template<class F, class C>
struct order_by_t : private F, private C {
F const& f() const { return *this; }
C const& c() const { return *this; }
template<class T>
auto f(T&&t)const
->decltype( std::declval<F const&>()(std::declval<T>()) )
{
return f()(std::forward<T>(t));
}
template<class T, class... Unused> // Unused to force lower priority
auto f(T&&t, Unused&&... ) const
-> std::decay_t<T>
{ return std::forward<T>(t); }
template<class Lhs, class Rhs>
bool operator()(Lhs&& lhs, Rhs&& rhs) const {
return c()( f(std::forward<Lhs>(lhs)), f(std::forward<Rhs>(rhs)) );
}
template<class F0, class C0>
order_by_t( F0&& f_, C0&& c_ ):
F(std::forward<F0>(f_)), C(std::forward<C0>(c_))
{}
};
template<class C=std::less<>, class F>
auto order_by( F&& f, C&& c={} )
-> order_by_t<std::decay_t<F>, std::decay_t<C>>
{ return {std::forward<F>(f), std::forward<C>(c)}; }
order_by
takes a projection from a domain to a range and possibly orders in that range and performs an ordering in the domain.
order_by(
[](int n, char c){
return [n,c](Person const* p)
->decltype(p->getName(n,c)) // SFINAE enabled
{return p->getName(n,c);};
}(5,'a'),
[](const std::string& x, const std::string& y) {return x.compare(y) < 0;}
}
now orders to Person const*
which follows your requirement.
We then pass this to bin_search
:
auto ordering = order_by(
[](int n, char c){
return [n,c](Person const* p)
->decltype(p->getName(n,c)) // SFINAE enabled
{return p->getName(n,c);}
}(5,'a'),
[](const std::string& x, const std::string& y) {return x.compare(y) < 0;}
);
Person*const* p = bin_search( people, "Tom", ordering );
now a few things had to be done to make the order_by
function object "transparent", where it accepts both things that can be projected (under the projection) and cannot be (which are passed directly to the comparator).
This requires the design operation to be SFINAE friendly (that is, that it "doesn't fire early"). For this purpose, I have explicitly defined its return type. (Below we see that this is not required, but may be in more complex situations).
Ridiculous, yours [](const std::string& x, const std::string& y) {return x.compare(y) < 0;}
agree with operator<
on std::string
, so you can opt out (and make order_by
it easier). However, I suspect your real-world use case needs this, and it's a useful feature to reinforce order_by
with.
Finally, notice that this part:
[](int n, char c){
return [n,c](Person const* p)
->decltype(p->getName(n,c)) // SFINAE enabled
{return p->getName(n,c);}
}(5,'a'),
is ugly and can be replaced with:
[](Person const* p)
->decltype(p->getName(5,'a')) // SFINAE enabled
{return p->getName(5,'a');}
which is less ugly. Also, since checking the lambda parameters is sufficient, we can remove the explicit return type of SFINAE:
[](Person const* p)
{return p->getName(5,'a');}
and we're done. Simple example :
auto ordering = order_by(
[](Person const* p)
{return p->getName(5,'a');}
);
Person*const* p = bin_search( people, "Tom", ordering );
or even:
Person*const* p = bin_search( people, "Tom",
order_by( [](Person const* p) {return p->getName(5,'a');} )
);
which looks a lot less ugly, doesn't it?
Oh and:
using std::literals;
Person*const* p = bin_search( people, "Tom"s,
order_by( [](Person const* p) {return p->getName(5,'a');} )
);
may have better performance as it avoids rebuilding std::string("Tom")
with every comparison. Likewise, an a getName
that returns a std::string const&
(if possible) can also provide a performance boost. A "projection lambda" might need to have it ->decltype(auto)
in order to realize this second impulse.
I have used C ++ 14 above. Aliases std::remove_reference_t<?>
(and similar ones) can be replaced with typename std::remove_reference<?>::type
, or you can write your own aliases _t
. Usage advice decltype(auto)
can be replaced with decltype(the return expression)
in C ++ 11.
order_by_t
uses inheritance to store f
and c
, because they can be empty classes, so I wanted to use empty base optimization.
source to share