C++ 从上方找到向量中最接近值的优雅方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8647635/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Elegant way to find closest value in a vector from above
提问by josmith42
I need a function that takes a vector (assumed to be sorted), and a value, and returns the closest number that's [edit] greater thanless than or equal to that number, preferably using an algorithm from the STL. I have come up with a solution using std::lower_bound(), but it seems kludgy and ugly:
我需要一个函数，它接受一个向量（假设已排序）和一个值，并返回 [edit]大于或等于该数字的最接近数字，最好使用 STL 中的算法。我想出了一个使用 std::lower_bound() 的解决方案，但它看起来笨拙而丑陋：
struct ClosestCmp {
bool operator()(const int & x, const int & y) { return x > y; }
};
// vec is assumed to be sorted
int closest(const std::vector<int> & vec, int value)
{
std::vector<int>::const_reverse_iterator cri =
std::lower_bound(vec.rbegin(), vec.rend(), value, ClosestCmp());
if (cri != vec.rend()) {
return *cri;
}
return -1;
}
// ...
vec.push_back(1);
vec.push_back(2);
vec.push_back(4);
vec.push_back(5);
std::cout << closest(vec, 2) << "\n"; // Should ouput "2"
std::cout << closest(vec, 3) << "\n"; // Should ouput "2"
std::cout << closest(vec, 4) << "\n"; // Should ouput "4"
Can anyone suggest a way that's more elegant, maybe using an STL algorithm without needing a comparison function or a reverse iterator? I have looked in the STL, but haven't been able to find a better solution than this.
任何人都可以提出一种更优雅的方法，也许使用 STL 算法而不需要比较函数或反向迭代器？我查看了 STL，但找不到比这更好的解决方案。
采纳答案by MSN
You can only use std::lower_boundand std::upper_boundwith binary predicates that match the order of the container. So, you can't sort by <and then use a different binary predicate (say <=or >). So your "kludge" is actually the correct thing to do. The sorted vector in reverse is the ordering criteria you want to use to find the element less than or equal to the value. (Otherwise, if you were actually searching for the value greater than or equal to, you could just use std::lower_bound.)
您只能使用std::lower_bound与std::upper_bound容器顺序匹配的二进制谓词。因此，您不能通过排序<然后使用不同的二元谓词（比如<=或>）。所以你的“kludge”实际上是正确的做法。反向排序向量是您要用于查找小于或等于该值的元素的排序标准。（否则，如果您实际上是在搜索大于或等于的值，则可以使用std::lower_bound。）
回答by Matthieu M.
For reminder:
提醒：
std::lower_bound: returns the first value that does not compare lessstd::upper_bound: returns the first value that compares strictly greater
std::lower_bound: 返回不比较less的第一个值std::upper_bound: 返回第一个比较严格的值
From your description, std::lower_boundalready looks like the perfect fit, what is wrong with:
从你的描述来看，std::lower_bound已经很合身了，有什么问题：
int closest(std::vector<int> const& vec, int value) {
auto const it = std::lower_bound(vec.begin(), vec.end(), value);
if (it == vec.end()) { return -1; }
return *it;
}
Which is used as:
用作：
int main() {
std::vector<int> vec;
vec.push_back(2);
vec.push_back(4);
std::cout << closest(vec, 2) << "\n";
std::cout << closest(vec, 3) << "\n";
std::cout << closest(vec, 4) << "\n";
}
Output:
输出：
2
4
4
回答by Robert
Requires C++11:
需要 C++11：
template<typename InputIterator, typename ValueType>
InputIterator closest(InputIterator first, InputIterator last, ValueType value)
{
return std::min_element(first, last, [&](ValueType x, ValueType y)
{
return std::abs(x - value) < std::abs(y - value);
});
}
回答by Alexandr Priymak
For the largest which is less or equal one can use this function
对于小于或等于的最大者可以使用此功能
int closest(std::vector<int> const& vec, int value) {
auto const it = std::lower_bound(vec.begin(), vec.end(), value);
if (it == vec.begin()) { return -1; }
else return *(it - 1);
}
