找到产生最大函数输出的输入的快速STL方法？ （连续的整数输入）
Fast STL way to find input that produces maximum output of function? (contiguous integer inputs)
为了提高可读性，我正在努力改掉重新发明轮子的习惯。
问题：
考虑一个黑盒函数，Foo，它有一个整数作为输入和输出。我们想要找到最大化输出的输入。考虑所有可能的输入都属于一个连续的整数范围；而且范围足够小，我们可以尝试每一个。
速度很重要，所以我们不使用容器。 即使用户已经为所有可能的输入创建了一个容器，计算下一个输入（++input) 而不是从内存中获取它（缓存未命中）。
示例：
范围：[5, 8)
Foo(5); // 19
Foo(6); // 72
Foo(7); // 31
我们想做一个函数应该 return 6:
InputOfMaxOutputOnRange(5, 8, Foo); // 6
自定义解决方案：
template <typename T, typename Func>
T InputOfMaxOutputOnRange (T begin_range, T end_range, Func && Scorer)
{
// initialise:
auto max_o = Scorer(begin_range);
T i_of_max_o = begin_range;
// now consider the rest of the range:
++begin_range;
for (T i = begin_range; i < end_range; ++i)
{
auto output = Scorer(i);
if (max_o < output)
{
max_o = output;
i_of_max_o = i;
}
}
return i_of_max_o;
}
问题：
我经常使用这样的函数，所以我认为应该有一种 STL 方法来实现它。有吗？
您可以使用 <algorithm> 中定义的 std::max_element。
这将return迭代到指定范围内的最大元素。您可以使用 std::distance.
获取索引
示例复制自 cppreference。
std::vector<int> v{ 3, 1, -14, 1, 5, 9 };
std::vector<int>::iterator result;
result = std::max_element(v.begin(), v.end());
std::cout << "max element at: " << std::distance(v.begin(), result) << '\n';
通常，STL 中的算法处理由迭代器遍历的值序列。他们也倾向于 return 迭代器。这就是它使用的模式。
如果你正在做很多这样的事情，其中你的输入“序列”是一个连续的数字列表，那么你将需要一个迭代器来“迭代”一个序列（w/o 后面的任何存储）。
进行了一些搜索 Boost.CountingIterator，看起来它可以满足您的需求。我相信还有其他类似的人。
警告 - 完全未经测试的代码
auto iter = std::max_element(boost::counting_iterator<int>(5),
boost::counting_iterator<int>(8),
// a comparator that compares two elements
);
return *iter; // should be '6'
正如其他人所观察到的，std::max_element 被定义为获取范围内的最大元素。
在你的例子中，“迭代器”是一个整数，取消引用该迭代器的结果是......一些与输入明显无关的结果（但显然你有一些方法可以得到尽管如此，它仍然有效。
在这种情况下，我可能会定义一个专门的迭代器 class，然后将其与 std::max_element:
一起使用
#include <iostream>
#include <iterator>
#include <algorithm>
// your association function goes here. I've just done something
// where the relationship from input to output isn't necessarily
// immediately obvious
int association_function(int input) {
int a = input * 65537 + 17;
int b = a * a * a;
return b % 127;
}
class yourIterator {
int value;
public:
// create an iterator from an int value
explicit yourIterator(int value) : value(value) {}
// "Deference" the iterator (get the associated value)
int operator*() const { return association_function(value); }
// advance to the next value:
yourIterator operator++(int) {
yourIterator temp(value);
++value;
return temp;
}
yourIterator &operator++() {
++value;
return *this;
}
// compare to another iterator
bool operator==(yourIterator const& other) const { return value == other.value; }
bool operator!=(yourIterator const& other) const { return value != other.value; }
// get the index of the current iterator:
explicit operator int() const { return value; }
};
int main() {
// For demo, print out all the values in a particular range:
std::cout << "values in range: ";
std::copy(yourIterator(5), yourIterator(10), std::ostream_iterator<int>(std::cout, "\t"));
// Find the iterator that gives the largest value:
yourIterator max = std::max_element(yourIterator(5), yourIterator(10));
// print out the value and the index that gave it:
std::cout << "\nLargest element: " << *max << "\n";
std::cout << "index of largest element: " << static_cast<int>(max);
}
当我运行这个时，我得到这样的输出：
values in range: 64 90 105 60 33
Largest element: 105
index of largest element: 7
所以，它似乎工作正常。
如果您需要将其与各种不同的关联函数一起使用，您可能希望将其作为模板参数传递，以保持迭代部分与关联函数分离。
// pass association as a template parameter
template <class Map>
class mappingIterator {
int value;
// create an instance of that type:
Map map;
public:
// use the instance to map from iterator to value:
int operator*() const { return map(value); }
然后你必须将你的关联函数重新转换为适合用作模板参数的形式，例如：
struct association_function {
int operator()(int input) const {
int a = input * 65537 + 17;
int b = a * a * a;
return b % 127;
}
};
然后在 main 中，您可能希望为迭代器定义一个类型并结合关联函数：
using It = mappingIterator<association_function>;
It max = std::max_element(It(5), It(10));
C++20 范围可以做到这一点：
template<typename T, typename F>
T argmax_iota(T begin, T end, F &&score) { // can't really think of a good name for this; maybe it doesn't even deserve its own function
return std::ranges::max(std::views::iota(begin, end), std::less{}, std::ref(score));
// over the values in the range [begin, end) produced by counting (iota)...
// find the one that produces the greatest value (max)...
// when passed to the projection function score...
// with those values under the ordering induced by std::less
}
iota 不会将整个范围存储在任何地方。范围内的迭代器包含一个 T 值，该值在迭代器递增时递增。
为了提高可读性，我正在努力改掉重新发明轮子的习惯。
问题：
考虑一个黑盒函数，Foo，它有一个整数作为输入和输出。我们想要找到最大化输出的输入。考虑所有可能的输入都属于一个连续的整数范围；而且范围足够小，我们可以尝试每一个。
速度很重要，所以我们不使用容器。 即使用户已经为所有可能的输入创建了一个容器，计算下一个输入（++input) 而不是从内存中获取它（缓存未命中）。
示例：
范围：[5, 8)
Foo(5); // 19
Foo(6); // 72
Foo(7); // 31
我们想做一个函数应该 return 6:
InputOfMaxOutputOnRange(5, 8, Foo); // 6
自定义解决方案：
template <typename T, typename Func>
T InputOfMaxOutputOnRange (T begin_range, T end_range, Func && Scorer)
{
// initialise:
auto max_o = Scorer(begin_range);
T i_of_max_o = begin_range;
// now consider the rest of the range:
++begin_range;
for (T i = begin_range; i < end_range; ++i)
{
auto output = Scorer(i);
if (max_o < output)
{
max_o = output;
i_of_max_o = i;
}
}
return i_of_max_o;
}
问题：
我经常使用这样的函数，所以我认为应该有一种 STL 方法来实现它。有吗？
您可以使用 <algorithm> 中定义的 std::max_element。
这将return迭代到指定范围内的最大元素。您可以使用 std::distance.
示例复制自 cppreference。
std::vector<int> v{ 3, 1, -14, 1, 5, 9 };
std::vector<int>::iterator result;
result = std::max_element(v.begin(), v.end());
std::cout << "max element at: " << std::distance(v.begin(), result) << '\n';
通常，STL 中的算法处理由迭代器遍历的值序列。他们也倾向于 return 迭代器。这就是它使用的模式。
如果你正在做很多这样的事情，其中你的输入“序列”是一个连续的数字列表，那么你将需要一个迭代器来“迭代”一个序列（w/o 后面的任何存储）。
进行了一些搜索 Boost.CountingIterator，看起来它可以满足您的需求。我相信还有其他类似的人。
警告 - 完全未经测试的代码
auto iter = std::max_element(boost::counting_iterator<int>(5),
boost::counting_iterator<int>(8),
// a comparator that compares two elements
);
return *iter; // should be '6'
正如其他人所观察到的，std::max_element 被定义为获取范围内的最大元素。
在你的例子中，“迭代器”是一个整数，取消引用该迭代器的结果是......一些与输入明显无关的结果（但显然你有一些方法可以得到尽管如此，它仍然有效。
在这种情况下，我可能会定义一个专门的迭代器 class，然后将其与 std::max_element:
#include <iostream>
#include <iterator>
#include <algorithm>
// your association function goes here. I've just done something
// where the relationship from input to output isn't necessarily
// immediately obvious
int association_function(int input) {
int a = input * 65537 + 17;
int b = a * a * a;
return b % 127;
}
class yourIterator {
int value;
public:
// create an iterator from an int value
explicit yourIterator(int value) : value(value) {}
// "Deference" the iterator (get the associated value)
int operator*() const { return association_function(value); }
// advance to the next value:
yourIterator operator++(int) {
yourIterator temp(value);
++value;
return temp;
}
yourIterator &operator++() {
++value;
return *this;
}
// compare to another iterator
bool operator==(yourIterator const& other) const { return value == other.value; }
bool operator!=(yourIterator const& other) const { return value != other.value; }
// get the index of the current iterator:
explicit operator int() const { return value; }
};
int main() {
// For demo, print out all the values in a particular range:
std::cout << "values in range: ";
std::copy(yourIterator(5), yourIterator(10), std::ostream_iterator<int>(std::cout, "\t"));
// Find the iterator that gives the largest value:
yourIterator max = std::max_element(yourIterator(5), yourIterator(10));
// print out the value and the index that gave it:
std::cout << "\nLargest element: " << *max << "\n";
std::cout << "index of largest element: " << static_cast<int>(max);
}
当我运行这个时，我得到这样的输出：
values in range: 64 90 105 60 33
Largest element: 105
index of largest element: 7
所以，它似乎工作正常。
如果您需要将其与各种不同的关联函数一起使用，您可能希望将其作为模板参数传递，以保持迭代部分与关联函数分离。
// pass association as a template parameter
template <class Map>
class mappingIterator {
int value;
// create an instance of that type:
Map map;
public:
// use the instance to map from iterator to value:
int operator*() const { return map(value); }
然后你必须将你的关联函数重新转换为适合用作模板参数的形式，例如：
struct association_function {
int operator()(int input) const {
int a = input * 65537 + 17;
int b = a * a * a;
return b % 127;
}
};
然后在 main 中，您可能希望为迭代器定义一个类型并结合关联函数：
using It = mappingIterator<association_function>;
It max = std::max_element(It(5), It(10));
C++20 范围可以做到这一点：
template<typename T, typename F>
T argmax_iota(T begin, T end, F &&score) { // can't really think of a good name for this; maybe it doesn't even deserve its own function
return std::ranges::max(std::views::iota(begin, end), std::less{}, std::ref(score));
// over the values in the range [begin, end) produced by counting (iota)...
// find the one that produces the greatest value (max)...
// when passed to the projection function score...
// with those values under the ordering induced by std::less
}
iota 不会将整个范围存储在任何地方。范围内的迭代器包含一个 T 值，该值在迭代器递增时递增。