c++ - 使用可变参数模板和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
}

但是现在由于我不明白的原因，我无法用 int, char替换特定的参数 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 ...)>'

更新:
研究了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可以进行SFINAE友好的确定范围的值和迭代器类型。

现在，在该样板之上添加 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如果存在，则在其下排序，否则返回 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;}

如果您确实需要一行完成，则直接进行绑定(bind)。

接下来，我们要 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友好的(即，它“过早失效”)。为此，我明确确定了它的返回类型。 (下面我们看到这不是必需的，但是可能在更复杂的情况下)。

Live example。

有趣的是，您的 [](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');}

我们完成了。 Simpler example:

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&也可以提高性能。 “投影lambda”可能必须带有 ->decltype(auto)才能实现第二次提升。

我在上面使用了一些C++ 14。 std::remove_reference_t<?>(及类似名称)别名可以替换为 typename std::remove_reference<?>::type，或者您可以编写自己的 _t别名。在C++ 11中，可以将 decltype(auto)的建议替换为 decltype(the return expression)。
order_by_t使用继承来存储 F和 C，因为它们很可能是空类，因此我想利用空基优化。