Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
36.
Алгоритмы поиска в STL
Алгоритмы find, find_if
Прототипы
template<typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T& value);
template<typename InputIterator, typename Predicate>
InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);
Описание
Первая версия алгоритма обходит диапазон [first; last) и возвращает первый итератор i такой, что *i == value.
Вторая версия возвращает первый итератор i такой, что pred(*i) == true. В обоих случаях, если такой итератор не найден, возвращается итератор last.
Временная сложность
Линейная. Максимальное количество применений оператора != (или pred в случае find_if) равно размеру диапазона [ first; last). Если соответствие найдено, количество сравнений (или применений pred) на одно больше размера диапазона [first; i).
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//Определение типа унарного предиката
class GreaterThan50
{ public:
bool operator()(int x)
{return x>50;}
};
int main()
{ //Создание вектора со значениями
//0,1,4,9,16,25,36,49,64,...,144
vector<int> v1;
for(int i=0;i<13;++i)
v1.push_back(i*i);
vector<int>::iterator it;
//ищем первое вхождение числа 25
it=find(v1.begin(),v1.end(),25);
cout<<"Number 25 in position: "<<it-v1.begin()<<endl;
//ищем первый элемент для которого истинен предикат
it=find_if(v1.begin(),v1.end(),GreaterThan50());
cout<<*it<<endl;
return 0;
}
Результаты выполнения программы:
Number 25 in position: 5
64
Алгоритм find_first_of
Прототипы
template <typename ForwardIterator1, typename ForwardIterator2> ForwardIteratorl find_first_of(ForwardIteratorl firstl, ForwardIteratorl lastl,
ForwardIterator2 first2, ForwardIterator2 last2);
template <typename ForwardIteratorl, typename ForwardIterator2,
typename BinaryPredicate>
ForwardIteratorl find_first_of(ForwardIteratorl firstl, ForwardIteratorl lastl,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
Описание
Алгоритм аналогичен алгоритму find с тем отличием, что вместо поиска единственного значения он выполняет поиск любого из значений диапазона [first2;last2).
Первая версия алгоритма обходит диапазон [firstl;lastl) и возвращает первый итератор i такой, что для некоторого итератора j из диапазона [first2;last2) выполняется равенство * i == * j.
Во второй версии искомым условием является не*i == *j, a pred(*i,*j)== true.
В любом случае, если такой итератор не найден, возвращается итератор lastl.
Временная сложность
Квадратичная. Если N — размер диапазона [firstl;lastl), а М— размер диапазона [first2;last2), то количество применений == (или pred в случае версии с предикатом) не превышает NM.
Алгоритм adjacent_find
Прототипы
template<typename ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);
template<typename ForwardIterator, typename BinaryPredicate>
ForwardIterator adjacent_find(Forwardlterator first,Forwardlterator last,
BinaryPredicate binary_pred);
Описание
Алгоритм adjacent_find возвращает итератор i, указывающий на первый из последовательных дубликатов в диапазоне [first;last), или last, если такого элемента нет. Последовательный дубликат — это элемент, эквивалентный элементу, следующему непосредственно за ним в диапазоне.
Сравнение выполняется с применением оператора == в первой версии алгоритма и функционального объекта binary_pred во второй версии.
Временная сложность
Линейная. Количество сравнений равно размеру диапазона [first; i).
#include<iostream>
#include<deque>
#include<algorithm>
#include<functional>
#include<string>
using namespace std;
int main()
{
deque<string> player(5);
deque<string>::iterator i;
//заполнение дека
player[0]="Pele";
player[1]="Platini";
player[2]="Maradona";
player[3]="Maradona";
player[4]="Rossi";
//Поиск первой пары одинаковых последовательных имен
i=adjacent_find(player.begin(),player.end());
cout<<"("<<*i<<","<<*(i+1)<<")\n";
//Поиск первого имени, лексикографически большего,
//чем следующего за ним
i=adjacent_find(player.begin(),player.end(),greater<string>());
cout<<"("<<*i<<","<<*(i+1)<<")\n";
return 0;
}
Результаты выполнения программы:
(Maradona,Maradona)
(Platini,Maradona)
Алгоритм count
Прототипы
template <typename InputIterator, typename T>
typename iterator_traits<Inputlterator>::difference_type
count(InputIterator first, InputIterator last, const T& value);
template <typename Inputlterator, typename Predicate>
typename iterator_traits<InputIterator>::difference_type
count_if(InputIterator first, InputIterator last, Predicate pred);
Описание
Алгоритм count возвращает количество элементов диапазона [first; last), равных value.
Алгоритм count_if возвращает количество итераторов диапазона [first; last), для которых выполняется равенство pred(* i) == true.
Временная сложность
Линейная. Количество выполняемых сравнений равно размеру диапазона [first; last).
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
int main()
{
int a[]={0,0,0,1,1,1,2,2,2};
//Подсчет количества единиц в массиве a
cout<<count(&a[0],&a[9],1)<<endl;
//Определение количества элементов массива a, которые не равны 1
cout<<count_if(&a[0],&a[9],bind2nd(not_equal_to<int>(),1))<<endl;
return 0;
}
Результаты выполнения программы:
3
6