Немодифицирующие последовательность алгоритмы STL.

Алгоритмы этой категории просматривают последовательность, не изменяя её. Используются для получения информации о последовательности или для определения положения элемента. Так же могут использоваться для изменения элемента (т.е. не модифицирующие алгоритмы - не изменяют контейнер как объект (к нему не прибавятся или от него не убавятся элементы) но сами элементы могут быть изменены)

std::find, std::find_if

Алгоритмы семейста find осуществляют поиск в последовательности и возвращают итератор на самый левый элемент, удовлетворяющий критерию поиска, или на конец последовательности (имеется в виду - переданной в алгоритм), если элемент не найден.
find ищет элемент по значению.

  1. template<class InputIterator, class T>
  2. InputIterator find ( InputIterator first, InputIterator last, const T& val )
  3. {
  4. while ( first!=last )
  5. {
  6. if ( *first==val ) return first;
  7. ++first;
  8. }
  9. return last;
  10. }

find_if, по условию, определяемому предикатом

  1. template<class InputIterator, class UnaryPredicate>
  2. InputIterator find_if ( InputIterator first, InputIterator last, UnaryPredicate pred )
  3. {
  4. while ( first!=last )
  5. {
  6. if ( pred(*first) ) return first;
  7. ++first;
  8. }
  9. return last;
  10. }

Пример использования:
Напечатать о нахождении указанного элемента в последовательности, и выдать его номер.

  1. // find example
  2. #include <iostream> // std::cout
  3. #include <algorithm> // std::find
  4. #include <vector> // std::vector
  5.  
  6. int main ()
  7. {
  8. int myints[] = { 10, 20, 30, 40, 50, 60 };
  9. int * p, myints_size = sizeof(myints)/sizeof(myints[0]);
  10.  
  11. std::vector<int> v ( myints,myints+myints_size );
  12. std::vector<int>::iterator it;
  13.  
  14. it = find ( v.begin(), v.end(), 30 ) ;
  15.  
  16. if (it != v.end())
  17. std::cout << "Element found in myints: " << *it <<
  18. " index: " << 1 + std::distance( v.begin(), it) <<
  19. '\n';
  20. else
  21. std::cout << "Element not found in v\n";
  22.  
  23. return 0;
  24. }

Пример второй, считать из файла целочисленные значения в вектор, и найти первое значение, удовлетворяющее некоторому критерию.

  1. // find example
  2. #include <iostream> // std::cout
  3. #include <algorithm> // std::find
  4. #include <vector> // std::vector
  5. #include <fstream> // std::ifstream
  6. #include <iterator> // std::istream_iterator
  7.  
  8. struct In_10_50
  9. {
  10. bool operator ( ) ( const int & x ) const { return x > 10 && x < 50; }
  11. };
  12.  
  13. int main ( )
  14. {
  15. In_10_50 in_10_50;
  16.  
  17. std::ifstream in ("inpnum.txt");
  18. if ( !in.is_open( ) )
  19. {
  20. std::cerr << "Error in open file \"inpnum.txt\"\n";
  21. return 1;
  22. }
  23.  
  24. std::vector<int> v ( (std::istream_iterator<int>(in)),
  25. std::istream_iterator<int>() );
  26.  
  27. std::cout <<
  28. std::distance ( v.begin(), std::find_if ( v.begin(), v.end(), in_10_50 ) )
  29. << '\n';
  30.  
  31. return 0;
  32. }

Кстати, видно, как можно красиво в одну строчку ( и избегая лишнюю загрузку стека-программы ) благодаря STL, сконструировать вектор. Взамен стандартного подхода.

  1. std::vector<int> v;
  2. int x;
  3. while ( in >> x )
  4. {
  5. v.push_back(x);
  6. }

Важно. Можно увидеть лишние круглые скобки в вызове конструктора через итератор. На самом деле это не лишние скобки, а очень нужные. А существуют они, как следствие того что Си++ очень богатый язык, с историей, в отличии от всяких там "современных языков" :)

Примеры использования остальных описываемых алгоритмов для краткости будут в отдельных файлах.

find_first_of, find_end

