Patchwork Remove algo logic duplication Round 3

login
register
mail settings
Submitter François Dumont
Date Sept. 28, 2013, 8:43 p.m.
Message ID <52473F85.1030508@gmail.com>
Download mbox | patch
Permalink /patch/278772/
State New
Headers show

Comments

François Dumont - Sept. 28, 2013, 8:43 p.m.
On 09/28/2013 02:45 AM, Paolo Carlini wrote:
> .. by the way, in the current stl_algo* I'm still seeing many, many, 
> functions which should be inline not declared as such: each function 
> which has a few __glibcxx_requires* at the beginning (which normally 
> boil down to nothing) and then forwards to a std::__* helper should be 
> inline.
>

Fixed with the attached patch tested under Linux x86_64.

I also get your remark about the open round bracket, I didn't know that 
round bracket was the other name for parentheses ! I also fix the one 
you pointed me, I will be more careful next  time.

2013-09-28  François Dumont  <fdumont@gcc.gnu.org>

     * include/bits/stl_algo.h (remove_copy, remove_copy_if): Declare
     inline.
     (rotate_copy, stable_partition, partial_sort_copy): Likewise.
     (lower_bound, upper_bound, equal_range, inplace_merge): Likewise.
     (includes, next_permutation, prev_permutation): Likewise.
     (replace_copy, replace_copy_if, is_sorted_until): Likewise.
     (minmax_element, is_permutation, adjacent_find): Likewise.
     (count, count_if, search, search_n, merge): Likewise.
     (set_intersection, set_difference): Likewise.
     (set_symmetric_difference, min_element, max_element): Likewise.
     * include/bits/stl_algobase.h (lower_bound): Likewise.
     (lexicographical_compare, mismatch): Likewise.

I consider it trivial enough to commit it.

François
Paolo Carlini - Sept. 29, 2013, 7:20 p.m.
Hi,

"François Dumont" <frs.dumont@gmail.com> ha scritto:
>I also get your remark about the open round bracket, I didn't know that
>
>round bracket was the other name for parentheses ! I also fix the one
>you pointed me, I will be more careful next  time.

No problem ;) For your linguistic curiosity, I often find myself using round bracket: I find it more precise, less vague. Not 100% sure about french, but in italian we of course have the equivalent of parentheses but it's generic, kids soon learn about round, square and curly variants. English is probably more precise, it usefully provides 3 different words: parentheses, brackets and braces, which often, outside a technical context, should be clear enough, without further qualifications.

Thanks!
Paolo

Patch

Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h	(revision 203005)
+++ include/bits/stl_algo.h	(working copy)
@@ -661,7 +661,7 @@ 
    *  are copied is unchanged.
   */
   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
