Re: Change to search_n

[Chris Jefferson <caj at cs dot york dot ac dot uk>]

Dimitris Xochellis wrote:

> Chris Jefferson wrote in:
>
> http://gcc.gnu.org/ml/libstdc++/2004-08/msg00090.html
>
>  
>
> > Hi and thanks for your message.
> >    
>
>  
>
> > During the next days I will analyze in detail your
> > proposal but, first, I'd like to ask your whether
> >    
> your
>  
>
> > work is related to this algorithm which we were
> > already finding very interesting:
> > http://www.codeproject.com/vcpp/stl/SearchN.asp
> >    
>
> Hello,
>
> I am the author of the above article and I am very 
> happy that you found it interesting. I just discovered
> this discussion thread and immediately after I have
> downloaded the latest(rev 1.50) stl_algo.h file from
> gcc/libstdc++-v3/include/bits/stl_algo.h.
> Unfortunately that file seems to contain only the
> traditional search_n implementation. :-( 
>
> What are the current status and your plans regarding
> the search_n implementation? Can I help in any way?
>
>  
Hello!

As Paolo has said, there was some worry this patch might slow things 
down in some cases.. in particular, I found it did slow things down when 
searching for strings of length 1 or 2 on some computers. Of course 
search_n for length 1 is just find, so we can ask find to do it, and I 
wrote a specialised version for length 2. I attach to this email my 
latest version from my personal gcc tree, which I am more than happy for 
you to comment on / suggest changes :)

As to submitting this into libstdc++, my personal current temptation was 
to submit it to the "so_7" branch, so called as it will be the next 
version of libstdc++ which is not binary compatable with the current 
version (so_6), mainly because I felt such a time was a good time to 
insert code which might change behaviour. Of course this code shouldn't 
change the behaviour of any code which follows the standard, but we've 
all seen enough badly written code to know it might upset someone..

Chris
  template<typename _ForwardIterator, typename _Integer, typename _Tp>
    _ForwardIterator
    __search_n(_ForwardIterator __first, _ForwardIterator __last,
	       _Integer __count, const _Tp& __val, forward_iterator_tag)
    {
      __first = std::find(__first, __last, __val);
      while (__first != __last)
	{
	  typename iterator_traits<_ForwardIterator>::difference_type
	    __n = __count;
	  _ForwardIterator __i = __first;
	  ++__i;
	  while (__i != __last && __n != 1 && *__i == __val)
	    {
	      ++__i;
	      --__n;
	    }
	  if (__n == 1)
	    return __first;
	  else
	    if(__i != __last)
	      __first = std::find(++__i, __last, __val);
	    else
	      return __last;
	}
      return __last;
    }

 template<typename _RandomAccessIterator, typename _Integer, typename _Tp>
   _RandomAccessIterator
   __search_n(_RandomAccessIterator __first, _RandomAccessIterator __last,
	       _Integer __count, const _Tp& __val, random_access_iterator_tag)
    {
      if(__last - __first < __count)
	return __last;
      if(__count == 1)
	return std::find(__first, __last, __val);
      if(__count == 2)
	{
	  __first++;
	  while(1)
	    {
	      if(*__first == __val)
		{
		  if(*(--__first) == __val)
		    return __first;
		  if(__last - __first <= 2)
		    return __last;
		  __first += 2;
		  if(*__first == __val)
		    return --__first;
		}
	      if(__last - __first <= 2)
		return __last;
	      else __first += 2;
	    }
	}
      else
	{
	  // Note: The following code is not correct for __count < 3
	  typename iterator_traits<_RandomAccessIterator>::difference_type
	    __precount = (*__first == __val);
	  __first += __count - __precount;
	  while(1)
	    {
	      if(*__first == __val)
		{
		  _RandomAccessIterator __it1 = __first;
		  typename iterator_traits<_RandomAccessIterator>::difference_type
		    __n = __count - 1;
		  --__it1;
		  while(*__it1 == __val && --__n > __precount)
		    --__it1;
		  if(__n == __precount)
		    return __it1 - __precount;
		  if(__last - __first <= __n)
		    return __last;
		  typename iterator_traits<_RandomAccessIterator>::difference_type
		    __cache_n  = __n;
		  _RandomAccessIterator __it2 = __first + __n;
		  while(*__it2 == __val && --__n > 0)
		    --__it2;
		  if(__n == 0)
		    return ++__it1;
		  __precount = __cache_n - __n;
		  if(__last - __first > __count - __precount)
		    __first += __count - __precount;
		  else
		    return __last;
		}
	      else
		{
		  if(__last - __first > __count)
		    {
		      __first += __count;
		      __precount = 0;
		    }
		  else
		    return __last;
		}
	    }
	}
    }
  
  /**
   *  @brief Search a sequence for a number of consecutive values.
   *  @param  first  A forward iterator.
   *  @param  last   A forward iterator.
   *  @param  count  The number of consecutive values.
   *  @param  val    The value to find.
   *  @return   The first iterator @c i in the range @p [first,last-count)
   *  such that @c *(i+N) == @p val for each @c N in the range @p [0,count),
   *  or @p last if no such iterator exists.
   *
   *  Searches the range @p [first,last) for @p count consecutive elements
   *  equal to @p val.
  */
  template<typename _ForwardIterator, typename _Integer, typename _Tp>
    _ForwardIterator
    search_n(_ForwardIterator __first, _ForwardIterator __last,
	     _Integer __count, const _Tp& __val)
    {
      // concept requirements
      __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
      __glibcxx_function_requires(_EqualityComparableConcept<
	    typename iterator_traits<_ForwardIterator>::value_type>)
      __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__count <= 0)
	return __first;
      else
	return __search_n(__first, __last, __count, __val, 
			  std::__iterator_category(__first));
    }