===================================================================
@@ -72,25 +72,27 @@
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
- /// Swaps the median value of *__a, *__b and *__c under __comp to *__a
+ /// Swaps the median value of *__a, *__b and *__c under __comp to *__result
template<typename _Iterator, typename _Compare>
void
- __move_median_first(_Iterator __a, _Iterator __b, _Iterator __c,
- _Compare __comp)
+ __move_median_to_first(_Iterator __result,_Iterator __a, _Iterator __b,
+ _Iterator __c, _Compare __comp)
{
if (__comp(__a, __b))
{
if (__comp(__b, __c))
- std::iter_swap(__a, __b);
+ std::iter_swap(__result, __b);
else if (__comp(__a, __c))
- std::iter_swap(__a, __c);
+ std::iter_swap(__result, __c);
+ else
+ std::iter_swap(__result, __a);
}
else if (__comp(__a, __c))
- return;
+ std::iter_swap(__result, __a);
else if (__comp(__b, __c))
- std::iter_swap(__a, __c);
+ std::iter_swap(__result, __c);
else
- std::iter_swap(__a, __b);
+ std::iter_swap(__result, __b);
}
/// This is an overload used by find algos for the Input Iterator case.
@@ -1915,7 +1917,8 @@
_RandomAccessIterator __last, _Compare __comp)
{
_RandomAccessIterator __mid = __first + (__last - __first) / 2;
- std::__move_median_first(__first, __mid, (__last - 1), __comp);
+ std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2),
+ __comp);
return std::__unguarded_partition(__first + 1, __last, __first, __comp);
}
===================================================================
@@ -0,0 +1,65 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include <algorithm>
+#include <testsuite_performance.h>
+
+int main()
+{
+ using namespace __gnu_test;
+
+ time_counter time;
+ resource_counter resource;
+
+ const int max_size = 10000000;
+
+ std::vector<int> v(max_size);
+
+ for (int i = 0; i < max_size; ++i)
+ v[i] = -i;
+
+ start_counters(time, resource);
+ std::sort(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "reverse", time, resource);
+ clear_counters(time, resource);
+
+ for (int i = 0; i < max_size; ++i)
+ v[i] = i;
+
+ start_counters(time, resource);
+ std::sort(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "forwards", time, resource);
+ clear_counters(time, resource);
+
+ // a simple psuedo-random series which does not rely on rand() and friends
+ v[0] = 0;
+ for (int i = 1; i < max_size; ++i)
+ v[i] = (v[i-1] + 110211473) * 745988807;
+
+ start_counters(time, resource);
+ std::sort(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "random", time, resource);
+
+ return 0;
+}
===================================================================
@@ -0,0 +1,73 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include <algorithm>
+#include <testsuite_performance.h>
+
+int main()
+{
+ using namespace __gnu_test;
+
+ time_counter time;
+ resource_counter resource;
+
+ const int max_size = 10000000;
+
+ std::vector<int> v(max_size);
+
+ for (int i = 0; i < max_size; ++i)
+ v[i] = -i;
+
+ start_counters(time, resource);
+ std::make_heap(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "make_heap_reverse", time, resource);
+ clear_counters(time, resource);
+
+ for (int i = 0; i < max_size; ++i)
+ v[i] = i;
+
+ start_counters(time, resource);
+ std::make_heap(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "make_heap_forwards", time, resource);
+ clear_counters(time, resource);
+
+ // a simple psuedo-random series which does not rely on rand() and friends
+ v[0] = 0;
+ for (int i = 1; i < max_size; ++i)
+ v[i] = (v[i-1] + 110211473) * 745988807;
+
+ start_counters(time, resource);
+ std::make_heap(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "make_heap_random", time, resource);
+
+
+ start_counters(time, resource);
+ std::sort_heap(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "sort_heap", time, resource);
+ clear_counters(time, resource);
+
+ return 0;
+}
===================================================================
@@ -0,0 +1,65 @@
+// Copyright (C) 2013 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <vector>
+#include <algorithm>
+#include <testsuite_performance.h>
+
+int main()
+{
+ using namespace __gnu_test;
+
+ time_counter time;
+ resource_counter resource;
+
+ const int max_size = 10000000;
+
+ std::vector<int> v(max_size);
+
+ for (int i = 0; i < max_size; ++i)
+ v[i] = -i;
+
+ start_counters(time, resource);
+ std::stable_sort(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "reverse", time, resource);
+ clear_counters(time, resource);
+
+ for (int i = 0; i < max_size; ++i)
+ v[i] = i;
+
+ start_counters(time, resource);
+ std::stable_sort(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "forwards", time, resource);
+ clear_counters(time, resource);
+
+ // a simple psuedo-random series which does not rely on rand() and friends
+ v[0] = 0;
+ for (int i = 1; i < max_size; ++i)
+ v[i] = (v[i-1] + 110211473) * 745988807;
+
+ start_counters(time, resource);
+ std::stable_sort(v.begin(), v.end());
+ stop_counters(time, resource);
+
+ report_performance(__FILE__, "random", time, resource);
+
+ return 0;
+}