-    _OutputIterator
+    inline _OutputIterator
     remove_copy(_InputIterator __first, _InputIterator __last,
 		_OutputIterator __result, const _Tp& __value)
     {
@@ -694,7 +694,7 @@ 
   */
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _Predicate>
-    _OutputIterator
+    inline _OutputIterator
     remove_copy_if(_InputIterator __first, _InputIterator __last,
 		   _OutputIterator __result, _Predicate __pred)
     {
@@ -1414,9 +1414,8 @@ 
       __glibcxx_requires_valid_range(__first, __middle);
       __glibcxx_requires_valid_range(__middle, __last);
 
-      typedef typename iterator_traits<_ForwardIterator>::iterator_category
-	_IterType;
-      std::__rotate(__first, __middle, __last, _IterType());
+      std::__rotate(__first, __middle, __last,
+		    std::__iterator_category(__first));
     }
 
   /**
@@ -1440,7 +1439,7 @@ 
    *  for each @p n in the range @p [0,__last-__first).
   */
   template<typename _ForwardIterator, typename _OutputIterator>
-    _OutputIterator
+    inline _OutputIterator
     rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
                 _ForwardIterator __last, _OutputIterator __result)
     {
@@ -1647,7 +1646,7 @@ 
    *  relative ordering after calling @p stable_partition().
   */
   template<typename _ForwardIterator, typename _Predicate>
-    _ForwardIterator
+    inline _ForwardIterator
     stable_partition(_ForwardIterator __first, _ForwardIterator __last,
 		     _Predicate __pred)
     {
@@ -1733,7 +1732,7 @@ 
    *  The value returned is @p __result_first+N.
   */
   template<typename _InputIterator, typename _RandomAccessIterator>
-    _RandomAccessIterator
+    inline _RandomAccessIterator
     partial_sort_copy(_InputIterator __first, _InputIterator __last,
 		      _RandomAccessIterator __result_first,
 		      _RandomAccessIterator __result_last)
@@ -1782,7 +1781,7 @@ 
   */
   template<typename _InputIterator, typename _RandomAccessIterator,
 	   typename _Compare>
-    _RandomAccessIterator
+    inline _RandomAccessIterator
     partial_sort_copy(_InputIterator __first, _InputIterator __last,
 		      _RandomAccessIterator __result_first,
 		      _RandomAccessIterator __result_last,
@@ -2016,7 +2015,7 @@ 
    *  the function used for the initial sort.
   */
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
-    _ForwardIterator
+    inline _ForwardIterator
     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val, _Compare __comp)
     {
@@ -2073,7 +2072,7 @@ 
    *  @ingroup binary_search_algorithms
   */
   template<typename _ForwardIterator, typename _Tp>
-    _ForwardIterator
+    inline _ForwardIterator
     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val)
     {
@@ -2105,7 +2104,7 @@ 
    *  the function used for the initial sort.
   */
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
-    _ForwardIterator
+    inline _ForwardIterator
     upper_bound(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val, _Compare __comp)
     {
@@ -2179,7 +2178,7 @@ 
    *  but does not actually call those functions.
   */
   template<typename _ForwardIterator, typename _Tp>
-    pair<_ForwardIterator, _ForwardIterator>
+    inline pair<_ForwardIterator, _ForwardIterator>
     equal_range(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val)
     {
@@ -2216,7 +2215,7 @@ 
    *  but does not actually call those functions.
   */
   template<typename _ForwardIterator, typename _Tp, typename _Compare>
-    pair<_ForwardIterator, _ForwardIterator>
+    inline pair<_ForwardIterator, _ForwardIterator>
     equal_range(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val, _Compare __comp)
     {
@@ -2580,7 +2579,7 @@ 
    *  distance(__first,__last).
   */
   template<typename _BidirectionalIterator>
-    void
+    inline void
     inplace_merge(_BidirectionalIterator __first,
 		  _BidirectionalIterator __middle,
 		  _BidirectionalIterator __last)
@@ -2620,7 +2619,7 @@ 
    *  the function used for the initial sort.
   */
   template<typename _BidirectionalIterator, typename _Compare>
-    void
+    inline void
     inplace_merge(_BidirectionalIterator __first,
 		  _BidirectionalIterator __middle,
 		  _BidirectionalIterator __last,
@@ -2827,7 +2826,7 @@ 
    *  returned.
   */
   template<typename _InputIterator1, typename _InputIterator2>
-    bool
+    inline bool
     includes(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2, _InputIterator2 __last2)
     {
@@ -2870,7 +2869,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _Compare>
-    bool
+    inline bool
     includes(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2, _InputIterator2 __last2,
 	     _Compare __comp)
@@ -2951,7 +2950,7 @@ 
    *  is the largest of the set, the smallest is generated and false returned.
   */
   template<typename _BidirectionalIterator>
-    bool
+    inline bool
     next_permutation(_BidirectionalIterator __first,
 		     _BidirectionalIterator __last)
     {
@@ -2982,7 +2981,7 @@ 
    *  smallest is generated and false returned.
   */
   template<typename _BidirectionalIterator, typename _Compare>
-    bool
+    inline bool
     next_permutation(_BidirectionalIterator __first,
 		     _BidirectionalIterator __last, _Compare __comp)
     {
@@ -3049,7 +3048,7 @@ 
    *  returned.
   */
   template<typename _BidirectionalIterator>
-    bool
+    inline bool
     prev_permutation(_BidirectionalIterator __first,
 		     _BidirectionalIterator __last)
     {
@@ -3080,7 +3079,7 @@ 
    *  the largest is generated and false returned.
   */
   template<typename _BidirectionalIterator, typename _Compare>
-    bool
+    inline bool
     prev_permutation(_BidirectionalIterator __first,
 		     _BidirectionalIterator __last, _Compare __comp)
     {
@@ -3129,7 +3128,7 @@ 
    *  equal to @p __old_value with @p __new_value.
   */
   template<typename _InputIterator, typename _OutputIterator, typename _Tp>
-    _OutputIterator
+    inline _OutputIterator
     replace_copy(_InputIterator __first, _InputIterator __last,
 		 _OutputIterator __result,
 		 const _Tp& __old_value, const _Tp& __new_value)
@@ -3164,7 +3163,7 @@ 
   */
   template<typename _InputIterator, typename _OutputIterator,
 	   typename _Predicate, typename _Tp>
-    _OutputIterator
+    inline _OutputIterator
     replace_copy_if(_InputIterator __first, _InputIterator __last,
 		    _OutputIterator __result,
 		    _Predicate __pred, const _Tp& __new_value)
@@ -3245,7 +3244,7 @@ 
    *           for which the range [__first, i) is sorted.
   */
   template<typename _ForwardIterator>
-    _ForwardIterator
+    inline _ForwardIterator
     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
     {
       // concept requirements
@@ -3268,7 +3267,7 @@ 
    *           for which the range [__first, i) is sorted.
   */
   template<typename _ForwardIterator, typename _Compare>
-    _ForwardIterator
+    inline _ForwardIterator
     is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
 		    _Compare __comp)
     {
@@ -3390,7 +3389,7 @@ 
    *           such that no other element in the range is larger.
   */
   template<typename _ForwardIterator>
-    pair<_ForwardIterator, _ForwardIterator>
+    inline pair<_ForwardIterator, _ForwardIterator>
     minmax_element(_ForwardIterator __first, _ForwardIterator __last)
     {
       // concept requirements
@@ -3416,7 +3415,7 @@ 
    *           such that no other element in the range is larger.
   */
   template<typename _ForwardIterator, typename _Compare>
-    pair<_ForwardIterator, _ForwardIterator>
+    inline pair<_ForwardIterator, _ForwardIterator>
     minmax_element(_ForwardIterator __first, _ForwardIterator __last,
 		   _Compare __comp)
     {
@@ -3520,7 +3519,7 @@ 
    *          returns true; otherwise, returns false.
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2>
-    bool
+    inline bool
     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 		   _ForwardIterator2 __first2)
     {
@@ -3552,7 +3551,7 @@ 
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
-    bool
+    inline bool
     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 		   _ForwardIterator2 __first2, _BinaryPredicate __pred)
     {
@@ -3643,7 +3642,7 @@ 
    *          otherwise, returns false.
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2>
-    bool
+    inline bool
     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 		   _ForwardIterator2 __first2, _ForwardIterator2 __last2)
     {
@@ -3671,7 +3670,7 @@ 
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
-    bool
+    inline bool
     is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 		   _ForwardIterator2 __first2, _ForwardIterator2 __last2,
 		   _BinaryPredicate __pred)
@@ -3891,7 +3890,7 @@ 
    *  or @p __last if no such iterator exists.
   */
   template<typename _ForwardIterator>
-    _ForwardIterator
+    inline _ForwardIterator
     adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
     {
       // concept requirements
@@ -3916,7 +3915,7 @@ 
    *  exists.
   */
   template<typename _ForwardIterator, typename _BinaryPredicate>
-    _ForwardIterator
+    inline _ForwardIterator
     adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
 		  _BinaryPredicate __binary_pred)
     {
@@ -3941,7 +3940,7 @@ 
    *  for which @c *i == @p __value
   */
   template<typename _InputIterator, typename _Tp>
-    typename iterator_traits<_InputIterator>::difference_type
+    inline typename iterator_traits<_InputIterator>::difference_type
     count(_InputIterator __first, _InputIterator __last, const _Tp& __value)
     {
       // concept requirements
@@ -3964,7 +3963,7 @@ 
    *  for which @p __pred(*i) is true.
   */
   template<typename _InputIterator, typename _Predicate>
-    typename iterator_traits<_InputIterator>::difference_type
+    inline typename iterator_traits<_InputIterator>::difference_type
     count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
     {
       // concept requirements
@@ -4004,7 +4003,7 @@ 
    *  @p [__first1,__last1-(__last2-__first2))
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2>
-    _ForwardIterator1
+    inline _ForwardIterator1
     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 	   _ForwardIterator2 __first2, _ForwardIterator2 __last2)
     {
@@ -4044,7 +4043,7 @@ 
   */
   template<typename _ForwardIterator1, typename _ForwardIterator2,
 	   typename _BinaryPredicate>
-    _ForwardIterator1
+    inline _ForwardIterator1
     search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
 	   _ForwardIterator2 __first2, _ForwardIterator2 __last2,
 	   _BinaryPredicate  __predicate)
@@ -4078,7 +4077,7 @@ 
    *  equal to @p __val.
   */
   template<typename _ForwardIterator, typename _Integer, typename _Tp>
-    _ForwardIterator
+    inline _ForwardIterator
     search_n(_ForwardIterator __first, _ForwardIterator __last,
 	     _Integer __count, const _Tp& __val)
     {
@@ -4112,7 +4111,7 @@ 
   */
   template<typename _ForwardIterator, typename _Integer, typename _Tp,
            typename _BinaryPredicate>
-    _ForwardIterator
+    inline _ForwardIterator
     search_n(_ForwardIterator __first, _ForwardIterator __last,
 	     _Integer __count, const _Tp& __val,
 	     _BinaryPredicate __binary_pred)
@@ -4751,7 +4750,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
-    _OutputIterator
+    inline _OutputIterator
     merge(_InputIterator1 __first1, _InputIterator1 __last1,
 	  _InputIterator2 __first2, _InputIterator2 __last2,
 	  _OutputIterator __result)
@@ -4799,7 +4798,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
-    _OutputIterator
+    inline _OutputIterator
     merge(_InputIterator1 __first1, _InputIterator1 __last1,
 	  _InputIterator2 __first2, _InputIterator2 __last2,
 	  _OutputIterator __result, _Compare __comp)
@@ -4961,7 +4960,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
-    _OutputIterator
+    inline _OutputIterator
     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
 	      _InputIterator2 __first2, _InputIterator2 __last2,
 	      _OutputIterator __result)
@@ -5008,7 +5007,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
-    _OutputIterator
+    inline _OutputIterator
     set_union(_InputIterator1 __first1, _InputIterator1 __last1,
 	      _InputIterator2 __first2, _InputIterator2 __last2,
 	      _OutputIterator __result, _Compare __comp)
@@ -5076,7 +5075,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
-    _OutputIterator
+    inline _OutputIterator
     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
 		     _InputIterator2 __first2, _InputIterator2 __last2,
 		     _OutputIterator __result)
@@ -5122,7 +5121,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
-    _OutputIterator
+    inline _OutputIterator
     set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
 		     _InputIterator2 __first2, _InputIterator2 __last2,
 		     _OutputIterator __result, _Compare __comp)
@@ -5192,7 +5191,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
-    _OutputIterator
+    inline _OutputIterator
     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
 		   _InputIterator2 __first2, _InputIterator2 __last2,
 		   _OutputIterator __result)
@@ -5240,7 +5239,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
-    _OutputIterator
+    inline _OutputIterator
     set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
 		   _InputIterator2 __first2, _InputIterator2 __last2,
 		   _OutputIterator __result, _Compare __comp)
@@ -5316,7 +5315,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator>
-    _OutputIterator
+    inline _OutputIterator
     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
 			     _InputIterator2 __first2, _InputIterator2 __last2,
 			     _OutputIterator __result)
@@ -5364,7 +5363,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _OutputIterator, typename _Compare>
-    _OutputIterator
+    inline _OutputIterator
     set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
 			     _InputIterator2 __first2, _InputIterator2 __last2,
 			     _OutputIterator __result,
@@ -5414,7 +5413,7 @@ 
   */
   template<typename _ForwardIterator>
     _ForwardIterator
-    min_element(_ForwardIterator __first, _ForwardIterator __last)
+    inline min_element(_ForwardIterator __first, _ForwardIterator __last)
     {
       // concept requirements
       __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
@@ -5436,7 +5435,7 @@ 
    *  according to __comp.
   */
   template<typename _ForwardIterator, typename _Compare>
-    _ForwardIterator
+    inline _ForwardIterator
     min_element(_ForwardIterator __first, _ForwardIterator __last,
 		_Compare __comp)
     {
@@ -5472,7 +5471,7 @@ 
    *  @return  Iterator referencing the first instance of the largest value.
   */
   template<typename _ForwardIterator>
-    _ForwardIterator
+    inline _ForwardIterator
     max_element(_ForwardIterator __first, _ForwardIterator __last)
     {
       // concept requirements
@@ -5495,7 +5494,7 @@ 
    *  according to __comp.
   */
   template<typename _ForwardIterator, typename _Compare>
-    _ForwardIterator
+    inline _ForwardIterator
     max_element(_ForwardIterator __first, _ForwardIterator __last,
 		_Compare __comp)
     {
Index: include/bits/stl_algobase.h
===================================================================
--- include/bits/stl_algobase.h	(revision 203005)
+++ include/bits/stl_algobase.h	(working copy)
@@ -898,9 +898,9 @@ 
       __lexicographical_compare<_BoolType>::
       __lc(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
       {
-	return std::__lexicographical_compare_impl(
-		__first1, __last1, __first2, __last2,
-		__gnu_cxx::__ops::__iter_less_iter());
+	return std::__lexicographical_compare_impl(__first1, __last1,
+						   __first2, __last2,
+					__gnu_cxx::__ops::__iter_less_iter());
       }
 
   template<>
@@ -976,7 +976,7 @@ 
    *  @ingroup binary_search_algorithms
   */
   template<typename _ForwardIterator, typename _Tp>
-    _ForwardIterator
+    inline _ForwardIterator
     lower_bound(_ForwardIterator __first, _ForwardIterator __last,
 		const _Tp& __val)
     {
@@ -1226,7 +1226,7 @@ 
    *  comp parameter instead of @c <.
   */
   template<typename _II1, typename _II2, typename _Compare>
-    bool
+    inline bool
     lexicographical_compare(_II1 __first1, _II1 __last1,
 			    _II2 __first2, _II2 __last2, _Compare __comp)
     {
@@ -1269,7 +1269,7 @@ 
    *  to by the iterators are not equal.
   */
   template<typename _InputIterator1, typename _InputIterator2>
-    pair<_InputIterator1, _InputIterator2>
+    inline pair<_InputIterator1, _InputIterator2>
     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2)
     {
@@ -1303,7 +1303,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _BinaryPredicate>
-    pair<_InputIterator1, _InputIterator2>
+    inline pair<_InputIterator1, _InputIterator2>
     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2, _BinaryPredicate __binary_pred)
     {
@@ -1349,7 +1349,7 @@ 
    *  to by the iterators are not equal.
   */
   template<typename _InputIterator1, typename _InputIterator2>
-    pair<_InputIterator1, _InputIterator2>
+    inline pair<_InputIterator1, _InputIterator2>
     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2, _InputIterator2 __last2)
     {
@@ -1385,7 +1385,7 @@ 
   */
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _BinaryPredicate>
-    pair<_InputIterator1, _InputIterator2>
+    inline pair<_InputIterator1, _InputIterator2>
     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
 	     _InputIterator2 __first2, _InputIterator2 __last2,
 	     _BinaryPredicate __binary_pred)