libstdc++-v3/testsuite/25_algorithms/nth_element/2.cc

   1 // Copyright (C) 2006-2025 Free Software Foundation, Inc.
   2 //
   3 // This file is part of the GNU ISO C++ Library.  This library is free
   4 // software; you can redistribute it and/or modify it under the
   5 // terms of the GNU General Public License as published by the
   6 // Free Software Foundation; either version 3, or (at your option)
   7 // any later version.
   8
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13
  14 // You should have received a copy of the GNU General Public License along
  15 // with this library; see the file COPYING3.  If not see
  16 // <http://www.gnu.org/licenses/>.
  17
  18 // 25.3.2 [lib.alg.nth.element]
  19
  20 // { dg-options "-DMAX_SIZE=256" { target simulator } }
  21
  22 #ifndef MAX_SIZE
  23 #define MAX_SIZE (1 << 10)
  24 #endif
  25
  26 #include <vector>
  27 #include <algorithm>
  28 #include <testsuite_hooks.h>
  29
  30 void
  31 test_set(std::vector<unsigned>& v, unsigned size)
  32 {
  33   v.clear();
  34
  35   for (unsigned i = 0; i < size; i += 4)
  36     {
  37       v.push_back(i / 2);
  38       v.push_back((size - 2) - (i / 2));
  39     }
  40   for (unsigned i = 1; i < size; i += 2)
  41     v.push_back(i);
  42 }
  43
  44 void
  45 do_test01(unsigned size)
  46 {
  47   std::vector<unsigned> v, s;
  48
  49   for (unsigned j = 0; j < size; ++j)
  50     {
  51       test_set(v, size);
  52       s = v;
  53       std::sort(s.begin(), s.end());
  54
  55       std::nth_element(v.begin(), v.begin() + j, v.end());
  56
  57       VERIFY( v[j] == s[j] );
  58
  59       for (unsigned i = 0; i < j; ++i)
  60         VERIFY( !(v[j] < v[i]) );
  61
  62       for (unsigned i = j; i < v.size(); ++i)
  63         VERIFY( !(v[i] < v[j]) );
  64     }
  65 }
  66
  67 void
  68 test01()
  69 {
  70   for (unsigned size = 4; size <= MAX_SIZE; size <<= 1)
  71     do_test01(size);
  72 }
  73
  74 int main()
  75 {
  76   test01();
  77   return 0;
  78 }