libstdc++-v3/testsuite/performance/25_algorithms/nth_element_worst_case.cc

   1 // Copyright (C) 2006-2023 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
  19 #include <vector>
  20 #include <algorithm>
  21 #include <testsuite_performance.h>
  22
  23 int main()
  24 {
  25   using namespace __gnu_test;
  26
  27   time_counter time;
  28   resource_counter resource;
  29
  30   const int max_size = 8192;
  31
  32   std::vector<int> v[max_size];
  33
  34   for (int i = 0; i < max_size; ++i)
  35     {
  36       for (int j = 0; j < i; j += 4)
  37         {
  38           v[i].push_back(j / 2);
  39           v[i].push_back((i - 2) - (j / 2));
  40         }
  41
  42       for (int j = 1; j < i; j += 2)
  43         v[i].push_back(j);
  44     }
  45
  46   start_counters(time, resource);
  47   for (int i = 0; i < max_size; ++i)
  48     std::nth_element(v[i].begin(), v[i].begin() + i, v[i].end());
  49   stop_counters(time, resource);
  50   report_performance(__FILE__, "", time, resource);
  51
  52   return 0;
  53 }