Находят первое (самое левое) и последнее (самое правое) вхождение элемента из второй последовательности в первой. В случае неудачного поиска возвращается last.

  1. template<class InputIt, class ForwardIt>
  2. InputIt find_first_of ( InputIt first, InputIt last,
  3. ForwardIt s_first, ForwardIt s_last )
  4. {
  5. for ( ; first != last; ++first )
  6. for ( ForwardIt it = s_first; it != s_last; ++it )
  7. if ( *first == *it )
  8. return first;
  9. return last;
  10. }
  1. template<class InputIt, class ForwardIt, class BinaryPredicate>
  2. InputIt find_first_of ( InputIt first, InputIt last,
  3. ForwardIt s_first, ForwardIt s_last,
  4. BinaryPredicate pred )
  5. {
  6. for ( ; first != last; ++first )
  7. for ( ForwardIt it = s_first; it != s_last; ++it )
  8. if ( pred(*first, *it) )
  9. return first;
  10.  
  11. return last;
  12. }

Пример

find_end

Находит последнее вхождение в первую последовательность второй последовательности ( с анализом предиката или без ) и возвращает итератор на первый совпадающий элемент последнего вхождения.

  1. template <class ForwardIt1, class ForwardIt2>
  2. ForwardIt1 find_end ( ForwardIt1 first, ForwardIt1 last,
  3. ForwardIt2 s_first, ForwardIt2 s_last )
  4. {
  5. if ( s_first == s_last )
  6. return last;
  7. ForwardIt1 result = last;
  8. while ( 1 )
  9. {
  10. ForwardIt1 new_result = std::search(first, last, s_first, s_last);
  11. if ( new_result == last )
  12. return result;
  13. else
  14. {
  15. result = new_result;
  16. first = result;
  17. ++first;
  18. }
  19. }
  20. return result;
  21. }
  1. template <class ForwardIt1, class ForwardIt2, class BinaryPredicate>
  2. ForwardIt1 find_end ( ForwardIt1 first, ForwardIt1 last,
  3. ForwardIt2 s_first, ForwardIt2 s_last,
  4. BinaryPredicate pred )
  5. {
  6. if ( s_first == s_last )
  7. return last;
  8. ForwardIt1 result = last;
  9. while ( 1 )
  10. {
  11. ForwardIt1 new_result = std::search(first, last, s_first, s_last, pred);
  12. if ( new_result == last )
  13. return result;
  14. else
  15. {
  16. result = new_result;
  17. first = result;
  18. ++first;
  19. }
  20. }
  21. return result;
  22. }

Пример

count, count_if

Выполняют подсчет количества вхождения значения в контейнере, по значению или по условию предиката.

Примечательно, что для ассоциативных контейнеров определен свой метод size_type count (const value_type& val) const;, использовать который предпочтительнее.

  1. template <class InputIterator, class T>
  2. typename iterator_traits<InputIterator>::difference_type
  3. count ( InputIterator first, InputIterator last, const T& val )
  4. {
  5. typename iterator_traits<InputIterator>::difference_type ret = 0;
  6. while ( first!=last )
  7. {
  8. if ( *first == val ) ++ret;
  9. ++first;
  10. }
  11. return ret;
  12. }
  13.  
  14. template <class InputIterator, class UnaryPredicate>
  15. typename iterator_traits<InputIterator>::difference_type
  16. count_if ( InputIterator first, InputIterator last, UnaryPredicate pred )
  17. {
  18. typename iterator_traits<InputIterator>::difference_type ret = 0;
  19. while ( first!=last )
  20. {
  21. if ( pred(*first) ) ++ret;
  22. ++first;
  23. }
  24. return ret;
  25. }

Пример

adjacent_find

Находит пару соседних значений. Первая форма алгоритма находит пару соседних одинаковых значений и возвращает итератор на первое из них или конец последовательности. Вторая форма находит соседние элементы, удовлетворяющие условию, заданному предикатом.

  1. template<class ForwardIt>
  2. ForwardIt adjacent_find ( ForwardIt first, ForwardIt last )
  3. {
  4. if ( first == last )
  5. return last;
  6.  
  7. ForwardIt next = first; ++next;
  8. for ( next != last; ++next, ++first )
  9. if ( *first == *next )
  10. return first;
  11. return last;
  12. }
  1. template <class ForwardIt, BinaryPredicate p>
  2. ForwardIt adjacent_find ( ForwardIt first, ForwardIt last,
  3. BinaryPredicate pred )
  4. {
  5. if ( first == last )
  6. return last;
  7.  
  8. ForwardIt next = first;
  9. ++next;
  10. for ( next != last; ++next, ++first )
  11. if ( pred(*first, *next) )
  12. return first;
  13. return last;
  14. }

