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

Go back to Richel Bilderbeek's C++ page.

Go back to Richel Bilderbeek's homepage.

(C++) std::upper_bound

External links