This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Change to search_n


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));
    }


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]