使用可变参数模板和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.它试图std::function从lambda中推导出类型,并因为它们是不相关的类型而失败.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;}

如果你真的需要在一行上做,直接进行绑定.

接下来,我们想要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<a 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返回a std::string const&(如果可能)的a也可以提高性能."投影lambda"可能必须有一个->decltype(auto)实现第二次提升.

我上面使用了一些C++ 14.的std::remove_reference_t<?>(以及类似),别名可以被替换typename std::remove_reference<?>::type,或者您也可以编写自己的_t别名.使用的建议decltype(auto)可以decltype(the return expression)在C++ 11中替换.

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