Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Elegant way to find closest value in a vector from above

Tags:

c++

algorithm

stl

I need a function that takes a vector (assumed to be sorted), and a value, and returns the closest number that's [edit] greater than less 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:

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.

like image 434
josmith42 Avatar asked Dec 27 '11 17:12

josmith42


People also ask

How do I find the nearest value in R?

To find the row corresponding to a nearest value in an R data frame, we can use which. min function after getting the absolute difference between the value and the column along with single square brackets for subsetting the row.

How do I find the closest number in an array C++?

So if the array is like [2, 5, 6, 7, 8, 8, 9] and the target number is 4, then closest element is 5. We can solve this by traversing through the given array and keep track of absolute difference of current element with every element. Finally return the element that has minimum absolute difference.

How do you find the end element of a vector?

If you want to access the last element of your vector use vec. back() , which returns a reference (and not iterator). Do note however that if the vector is empty, this will lead to an undefined behavior; most likely a crash.


2 Answers

For reminder:

  • std::lower_bound: returns the first value that does not compare less
  • std::upper_bound: returns the first value that compares strictly greater

From your description, std::lower_bound already looks like the perfect fit, what is wrong with:

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 
like image 93
Matthieu M. Avatar answered Sep 20 '22 11:09

Matthieu M.


You can only use std::lower_bound and std::upper_bound with 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.)

like image 32
MSN Avatar answered Sep 17 '22 11:09

MSN