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]

Change to search_n


Hello!

I apologise in advance for what will be I suspect a badly formed e-mail. I hope that with your help I can shape it up a little, and that I will have some useful things to say.

I was recently looking at the STL function search_n, included in stl_algo.h. The version I have is gcc 3.3.4 (as this appears to be the most recent version in Debian). I have been having some minor difficulties getting the CVS version, so I hope things have not changed too much!

First of all, a very small patch near the end of the function:

if(__n == 0)
   return __first;
else
   __first = find(__i, __last, __val);

Can be changed to:

if(__n == 0)
   return __first;
if(__i == __last)
   return __last;
__first = __find(++__i, __last, __val);

This creates a small speed improvement generally, and in the best case (where you are for example searching through a list which alternates a,b,a,b,a,b... , you are looking for 2 (or more) a's, and the comparison function is expensive) then can lead to a 50% speed improvement (as previously each "b" would be checked twice). This new version also has the advantage it checks each variable only once.

Further to this, I have also introduced a special search_n for random access iterators in the same way as exists for some other functions (and in I hope a similar way), which I have included in an attached file. This will also compare no two objects more than once, and also while having the same worst case complexity, the average case complexity is closer to (length/n) where length is the distance between the input iterators and n is the length of symbols to be found. The only difference between this and the implentation of find_if (which is where I borrowed the idea and implementation from) is that the "specialised "search_n" functions are not called search_n, as this appears to interfere with the varient of search_n which takes an extra parameter.

I also have a testing program which checks a range of areas where I suspected the algorithms could go wrong, and also compares them to each other for all possible inputs of length 12 or less to make sure they agree. I haven't attached this because it isn't really very clean.

I hope that this is useful and interesting, and also perhaps someone might be able to point me to what I should do to a) include these in the standard library should they be applicable b) get my own version and get it compiled, and c) add things to the test suite. I tried checking the stdlib webpage but was worried it hasn't been updated since 2002 (it appears) so may be very out of date.

Thank you,

Chris
  template<typename _InputIter, typename _Integer, typename _Tp>
  inline _InputIter
  search_n(_InputIter __first, _InputIter __last,
       _Integer __count, const _Tp& __val)
  {
    // concept requirements
    __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
      __glibcpp_function_requires(_EqualityComparableConcept<
				  typename iterator_traits<_ForwardIter>::value_type>)
      __glibcpp_function_requires(_EqualityComparableConcept<_Tp>)

      return _search_n(__first, __last, __count, __val, __iterator_category(__first));
  }
  


  template<typename _ForwardIter, typename _Integer, typename _Tp>
  _ForwardIter
  _search_n(_ForwardIter __first, _ForwardIter __last,
	   _Integer __count, const _Tp& __val,random_access_iterator_tag)
  {
    if(__count<=0) return __first;
 
    while(__first<=__last) {
      if(__count>__last-__first)
	return __last;
      _ForwardIter __i = __first;
      
      __i+=__count-1;
      if(__i>=__last) return __last;
      if(*__i==__val) {
	int __equal=0;
	while((*__i==__val) && (__i>=__first)) {
	  __equal++; __i--;
	}
	__i++;
	_ForwardIter __possibleFirst = __i;

	__i=__first+__count;
	while(*__i==__val && __i<__last && __equal<__count) {    
	  __equal++; __i++;
	}
	if(__equal==__count)
	  return __possibleFirst;
	if(__i==__last) 
	  return __last;
      }
      __i++;
      
      __first=__i;
    }
    return __last;
  }
  
  
  template<typename _ForwardIter, typename _Integer, typename _Tp>
  _ForwardIter
  _search_n(_ForwardIter __first, _ForwardIter __last,
		    _Integer __count, const _Tp& __val,input_iterator_tag)
  {
      if (__count <= 0)
	return __first;
      else {
	__first = find(__first, __last, __val);
	while (__first != __last) {
	  typename iterator_traits<_ForwardIter>::difference_type __n = __count;
	  --__n;
	  _ForwardIter __i = __first;
	  ++__i;
	  while (__i != __last && __n != 0 && *__i == __val) {
	    ++__i;
	    --__n;
	  }
	  if (__n == 0)
	    return __first;
	  if (__i == __last)
	    return __last;

	    __first = find(++__i, __last, __val);
	}
	return __last;
      }
  }

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