test/std/algorithms/alg.sorting/alg.binary.search/upper.bound/upper_bound.pass.cpp

   1 //===----------------------------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is dual licensed under the MIT and the University of Illinois Open
   6 // Source Licenses. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 // <algorithm>
  11
  12 // template<ForwardIterator Iter, class T>
  13 //   requires HasLess<T, Iter::value_type>
  14 //   Iter
  15 //   upper_bound(Iter first, Iter last, const T& value);
  16
  17 #include <algorithm>
  18 #include <vector>
  19 #include <cassert>
  20 #include <cstddef>
  21
  22 #include "test_iterators.h"
  23
  24 template <class Iter, class T>
  25 void
  26 test(Iter first, Iter last, const T& value)
  27 {
  28     Iter i = std::upper_bound(first, last, value);
  29     for (Iter j = first; j != i; ++j)
  30         assert(!(value < *j));
  31     for (Iter j = i; j != last; ++j)
  32         assert(value < *j);
  33 }
  34
  35 template <class Iter>
  36 void
  37 test()
  38 {
  39     const unsigned N = 1000;
  40     const int M = 10;
  41     std::vector<int> v(N);
  42     int x = 0;
  43     for (std::size_t i = 0; i < v.size(); ++i)
  44     {
  45         v[i] = x;
  46         if (++x == M)
  47             x = 0;
  48     }
  49     std::sort(v.begin(), v.end());
  50     for (x = 0; x <= M; ++x)
  51         test(Iter(v.data()), Iter(v.data()+v.size()), x);
  52 }
  53
  54 int main()
  55 {
  56     int d[] = {0, 1, 2, 3};
  57     for (int* e = d; e <= d+4; ++e)
  58         for (int x = -1; x <= 4; ++x)
  59             test(d, e, x);
  60
  61     test<forward_iterator<const int*> >();
  62     test<bidirectional_iterator<const int*> >();
  63     test<random_access_iterator<const int*> >();
  64     test<const int*>();
  65 }