(C++) std::upper_bound

 

std::upper_bound is an algorithm that returns the location where a given element can be inserted in a sorted container without violating the order.

 

std::upper_bound is defined in the header file algorithm.h.

 

---

#include <algorithm> #include <iostream> #include <vector> int main() {   std::vector<int> v;   v.push_back(1);   v.push_back(4);   v.push_back(9);   v.push_back(9);   v.push_back(16);   const std::size_t sz = v.size();   for (std::size_t i=0; i!=sz; ++i)   {     std::cout << "v[" << i << "] = " << v[i] << std::endl;   }   for (int i=0; i!=20; ++i)   {     const std::vector<int>::iterator my_iterator = std::upper_bound(v.begin(),v.end(),i);     const int index = std::distance(v.begin(),my_iterator);     std::cout       << "The value '" << i       << "' can be safely inserted at index "       << index << " without violating the order"       << std::endl;   } }

 

Screen output:

 

---

v[0] = 1 v[1] = 4 v[2] = 9 v[3] = 9 v[4] = 16 The value '0' can be safely inserted at index 0 without violating the order The value '1' can be safely inserted at index 1 without violating the order The value '2' can be safely inserted at index 1 without violating the order The value '3' can be safely inserted at index 1 without violating the order The value '4' can be safely inserted at index 2 without violating the order The value '5' can be safely inserted at index 2 without violating the order The value '6' can be safely inserted at index 2 without violating the order The value '7' can be safely inserted at index 2 without violating the order The value '8' can be safely inserted at index 2 without violating the order The value '9' can be safely inserted at index 4 without violating the order The value '10' can be safely inserted at index 4 without violating the order The value '11' can be safely inserted at index 4 without violating the order The value '12' can be safely inserted at index 4 without violating the order The value '13' can be safely inserted at index 4 without violating the order The value '14' can be safely inserted at index 4 without violating the order The value '15' can be safely inserted at index 4 without violating the order The value '16' can be safely inserted at index 5 without violating the order The value '17' can be safely inserted at index 5 without violating the order The value '18' can be safely inserted at index 5 without violating the order The value '19' can be safely inserted at index 5 without violating the order

 

 

 

 

 

External links

 

• SGI page about std::upper_bound