C++. Обобщенные алгоритмы. adjacent_find (алгоритм поиска)

Опубликовано 09.07.2013 | Автор: admin

adjacent_find принадлежит к группе обобщенных алгоритмов и по умолчанию выполняет поиск первого вхождения одинаковых элементов, являющихся соседними.

10 20 30 30 30 40 10

В показанной последовательности есть несколько пар одинаковых элементов, но первыми соседничают выделенные красным 30 и 30. Алгоритм находит вхождение первой пары и возвращает итератор (аналог указателя) на первый элемент найденной пары, либо, если не нашлось ничего, итератор на конец последовательности. С помощью найденного итератора можно вытащить найденое значение, либо использовать итератор для других целей.

C++ 		Листинг #1.1		adjacent_find
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    vector<int> v = {10, 20, 30, 30, 30, 30, 40, 10};
    vector<int>::iterator it;    //для сохранения результатов adjacent_find

    it = adjacent_find(v.begin(), v.end());

    cout << *it;        //Выводим найденное значение
}

C++ Листинг #1.1 adjacent_find

#include <iostream>

#include <algorithm>

using namespace std;

int main(){

vector<int> v = {10, 20, 30, 30, 30, 30, 40, 10};

vector<int>::iterator it; //для сохранения результатов adjacent_find

it = adjacent_find(v.begin(), v.end());

cout << *it; //Выводим найденное значение

}

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

	//C++	Листинг #1.2
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    setlocale(LC_ALL, "");
    vector<int> v = {10, 20, 30, 40, 10};
    vector<int>::iterator it;    //для сохранения результатов adjacent_find

    it = adjacent_find(v.begin(), v.end());

    if (it !=v.end()){
      cout << *it << '\n';        //Выводим найденное значение
    } else {
      cout << "нет ни одной одинаковой пары значений\n";
    }
}

//C++ Листинг #1.2

#include <iostream>

#include <algorithm>

using namespace std;

int main(){

setlocale(LC_ALL, "");

vector<int> v = {10, 20, 30, 40, 10};

vector<int>::iterator it; //для сохранения результатов adjacent_find

it = adjacent_find(v.begin(), v.end());

if (it !=v.end()){

cout << *it << '\n'; //Выводим найденное значение

} else {

cout << "нет ни одной одинаковой пары значений\n";

}

Если работать с итераторами как с указателями, то можно смещаться относительно найденной позиции. cout << *(it + 1); выведет второе значение пары (оно всегда равно первому).

Чтобы вывести все пары соседних элементов, можно сделать цикл, в котором с нахождением очередной пары смещать итератор на следующий элемент.

//C++	Листинг #2.1      
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    setlocale(LC_ALL, "");
    vector<int> v = {40, 20, 20, 10, 20, 30, 30, 30, 40, 10};
    vector<int>::iterator it;    //для сохранения результатов adjacent_find

    it = adjacent_find(v.begin(), v.end());

    while (it !=  v.end()){
      cout << *it << " " << *(it + 1) << '\n';
      it = adjacent_find(it+1, v.end());        //Не забываем переключиться на следующий за найденным вхожением итератор
    }
}

//C++ Листинг #2.1

#include <iostream>

#include <algorithm>

using namespace std;

