stl_algo.h
来自「symbian上STL模板库的实现」· C头文件 代码 · 共 1,620 行 · 第 1/5 页
H
1,620 行
/** * @brief Find the first element in a sequence for which a predicate is true. * @param first An input iterator. * @param last An input iterator. * @param pred A predicate. * @return The first iterator @c i in the range @p [first,last) * such that @p pred(*i) is true, or @p last if no such iterator exists. */ template<typename _InputIterator, typename _Predicate> inline _InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) { // concept requirements#ifndef NO__GLIBCXX_FUNCTION_REQUIRES __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, typename iterator_traits<_InputIterator>::value_type>)#endif __glibcxx_requires_valid_range(__first, __last); return std::find_if(__first, __last, __pred, std::__iterator_category(__first)); } /** * @brief Find two adjacent values in a sequence that are equal. * @param first A forward iterator. * @param last A forward iterator. * @return The first iterator @c i such that @c i and @c i+1 are both * valid iterators in @p [first,last) and such that @c *i == @c *(i+1), * or @p last if no such iterator exists. */ template<typename _ForwardIterator> _ForwardIterator adjacent_find(_ForwardIterator __first, _ForwardIterator __last) { // concept requirements#ifndef NO__GLIBCXX_FUNCTION_REQUIRES __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_EqualityComparableConcept< typename iterator_traits<_ForwardIterator>::value_type>)#endif __glibcxx_requires_valid_range(__first, __last); if (__first == __last) return __last; _ForwardIterator __next = __first; while(++__next != __last) { if (*__first == *__next) return __first; __first = __next; } return __last; } /** * @brief Find two adjacent values in a sequence using a predicate. * @param first A forward iterator. * @param last A forward iterator. * @param binary_pred A binary predicate. * @return The first iterator @c i such that @c i and @c i+1 are both * valid iterators in @p [first,last) and such that * @p binary_pred(*i,*(i+1)) is true, or @p last if no such iterator * exists. */ template<typename _ForwardIterator, typename _BinaryPredicate> _ForwardIterator adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __binary_pred) { // concept requirements#ifndef NO__GLIBCXX_FUNCTION_REQUIRES __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>) __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, typename iterator_traits<_ForwardIterator>::value_type, typename iterator_traits<_ForwardIterator>::value_type>)#endif __glibcxx_requires_valid_range(__first, __last); if (__first == __last) return __last; _ForwardIterator __next = __first; while(++__next != __last) { if (__binary_pred(*__first, *__next)) return __first; __first = __next; } return __last; } /** * @brief Count the number of copies of a value in a sequence. * @param first An input iterator. * @param last An input iterator. * @param value The value to be counted. * @return The number of iterators @c i in the range @p [first,last) * for which @c *i == @p value */ template<typename _InputIterator, typename _Tp> typename iterator_traits<_InputIterator>::difference_type count(_InputIterator __first, _InputIterator __last, const _Tp& __value) { // concept requirements#ifndef NO__GLIBCXX_FUNCTION_REQUIRES __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) __glibcxx_function_requires(_EqualityComparableConcept< typename iterator_traits<_InputIterator>::value_type >) __glibcxx_function_requires(_EqualityComparableConcept<_Tp>)#endif __glibcxx_requires_valid_range(__first, __last); typename iterator_traits<_InputIterator>::difference_type __n = 0; for ( ; __first != __last; ++__first) if (*__first == __value) ++__n; return __n; } /** * @brief Count the elements of a sequence for which a predicate is true. * @param first An input iterator. * @param last An input iterator. * @param pred A predicate. * @return The number of iterators @c i in the range @p [first,last) * for which @p pred(*i) is true. */ template<typename _InputIterator, typename _Predicate> typename iterator_traits<_InputIterator>::difference_type count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) { // concept requirements#ifndef NO__GLIBCXX_FUNCTION_REQUIRES __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>) __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate, typename iterator_traits<_InputIterator>::value_type>)#endif __glibcxx_requires_valid_range(__first, __last); typename iterator_traits<_InputIterator>::difference_type __n = 0; for ( ; __first != __last; ++__first) if (__pred(*__first)) ++__n; return __n; } /** * @brief Search a sequence for a matching sub-sequence. * @param first1 A forward iterator. * @param last1 A forward iterator. * @param first2 A forward iterator. * @param last2 A forward iterator. * @return The first iterator @c i in the range * @p [first1,last1-(last2-first2)) such that @c *(i+N) == @p *(first2+N) * for each @c N in the range @p [0,last2-first2), or @p last1 if no * such iterator exists. * * Searches the range @p [first1,last1) for a sub-sequence that compares * equal value-by-value with the sequence given by @p [first2,last2) and * returns an iterator to the first element of the sub-sequence, or * @p last1 if the sub-sequence is not found. * * Because the sub-sequence must lie completely within the range * @p [first1,last1) it must start at a position less than * @p last1-(last2-first2) where @p last2-first2 is the length of the * sub-sequence. * This means that the returned iterator @c i will be in the range * @p [first1,last1-(last2-first2)) */ template<typename _ForwardIterator1, typename _ForwardIterator2> _ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2) { // concept requirements#ifndef NO__GLIBCXX_FUNCTION_REQUIRES __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) __glibcxx_function_requires(_EqualOpConcept< typename iterator_traits<_ForwardIterator1>::value_type, typename iterator_traits<_ForwardIterator2>::value_type>)#endif __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) return __first1; // Test for a pattern of length 1. _ForwardIterator2 __tmp(__first2); ++__tmp; if (__tmp == __last2) return std::find(__first1, __last1, *__first2); // General case. _ForwardIterator2 __p1, __p; __p1 = __first2; ++__p1; _ForwardIterator1 __current = __first1; while (__first1 != __last1) { __first1 = std::find(__first1, __last1, *__first2); if (__first1 == __last1) return __last1; __p = __p1; __current = __first1; if (++__current == __last1) return __last1; while (*__current == *__p) { if (++__p == __last2) return __first1; if (++__current == __last1) return __last1; } ++__first1; } return __first1; } /** * @brief Search a sequence for a matching sub-sequence using a predicate. * @param first1 A forward iterator. * @param last1 A forward iterator. * @param first2 A forward iterator. * @param last2 A forward iterator. * @param predicate A binary predicate. * @return The first iterator @c i in the range * @p [first1,last1-(last2-first2)) such that * @p predicate(*(i+N),*(first2+N)) is true for each @c N in the range * @p [0,last2-first2), or @p last1 if no such iterator exists. * * Searches the range @p [first1,last1) for a sub-sequence that compares * equal value-by-value with the sequence given by @p [first2,last2), * using @p predicate to determine equality, and returns an iterator * to the first element of the sub-sequence, or @p last1 if no such * iterator exists. * * @see search(_ForwardIter1, _ForwardIter1, _ForwardIter2, _ForwardIter2) */ template<typename _ForwardIterator1, typename _ForwardIterator2, typename _BinaryPredicate> _ForwardIterator1 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __predicate) { // concept requirements#ifndef NO__GLIBCXX_FUNCTION_REQUIRES __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>) __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>) __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate, typename iterator_traits<_ForwardIterator1>::value_type, typename iterator_traits<_ForwardIterator2>::value_type>)#endif __glibcxx_requires_valid_range(__first1, __last1); __glibcxx_requires_valid_range(__first2, __last2); // Test for empty ranges if (__first1 == __last1 || __first2 == __last2) return __first1; // Test for a pattern of length 1. _ForwardIterator2 __tmp(__first2); ++__tmp; if (__tmp == __last2) { while (__first1 != __last1 && !__predicate(*__first1, *__first2)) ++__first1; return __first1; } // General case. _ForwardIterator2 __p1, __p; __p1 = __first2; ++__p1; _ForwardIterator1 __current = __first1; while (__first1 != __last1) { while (__first1 != __last1) { if (__predicate(*__first1, *__first2)) break; ++__first1; } while (__first1 != __last1 && !__predicate(*__first1, *__first2)) ++__first1; if (__first1 == __last1) return __last1; __p = __p1; __current = __first1; if (++__current == __last1) return __last1; while (__predicate(*__current, *__p)) { if (++__p == __last2) return __first1; if (++__current == __last1) return __last1; } ++__first1; } return __first1; } /** * @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)⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?