diff options
Diffstat (limited to 'libstdc++-v3')
| -rw-r--r-- | libstdc++-v3/ChangeLog | 8 | ||||
| -rw-r--r-- | libstdc++-v3/include/bits/stl_algobase.h | 91 | ||||
| -rw-r--r-- | libstdc++-v3/testsuite/performance/25_algorithms/lexicographical_compare.cc | 55 |
3 files changed, 133 insertions, 21 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index b67328c..8af41ef 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,11 @@ +2007-07-30 Paolo Carlini <pcarlini@suse.de> + + PR libstdc++/32908 + * include/bits/stl_algobase.h (struct __lc_rai): New. + (lexicographical_compare(_II1, _II1, _II2, _II2), + lexicographical_compare(_II1, _II1, _II2, _II2, _Compare)): Use it. + * testsuite/performance/25_algorithms/lexicographical_compare.cc: New. + 2007-07-27 Paolo Carlini <pcarlini@suse.de> PR libstdc++/32907 diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h index fd9592a..4146b21 100644 --- a/libstdc++-v3/include/bits/stl_algobase.h +++ b/libstdc++-v3/include/bits/stl_algobase.h @@ -778,6 +778,43 @@ _GLIBCXX_BEGIN_NAMESPACE(std) return true; } + + template<typename, typename> + struct __lc_rai + { + template<typename _II1, typename _II2> + static _II1 + __newlast1(_II1, _II1 __last1, _II2, _II2) + { return __last1; } + + template<typename _II> + static bool + __cnd2(_II __first, _II __last) + { return __first != __last; } + }; + + template<> + struct __lc_rai<random_access_iterator_tag, + random_access_iterator_tag> + { + template<typename _RAI1, typename _RAI2> + static _RAI1 + __newlast1(_RAI1 __first1, _RAI1 __last1, + _RAI2 __first2, _RAI2 __last2) + { + const typename iterator_traits<_RAI1>::difference_type + __diff1 = __last1 - __first1; + const typename iterator_traits<_RAI2>::difference_type + __diff2 = __last2 - __first2; + return __diff2 < __diff1 ? __first1 + __diff2 : __last1; + } + + template<typename _RAI> + static bool + __cnd2(_RAI, _RAI) + { return true; } + }; + /** * @brief Performs "dictionary" comparison on ranges. * @param first1 An input iterator. @@ -792,24 +829,30 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * (Quoted from [25.3.8]/1.) If the iterators are all character pointers, * then this is an inline call to @c memcmp. */ - template<typename _InputIterator1, typename _InputIterator2> + template<typename _II1, typename _II2> bool - lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2) + lexicographical_compare(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2) { + typedef typename iterator_traits<_II1>::iterator_category _Category1; + typedef typename iterator_traits<_II2>::iterator_category _Category2; + // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) - __glibcxx_function_requires(_LessThanOpConcept< - typename iterator_traits<_InputIterator1>::value_type, - typename iterator_traits<_InputIterator2>::value_type>) - __glibcxx_function_requires(_LessThanOpConcept< - typename iterator_traits<_InputIterator2>::value_type, - typename iterator_traits<_InputIterator1>::value_type>) + typedef typename iterator_traits<_II1>::value_type _ValueType1; + typedef typename iterator_traits<_II2>::value_type _ValueType2; + __glibcxx_function_requires(_InputIteratorConcept<_II1>) + __glibcxx_function_requires(_InputIteratorConcept<_II2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>) + __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>) __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); - for (; __first1 != __last1 && __first2 != __last2; + __last1 = __lc_rai<_Category1, _Category2>::__newlast1(__first1, + __last1, + __first2, + __last2); + for (; __first1 != __last1 + && __lc_rai<_Category1, _Category2>::__cnd2(__first2, __last2); ++__first1, ++__first2) { if (*__first1 < *__first2) @@ -829,23 +872,29 @@ _GLIBCXX_BEGIN_NAMESPACE(std) * @param comp A @link s20_3_3_comparisons comparison functor@endlink. * @return A boolean true or false. * - * The same as the four-parameter @c lexigraphical_compare, but uses the + * The same as the four-parameter @c lexicographical_compare, but uses the * comp parameter instead of @c <. */ - template<typename _InputIterator1, typename _InputIterator2, - typename _Compare> + template<typename _II1, typename _II2, typename _Compare> bool - lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, - _Compare __comp) + lexicographical_compare(_II1 __first1, _II1 __last1, + _II2 __first2, _II2 __last2, _Compare __comp) { + typedef typename iterator_traits<_II1>::iterator_category _Category1; + typedef typename iterator_traits<_II2>::iterator_category _Category2; + // concept requirements - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>) - __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>) + __glibcxx_function_requires(_InputIteratorConcept<_II1>) + __glibcxx_function_requires(_InputIteratorConcept<_II2>) __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); - for (; __first1 != __last1 && __first2 != __last2; + __last1 = __lc_rai<_Category1, _Category2>::__newlast1(__first1, + __last1, + __first2, + __last2); + for (; __first1 != __last1 + && __lc_rai<_Category1, _Category2>::__cnd2(__first2, __last2); ++__first1, ++__first2) { if (__comp(*__first1, *__first2)) diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/lexicographical_compare.cc b/libstdc++-v3/testsuite/performance/25_algorithms/lexicographical_compare.cc new file mode 100644 index 0000000..b983881 --- /dev/null +++ b/libstdc++-v3/testsuite/performance/25_algorithms/lexicographical_compare.cc @@ -0,0 +1,55 @@ +// Copyright (C) 2007 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 2, 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 COPYING. If not, write to the Free +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +#include <vector> +#include <testsuite_performance.h> + +// libstdc++/32908 +int main() +{ + using namespace __gnu_test; + + time_counter time; + resource_counter resource; + + int cnt = 0; + std::vector<int> a(10000), b(10000); + + start_counters(time, resource); + for (int i = 0; i < 100000; ++i) + { + if (a < b) + ++cnt; + if (a > b) + ++cnt; + } + stop_counters(time, resource); + report_performance(__FILE__, "", time, resource); + clear_counters(time, resource); + + return cnt; +} |