使用可变模板和lambda函数的二进制搜索

Question

想想这个，

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's 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};

因为people是按名称排序的，所以我们可以执行二进制搜索来查找具有特定名称的people元素。我想让这个电话看起来像

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');

因此，模板函数binarySearch可以泛化使用。我让它处理了以下几个方面：

#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's 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
}

但是，由于我不明白的原因，我无法用Args...替换特定的参数Args...。您可以继续将Args... args和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,
        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:在研究了Yakk的解决方案后，将我的解决方案调整为以下内容(使用更多的首要原则而不是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's 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";
}

Answer 1

照我的想法

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');

是一个可怕的语法。您的binarySearch函数可用于处理太多的事情。

但是首先，出了什么问题:您的模糊错误发生是因为lambda不是std::function。它试图从lambda中推断出std::function类型，但是失败了，因为它们是无关的类型。从其他地方推断Args...的能力没有帮助。

您可以将您的std::function参数包装在：

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... > >和您的代码将开始编译(因为Args...是在其他地方推导出来的)。identity<?>阻止对该参数的模板类型推断，因此编译器不再尝试，而是从其他参数中推断该类型。

然而，这不是一个好的解决办法。

一个更好的解决方案是让f和c的类型成为F和C --根本不要把它们变成std::function。这样就消除了不必要的类型擦除开销，并消除了对identity<?>的需求。

这仍然不是一个好的解决方案，因为您的模板函数做了很多事情，其中很少做得很好。相反，将您的操作分解为更简单的问题，然后将它们组合在一起：

首先，我们已经有了std::equal_range，它将比您可能编写的任何二进制搜索都要好。编写一个返回单个元素并接受容器的函数似乎是合理的，因为使用迭代器是很烦人的。

为了实现这一点，我们首先编写了一些基于范围的样板：

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>>())>;

这允许我们支持std::容器和数组以及第三方可迭代容器和范围。adl_的内容为我们提供了与begin和end有关的参数相关查找。iterator_t和value_t可以方便地确定范围的值和迭代器类型.

现在，bin_search放在样板上：

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 `&`
}

它返回一个指向元素t的指针，该指针位于排序f下，假定R在其下排序，如果存在，则返回R，否则返回nullptr。

下一部分是你的订购混乱：

[](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'

首先，去掉那个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;}

如果您确实需要在一行上进行绑定，则直接执行绑定。

接下来，我们要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接受从域到范围的投影，并在该范围上(可选地)排序，并在域上产生排序。

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*进行排序。

然后我们将其输入到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 );

现在，必须谨慎地使order_by成为一个“透明”函数对象，在该对象中，它接受两个可以投影(在投影下)和不能(直接传递给比较器)的东西。

这要求投影操作是SFINAE友好的(即，它“早期失败”)。为此，我显式地确定了它的返回类型。(下面我们看到这不是必需的，但可能是在更复杂的情况下)。

实例化。

有趣的是，您的[](const std::string& x, const std::string& y) {return x.compare(y) < 0;}与operator<在std::string上一致，因此您可以放弃它(并使order_by变得更简单)。然而，我怀疑您真正的用例需要它，并且它是增强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'),

是丑陋的，可以用：

  [](Person const* p)
    ->decltype(p->getName(5,'a')) // SFINAE enabled
    {return p->getName(5,'a');}

就不那么丑了。另外，由于lambda的参数检查足够了，我们可以删除SFINAE显式返回类型：

  [](Person const* p)
    {return p->getName(5,'a');}

我们就完了。更简单的例子

auto ordering = order_by(
   [](Person const* p)
     {return p->getName(5,'a');}
);
Person*const* p = bin_search( people, "Tom", ordering );

甚至：

Person*const* p = bin_search( people, "Tom",
  order_by( [](Person const* p) {return p->getName(5,'a');} )
);

看上去不那么丑，不是吗？

哦，还有：

using std::literals;
Person*const* p = bin_search( people, "Tom"s,
  order_by( [](Person const* p) {return p->getName(5,'a');} )
);

可能有更好的性能，因为它将避免在每次比较中重复构造std::string("Tom")。类似地，返回一个getName (如果可能的话)的std::string const&也可以提高性能。“投射灯”可能必须有一个->decltype(auto)，才能实现第二次提振。

我在上面使用了一些C++14。std::remove_reference_t<?> (和类似的)别名可以替换为typename std::remove_reference<?>::type，也可以编写自己的_t别名。使用decltype(auto)的建议可以在C++11中用decltype(the return expression)代替。

order_by_t使用继承来存储F和C，因为它们可能是空类，所以我想利用空基优化。