Пример

mismatch

Возвращает итераторы на первую пару несовпадающих элементов из двух последовательностей.

  1. template <class InputIt1, class InputIt2>
  2. std::pair <InputIt1, InputIt2>
  3. mismatch ( InputIt1 first1, InputIt1 last1, InputIt2 first2 )
  4. {
  5. while ( first1 != last1 && *first1 == *first2 )
  6. {
  7. ++first1, ++first2;
  8. }
  9. return std::make_pair ( first1, first2 );
  10. }
  1. template <class InputIt1, class InputIt2, class BinaryPredicate>
  2. std::pair <InputIt1, InputIt2>
  3. mismatch ( InputIt1 first1, InputIt1 last1, InputIt2 first2, BinaryPredicate pred )
  4. {
  5. while ( first1 != last1 && pred(*first1, *first2) )
  6. {
  7. ++first1, ++first2;
  8. }
  9. return std::make_pair ( first1, first2 );
  10. }

Пример

search

Находит первое вхождение в первую последовательность второй последовательности по значению элементов или по предикату.

  1. template <class ForwardIterator1, class ForwardIterator2>
  2. ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
  3. ForwardIterator2 first2, ForwardIterator2 last2 )
  4. {
  5. if ( first2==last2 ) return first1; // specified in C++11
  6.  
  7. while ( first1!=last1 )
  8. {
  9. ForwardIterator1 it1 = first1;
  10. ForwardIterator2 it2 = first2;
  11. while ( *it1 == *it2 )
  12. {
  13. ++it1; ++it2;
  14. if ( it2 == last2 ) return first1;
  15. if ( it1 == last1 ) return last1;
  16. }
  17. ++first1;
  18. }
  19. return last1;
  20. }
  1. template <class ForwardIterator1, class ForwardIterator2>
  2. ForwardIterator1 search ( ForwardIterator1 first1, ForwardIterator1 last1,
  3. ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred )
  4. {
  5. if ( first2==last2 ) return first1; // specified in C++11
  6.  
  7. while ( first1!=last1 )
  8. {
  9. ForwardIterator1 it1 = first1;
  10. ForwardIterator2 it2 = first2;
  11. while ( pred(*it1,*it2) )
  12. {
  13. ++it1; ++it2;
  14. if ( it2 == last2 ) return first1;
  15. if ( it1 == last1 ) return last1;
  16. }
  17. ++first1;
  18. }
  19. return last1;
  20. }

Пример

search_n

Ищет в указанном диапазоне [first, last) первую последовательность из count одинаковых элементов, используя оператор == или бинарный предикат.

  1. template<class ForwardIterator, class Size, class T>
  2. ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
  3. Size count, const T& val )
  4. {
  5. ForwardIterator it, limit;
  6. Size i;
  7.  
  8. limit=first; std::advance(limit,std::distance(first,last)-count);
  9.  
  10. while ( first != limit )
  11. {
  12. it = first; i=0;
  13. while ( *it==val )
  14. { ++it; if ( ++i == count ) return first; }
  15. ++first;
  16. }
  17. return last;
  18. }
  1. template<class ForwardIterator, class Size, class T>
  2. ForwardIterator search_n ( ForwardIterator first, ForwardIterator last,
  3. Size count, const T& val, BinaryPredicate pred )
  4. {
  5. ForwardIterator it, limit;
  6. Size i;
  7.  
  8. limit=first; std::advance(limit,std::distance(first,last)-count);
  9.  
  10. while ( first != limit )
  11. {
  12. it = first; i=0;
  13. while ( pred(*it,val) )
  14. { ++it; if ( ++i == count ) return first; }
  15. ++first;
  16. }
  17. return last;
  18. }

Пример