int main(){

setlocale(LC_ALL, "");

vector<int> v = {40, 20, 20, 10, 20, 30, 30, 30, 40, 10};

vector<int>::iterator it; //для сохранения результатов adjacent_find

it = adjacent_find(v.begin(), v.end());

while (it != v.end()){

cout << *it << " " << *(it + 1) << '\n';

it = adjacent_find(it+1, v.end()); //Не забываем переключиться на следующий за найденным вхожением итератор

}

Иногда может быть нужно немного подстроить алгоритм под себя. Например, можно искать соседей не равных друг другу, а так, чтобы правый сосед был меньше левого на 5, тогда можно написать предикатную функцию (после введения лямбда-выражений пишут не функции и функторы, а лямбда выражения). Но здесь я покажу на функции:

//C++	Листинг #3.1
#include <iostream>
#include <algorithm>

using namespace std;

bool my_predicat(int left, int right){
   return right - left == 5;     //Проверяем, что правое значение последовательности больше левого на 5
}

int main(){
    setlocale(LC_ALL, "");
    vector<int> v = {10, 20, 30, 40, 45, 10};
    vector<int>::iterator it;    //для сохранения результатов adjacent_find

    it = adjacent_find(v.begin(), v.end(), my_predicat);

    if (it !=v.end()){
      cout << *it << '\n';        //Выводим найденное значение
    } else {
      cout << "нет ни одной одинаковой пары значений\n";
    }
}

//C++ Листинг #3.1

#include <iostream>

#include <algorithm>

using namespace std;

bool my_predicat(int left, int right){

return right - left == 5; //Проверяем, что правое значение последовательности больше левого на 5

}

int main(){

setlocale(LC_ALL, "");

vector<int> v = {10, 20, 30, 40, 45, 10};

vector<int>::iterator it; //для сохранения результатов adjacent_find

it = adjacent_find(v.begin(), v.end(), my_predicat);

if (it !=v.end()){

cout << *it << '\n'; //Выводим найденное значение

} else {

cout << "нет ни одной одинаковой пары значений\n";

}

//Листинг #a1
bool my_predicat(int left, int right){
   return right - left == 5;     //Проверяем, что правое значение последовательности больше левого на 5
}

//Листинг #a1

bool my_predicat(int left, int right){

return right - left == 5; //Проверяем, что правое значение последовательности больше левого на 5

}

//Листинг #a2
bool my_predicat(int left, int right){
   if (right - left == 5){		//Проверяем, что правое значение последовательности больше левого на 5
	 return true;
   }
   return false;     
}

//Листинг #a2

bool my_predicat(int left, int right){

if (right - left == 5){ //Проверяем, что правое значение последовательности больше левого на 5

return true;

}

return false;

}

Листинги #a1 и #a2 выполняют одно и то же, просто #a1 короче, поэтому используется почти всегда именно подобное написание.

В #3.1 мы получили первое вхождение таких соседей, у которых правый больше левого на 5. Такая пара — это 40 45. Если бы нужно было в любое время задавать своё число вместо 5, следовало бы использовать лямбда-выражения или функторы:

//C++	Листинг #3.2
#include <iostream>
#include <algorithm>

using namespace std;


int main(){
    setlocale(LC_ALL, "");
    vector<int> v = {10, 20, 30, 40, 45, 10};
    vector<int>::iterator it;    //для сохранения результатов adjacent_find

    it = adjacent_find(v.begin(), v.end(), [](int left, int right){return right - left == 5; });			//Сразу по месту

    if (it !=v.end()){
      cout << *it << '\n';        //Выводим найденное значение
    } else {
      cout << "нет ни одной одинаковой пары значений\n";
    }
}

//C++ Листинг #3.2

#include <iostream>

#include <algorithm>

using namespace std;

int main(){

setlocale(LC_ALL, "");

vector<int> v = {10, 20, 30, 40, 45, 10};

vector<int>::iterator it; //для сохранения результатов adjacent_find

it = adjacent_find(v.begin(), v.end(), [](int left, int right){return right - left == 5; }); //Сразу по месту

if (it !=v.end()){

cout << *it << '\n'; //Выводим найденное значение

} else {

cout << "нет ни одной одинаковой пары значений\n";

}

//C++	Листинг #3.3
#include <iostream>
#include <algorithm>

using namespace std;


int main(){
    setlocale(LC_ALL, "");
    vector<int> v = {10, 20, 30, 40, 45, 10};
    vector<int>::iterator it;    //для сохранения результатов adjacent_find

    int dx = 5;
    it = adjacent_find(v.begin(), v.end(), [dx](int left, int right){return right - left == dx; });   //С использованием захвата

    if (it !=v.end()){
      cout << *it << '\n';        //Выводим найденное значение
    } else {
      cout << "нет ни одной одинаковой пары значений\n";
    }
}

//C++ Листинг #3.3

#include <iostream>

#include <algorithm>

using namespace std;

int main(){

setlocale(LC_ALL, "");

vector<int> v = {10, 20, 30, 40, 45, 10};

vector<int>::iterator it; //для сохранения результатов adjacent_find

int dx = 5;

it = adjacent_find(v.begin(), v.end(), [dx](int left, int right){return right - left == dx; }); //С использованием захвата

if (it !=v.end()){

cout << *it << '\n'; //Выводим найденное значение

} else {

cout << "нет ни одной одинаковой пары значений\n";

}

Про лямбда-выражения можно узнать в этой теме: С++. Лямбда-функции. Знакомство с синтаксисом

Когда я решил написать об этом алгоритме, меня привекло странное для меня название, но в итоге оказалось, что он не очень интересный, хотя, если кто-то нашёл, что искал, то это здорово.

Рубрика: Без рубрики