diff options
author | Paolo Carlini <paolo@gcc.gnu.org> | 2005-09-12 21:13:04 +0000 |
---|---|---|
committer | Paolo Carlini <paolo@gcc.gnu.org> | 2005-09-12 21:13:04 +0000 |
commit | b35c082263257779ba2c3e2ae8fbeaa19bfdf374 (patch) | |
tree | 17e39f1823874105167557a234b7c98f6947dfed /libstdc++-v3 | |
parent | dda6e8cd3a8f81a42485f9a78cb3c8c3b0103307 (diff) | |
download | gcc-b35c082263257779ba2c3e2ae8fbeaa19bfdf374.zip gcc-b35c082263257779ba2c3e2ae8fbeaa19bfdf374.tar.gz gcc-b35c082263257779ba2c3e2ae8fbeaa19bfdf374.tar.bz2 |
[multiple changes]
2005-09-12 Chris Jefferson <chris@bubblescope.net>
* include/bits/stl_algo.h (search_n): Delegate to specializations.
(search_n(,,,,binary_predicate)): Likewise.
(__search_n(forward_iterator_tag)): Original search_n, tweak to
remove an unnecessary comparison.
(__search_n(,,,,binary_predicate,forward_iterator_tag)): Likewise.
2005-09-12 Jim Xochellis <jimxoch@yahoo.gr>
* include/bits/stl_algo.h (__search_n(std::random_access_iterator_tag)):
Add specialization.
(__search_n(,,,,binary_predicate,std::random_access_iterator_tag)):
Likewise.
From-SVN: r104192
Diffstat (limited to 'libstdc++-v3')
-rw-r--r-- | libstdc++-v3/ChangeLog | 15 | ||||
-rw-r--r-- | libstdc++-v3/include/bits/stl_algo.h | 233 |
2 files changed, 200 insertions, 48 deletions
diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 4c8db92..154e32a 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,18 @@ +2005-09-12 Chris Jefferson <chris@bubblescope.net> + + * include/bits/stl_algo.h (search_n): Delegate to specializations. + (search_n(,,,,binary_predicate)): Likewise. + (__search_n(forward_iterator_tag)): Original search_n, tweak to + remove an unnecessary comparison. + (__search_n(,,,,binary_predicate,forward_iterator_tag)): Likewise. + +2005-09-12 Jim Xochellis <jimxoch@yahoo.gr> + + * include/bits/stl_algo.h (__search_n(std::random_access_iterator_tag)): + Add specialization. + (__search_n(,,,,binary_predicate,std::random_access_iterator_tag)): + Likewise. + 2005-09-12 Benjamin Kosnik <bkoz@redhat.com> PR libstdc++/23417 diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h index 5754d04..1a7fd6e 100644 --- a/libstdc++-v3/include/bits/stl_algo.h +++ b/libstdc++-v3/include/bits/stl_algo.h @@ -607,6 +607,92 @@ namespace std } /** + * @if maint + * This is an uglified + * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) + * overloaded for forward iterators. + * @endif + */ + template<typename _ForwardIterator, typename _Integer, typename _Tp> + _ForwardIterator + __search_n(_ForwardIterator __first, _ForwardIterator __last, + _Integer __count, const _Tp& __val, + std::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; + if (__i == __last) + return __last; + __first = std::find(++__i, __last, __val); + } + return __last; + } + + /** + * @if maint + * This is an uglified + * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&) + * overloaded for random access iterators. + * @endif + */ + template<typename _RandomAccessIter, typename _Integer, typename _Tp> + _RandomAccessIter + __search_n(_RandomAccessIter __first, _RandomAccessIter __last, + _Integer __count, const _Tp& __val, + std::random_access_iterator_tag) + { + + typedef typename std::iterator_traits<_RandomAccessIter>::difference_type + _DistanceType; + + _DistanceType __tailSize = __last - __first; + const _DistanceType __pattSize = __count; + + if (__tailSize < __pattSize) + return __last; + + const _DistanceType __skipOffset = __pattSize - 1; + _RandomAccessIter __lookAhead = __first + __skipOffset; + __tailSize -= __pattSize; + + while (1) // the main loop... + { + // __lookAhead here is always pointing to the last element of next + // possible match. + while (!(*__lookAhead == __val)) // the skip loop... + { + if (__tailSize < __pattSize) + return __last; // Failure + __lookAhead += __pattSize; + __tailSize -= __pattSize; + } + _DistanceType __remainder = __skipOffset; + for (_RandomAccessIter __backTrack = __lookAhead - 1; + *__backTrack == __val; --__backTrack) + { + if (--__remainder == 0) + return (__lookAhead - __skipOffset); // Success + } + if (__remainder > __tailSize) + return __last; // Failure + __lookAhead += __remainder; + __tailSize -= __remainder; + } + } + + /** * @brief Search a sequence for a number of consecutive values. * @param first A forward iterator. * @param last A forward iterator. @@ -632,26 +718,103 @@ namespace std if (__count <= 0) return __first; - else + if (__count == 1) + return std::find(__first, __last, __val); + return std::__search_n(__first, __last, __count, __val, + std::__iterator_category(__first)); + } + + /** + * @if maint + * This is an uglified + * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, + * _BinaryPredicate) + * overloaded for forward iterators. + * @endif + */ + template<typename _ForwardIterator, typename _Integer, typename _Tp, + typename _BinaryPredicate> + _ForwardIterator + __search_n(_ForwardIterator __first, _ForwardIterator __last, + _Integer __count, const _Tp& __val, + _BinaryPredicate __binary_pred, std::forward_iterator_tag) + { + while (__first != __last && !__binary_pred(*__first, __val)) + ++__first; + + while (__first != __last) { - __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) { - 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 - __first = std::find(__i, __last, __val); + --__n; } - return __last; + if (__n == 1) + return __first; + if (__i == __last) + return __last; + __first = ++__i; + while (__first != __last && !__binary_pred(*__first, __val)) + ++__first; + } + return __last; + } + + /** + * @if maint + * This is an uglified + * search_n(_ForwardIterator, _ForwardIterator, _Integer, const _Tp&, + * _BinaryPredicate) + * overloaded for random access iterators. + * @endif + */ + template<typename _RandomAccessIter, typename _Integer, typename _Tp, + typename _BinaryPredicate> + _RandomAccessIter + __search_n(_RandomAccessIter __first, _RandomAccessIter __last, + _Integer __count, const _Tp& __val, + _BinaryPredicate __binary_pred, std::random_access_iterator_tag) + { + + typedef typename std::iterator_traits<_RandomAccessIter>::difference_type + _DistanceType; + + _DistanceType __tailSize = __last - __first; + const _DistanceType __pattSize = __count; + + if (__tailSize < __pattSize) + return __last; + + const _DistanceType __skipOffset = __pattSize - 1; + _RandomAccessIter __lookAhead = __first + __skipOffset; + __tailSize -= __pattSize; + + while (1) // the main loop... + { + // __lookAhead here is always pointing to the last element of next + // possible match. + while (!__binary_pred(*__lookAhead, __val)) // the skip loop... + { + if (__tailSize < __pattSize) + return __last; // Failure + __lookAhead += __pattSize; + __tailSize -= __pattSize; + } + _DistanceType __remainder = __skipOffset; + for (_RandomAccessIter __backTrack = __lookAhead - 1; + __binary_pred(*__backTrack, __val); --__backTrack) + { + if (--__remainder == 0) + return (__lookAhead - __skipOffset); // Success + } + if (__remainder > __tailSize) + return __last; // Failure + __lookAhead += __remainder; + __tailSize -= __remainder; } } @@ -685,40 +848,14 @@ namespace std if (__count <= 0) return __first; - else + if (__count == 1) { - while (__first != __last) - { - if (__binary_pred(*__first, __val)) - break; - ++__first; - } - while (__first != __last) - { - typename iterator_traits<_ForwardIterator>::difference_type - __n = __count; - _ForwardIterator __i = __first; - ++__i; - while (__i != __last && __n != 1 && __binary_pred(*__i, __val)) - { - ++__i; - --__n; - } - if (__n == 1) - return __first; - else - { - while (__i != __last) - { - if (__binary_pred(*__i, __val)) - break; - ++__i; - } - __first = __i; - } - } - return __last; + while (__first != __last && !__binary_pred(*__first, __val)) + ++__first; + return __first; } + return std::__search_n(__first, __last, __count, __val, __binary_pred, + std::__iterator_category(__first)); } /** |