使用二进制搜索的模板递归
Template recursion using binary search
考虑一下我写的这个工作代码:
#include <iostream>
constexpr int MIN_FOO = 0, MAX_FOO = 100;
template <int N>
void foo() {std::cout << "foo<" << N << ">() called.\n";}
template <int N>
void foo (char, double, bool) {std::cout << "foo<" << N << ">(char, double, bool) called.\n";}
template <int Low, int High, typename... Args>
void searchFooBinary (int key, Args... args) {
// if (LOW > HIGH) {std::cout << "Error with searchFooBinary.\n"; return;}
constexpr int Mid = (Low + High) /2;
if (key == Mid)
foo<Mid>(std::forward<Args>(args)...); // Want to generalize this using 'f'.
else if (key < Mid)
searchFooBinary<Low, Mid - 1>(key, std::forward<Args>(args)...);
else
searchFooBinary<Mid + 1, High>(key, std::forward<Args>(args)...);
}
template <typename... Args>
void executeFooBinarySearch (int n, Args... args) {
searchFooBinary<MIN_FOO, MAX_FOO>(n, std::forward<Args>(args)...);
}
int main() {
executeFooBinarySearch(99);
executeFooBinarySearch (99, 'a', 1.5, true);
}
所以 foo
是一个模板函数,这里传递了一个 运行-time int 并且 searchFooBinary
使用二进制搜索为模板参数找到正确的 int 值。到目前为止一切顺利,但我不想为每个新函数(如 foo
)编写此二进制搜索函数。我如何将 searchFooBinary
中 foo
的用法推广到更一般的 f
?如果不允许模板函数指针,实现此目标的解决方法是什么?
使用仿函数如何:
#include <iostream>
constexpr int MIN_FOO = 0, MAX_FOO = 100;
struct Foo
{
template <int N>
void operator() (char, double, bool) {std::cout << "Foo<" << N << ">(char, double, bool) called.\n";}
};
struct Bar
{
template <int N>
void operator() () {std::cout << "Bar<" << N << ">() called.\n";}
};
template <int Low, int High, typename Fun, typename... Args>
void searchBinary (int key, Fun f, Args... args)
{
constexpr int Mid = (Low + High) /2;
if (key == Mid)
{
f.template operator()<Mid>(std::forward<Args>(args)...);
}
else if (key < Mid)
{
searchBinary<Low, Mid - 1>(key, f, std::forward<Args>(args)...);
}
else
{
searchBinary<Mid + 1, High>(key, f, std::forward<Args>(args)...);
}
}
template <typename Fun, typename... Args>
void executeBinarySearch (int n, Fun f, Args... args)
{
searchBinary<MIN_FOO, MAX_FOO, Fun>(n, f, std::forward<Args>(args)...);
}
int main()
{
executeBinarySearch (99, Foo(), 'a', 1.5, true);
executeBinarySearch (99, Bar());
}
输出
Foo<99>(char, double, bool) called.
Bar<99>() called.
考虑一下我写的这个工作代码:
#include <iostream>
constexpr int MIN_FOO = 0, MAX_FOO = 100;
template <int N>
void foo() {std::cout << "foo<" << N << ">() called.\n";}
template <int N>
void foo (char, double, bool) {std::cout << "foo<" << N << ">(char, double, bool) called.\n";}
template <int Low, int High, typename... Args>
void searchFooBinary (int key, Args... args) {
// if (LOW > HIGH) {std::cout << "Error with searchFooBinary.\n"; return;}
constexpr int Mid = (Low + High) /2;
if (key == Mid)
foo<Mid>(std::forward<Args>(args)...); // Want to generalize this using 'f'.
else if (key < Mid)
searchFooBinary<Low, Mid - 1>(key, std::forward<Args>(args)...);
else
searchFooBinary<Mid + 1, High>(key, std::forward<Args>(args)...);
}
template <typename... Args>
void executeFooBinarySearch (int n, Args... args) {
searchFooBinary<MIN_FOO, MAX_FOO>(n, std::forward<Args>(args)...);
}
int main() {
executeFooBinarySearch(99);
executeFooBinarySearch (99, 'a', 1.5, true);
}
所以 foo
是一个模板函数,这里传递了一个 运行-time int 并且 searchFooBinary
使用二进制搜索为模板参数找到正确的 int 值。到目前为止一切顺利,但我不想为每个新函数(如 foo
)编写此二进制搜索函数。我如何将 searchFooBinary
中 foo
的用法推广到更一般的 f
?如果不允许模板函数指针,实现此目标的解决方法是什么?
使用仿函数如何:
#include <iostream>
constexpr int MIN_FOO = 0, MAX_FOO = 100;
struct Foo
{
template <int N>
void operator() (char, double, bool) {std::cout << "Foo<" << N << ">(char, double, bool) called.\n";}
};
struct Bar
{
template <int N>
void operator() () {std::cout << "Bar<" << N << ">() called.\n";}
};
template <int Low, int High, typename Fun, typename... Args>
void searchBinary (int key, Fun f, Args... args)
{
constexpr int Mid = (Low + High) /2;
if (key == Mid)
{
f.template operator()<Mid>(std::forward<Args>(args)...);
}
else if (key < Mid)
{
searchBinary<Low, Mid - 1>(key, f, std::forward<Args>(args)...);
}
else
{
searchBinary<Mid + 1, High>(key, f, std::forward<Args>(args)...);
}
}
template <typename Fun, typename... Args>
void executeBinarySearch (int n, Fun f, Args... args)
{
searchBinary<MIN_FOO, MAX_FOO, Fun>(n, f, std::forward<Args>(args)...);
}
int main()
{
executeBinarySearch (99, Foo(), 'a', 1.5, true);
executeBinarySearch (99, Bar());
}
输出
Foo<99>(char, double, bool) called.
Bar<99>() called.