algorithm - find_if 的两个条件

Question

在 std::vector<unsigned int> 中，我想找到最大数小于某个数的元素的位置。例如:

v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

我想找到一个最大小于 8 的数字。那个数字是 7。

以下代码不正确，但这可能是我想要得到的。

std::vector<unsigned int>::iterator pnt = std::find_if (v.begin(), v.end(), [](const unsigned int& x) { return x < 8; && x == MAX; });

Answer 1

如果你的 vector 总是排序的，那么你可以用对数复杂度来做

auto it = std::lower_bound(v.begin(), v.end(), 8); // first value >= 8
auto m = *((it != v.begin())? --it : it);         

如果您的 vector 未排序，但可以修改，您可以分两步完成:

auto it = std::partition(v.begin(), v.end(), [](int x) { x < 8 });
auto m = *(it != v.begin())? std::max_element(v.begin(), it) : it);

如果你不能修改你的 vector ，你可以手工做

auto max = 0;
for (elem: v) {
   if (elem < 8) 
       m = std::max(elem, m);
}
// m is now the max of all elements < 8

最后两种方法都具有线性复杂度。后者可以通过使用 filter_iterator 来概括。来自 Boost.Iterator图书馆，但你已经深入到模板领域，所以只有当你反复需要这种魔法时才这样做。