C++. Для начинающих несколько примеров использования обобщённых алгоритмов
Кто-то из вас уже встречался с упоминанием алгоритмов STL, кто-то ещё встретится. А что это такое? Когда кто-то говорит об алгоритмах, первое что обычно приходит на ум новичку — это те блоксхемы, которые он рисовал на уроках информатики.
- Алгоритмы STL — это встроенные в C++ функции, помогающие работать с STL-объектами (векторами, списками, очередями, деревьями...)
Алгоритмы STL — это шаблонные функции, которые, как правило, принимают на вход начало и конец последовательности и часто может принимать фрагмент исполняемого кода (фрагментом может быть функция, лямбда-функция, функтор: всё, что работает как функция), иногда вместо фрагмента кода обычное значение. Шаблонные функции — это такие функции, которые отвязаны от конкретного типа.
Всем, кто решал задачи с массивами, известны часто встречающиеся: найти в массиве максимальный и минимальный элемент, отсортировать массив, посчитать число четных или нечетных элементов, определить, содержится ли в массиве какое-то значение и многие другие. Так вот набор функций для решения этих задач разделили на группы и назвали этот набор групп функций, встроенных в язык, алгоритмами.
- Для подключения возможности использовать алгоритмы STL нужно задействовать директиву алгоритмов: #include <algorithm>
Преимущество использования алгоритмов в том, что они в большинстве своём настраиваемые, благодаря возможности подавать им фрагменты кода. Если вы понимаете, что такое возвращаемое значение из функции — вы легко поймёте, как оно влияет на работу алгоритмов. Но о настраиваемости чуть позже: не все алгоритмы умеют принимать фрагменты кода. Для начала выполним поиск в массиве заданного значения:
АЛГОРИТМЫ ПОИСКА
|
1 2 3 4 5 6 7 8 9 10 11 |
//C++ STL Листинг #1.1 find #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ vector<int> v = {77, 88, 99, 111, 2222}; //для сокращения кода я сразу инициализировал вектор значениями find(v.begin(), v.end(), 99); } |
В #1.1 алгоритму задаются начало и конец последовательности (вектора v) и искомое значение (99). Алгоритм отрабатывает и возвращает результат, только он возвращает не булево значение (что может кто-то ожидать), а итератор на найденный элемент или на конец последовательности. Если не знаете, что такое итераторы, то можете их воспринимать как указатели. Это своеобразные указатели, направляемые на кконкретные элементы контейнеров. Так вот, если итератор достиг конца вектора, то, значит, искомого элемента в векторе нет, но если не достиг, то можно выявить позицию или просто сориентироваться, что коли элемент есть, то надо что-то сделать:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//C++ STL Листинг #1.2 find #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {77, 88, 99, 111, 2222}; if (find(v.begin(), v.end(), 99) != v.end()){ //Проверяем на достижение v.end() cout << "Элемент 99 найден\n"; } else { cout << "Элемент 99 не найден\n"; } } |
Чтобы определить позицию найденного элемента, нужно от полученного результата вычесть v.begin(). Можно искать с помощью функции distance, но я по инерции продолжу как сделал. Сейчас будет правильно считающий позицию существующего элемента, но немного неправильный код:
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//C++ STL Листинг #1.3 find #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {77, 88, 99, 111, 2222}; cout << find(v.begin() , v.end(), 88)) - v.begin() << '\n'; } |
Неправильно здесь то, что этот код не учитывает, что у искомого значения может не быть позиции в векторе (что значения в векторе нет). Это можно исправить, если дважды написать алгоритм, но зачем два раза выполнять один алгоритм, если можно запомнить итератор на найденный элемент, а потом использовать этот итератор как результат алгоритма?
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//C++ STL Листинг #1.3 find #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {77, 88, 99, 111, 2222}; vector<int>::iterator it; it = find(v.begin(), v.end(), 99); if (it != v.end()){ cout << it - v.begin() << '\n'; } else { cout << "элемента нет в векторе\n"; } } |
Вообще к итераторам придётся привыкать. Многие алгоритмы возвращают именно их. В целом, итераторы похожи на указатели, для них работает практически всё, что работает для указателей, поэтому часто итераторы и указатели приравнивают.
Алгоритм find работает не с фрагментом кода, а непосредственно со значением в третьем параметре, поэтому его нельзя использовать для поиска по условию. Для поиска по условию используют алгоритм find_if. Понятие настраиваемости алгоритмов как раз и означает, что алгоритму можно задавать условия с помощью функций, функторов и лямбда-выражений (всего, что можно использовать как функции).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
//C++ STL Листинг #2.1 find_if #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; bool my_pred(int value){ //Функция (фрагмент кода) для поиска по критерию if (value > 10){ return true; } return false; } int main(){ setlocale(LC_ALL, ""); vector<int> v = {7, 88, 99, 111, 2222}; vector<int>::iterator it; //Итератор для хранения результата работы алгоритма it = find_if(v.begin(), v.end(), my_pred); //запоминаем результат if (it != v.end()){ //если алгоритм не добрался до конца вектора cout << *it << "найден: "; //то элемент, удовлетворяющий условию поиска, нашёлся } } |
Функции, возвращающие булевы значения и служащие для обозначения критериев, называют предикатными или предикатами. В #2.1 предикатную функцию можно сократить, оставив возвращаемым значением только само условие. Это удобно, поэтому так делают все:
|
1 2 3 |
bool my_pred(int value){ //Функция (фрагмент кода) для поиска по критерию return value > 10; } |
Обходимый алгоритмом элемент последовательности, можно сказать, вшит в работу алгоритма, поэтому его не нужно указывать предикатоной функции. Если алгоритм предполагает работу с одним элементом обходимого контейнера, то предикатная функция должна принимать один элемент. Алгоритм подставит в параметр функции обходимый элемент. Проблема в #2.1 в том, что значение для сравнения жёстко вшито в предикатную функцию. Из-за этого нет возможности выбирать любое значение в любой момент времени. Ведь может быть необходимость вместо 10 подставлять другие значения. Это обходится либо с помощью функциональных адаптеров (так делали раньше), либо с помощью функторов или лямбда-функций.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//C++ STL Листинг #2.2 find_if #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {7, 88, 99, 111, 2222}; vector<int>::iterator it100; vector<int>::iterator it200; it100 = find_if(v.begin(), v.end(), [](int value){ return value > 100; }); it200 = find_if(v.begin(), v.end(), [](int value){ return value > 200; }); if (it100 != v.end()){ //если алгоритм не добрался до конца вектора cout << *it100 << ">100 найден "; //то элемент, удовлетворяющий условию поиска, нашёлся } cout << '\n'; if (it200 != v.end()){ //если алгоритм не добрался до конца вектора cout << *it200 << ">200 найден "; //то элемент, удовлетворяющий условию поиска, нашёлся } } |
Поскольку итераторы практически указатели, то разыменованием итератора часто можно получить значение, на которое итератор направлен. Иногда может быть нужно найти все элементы последовательности, удовлетворяющие условию, тогда поскольку find_if ищет только первое вхождение, нужно зацикливать поиск:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//C++ STL Листинг #2.3 find_if #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {7, 88, 99, 111, 2222}; vector<int>::iterator it; //Итератор для сохранения результатов работы алгоритма vector<int>::iterator beg; //Итератор для отслеживания последней найденной позиции beg = v.begin(); //Устанавливаем отслеживатель позиции на начало вектора while (it != v.end()){ it = find_if(beg, v.end(), [](int value){ return value > 100; }); if (it != v.end()){ cout << *it << '\n'; //будут выведены все элементы, большие 100 } beg = it + 1; //Устанавливаем отслеживатель за найденный элемент } } |
При создании циклов, подобных в #2.3 у начинающих возможны ошибки, когда последовательность обходится каждый раз с самого начала (т. е. обход уже обойдённого) и когда забывают переместиться на один элемент вперёд (из-за чего итератор зацикливается на найденной позиции). В общем, нужно отслеживать позиции, на которые нацелены итераторы и не забывать смещать точку старта для циклов. Вообще #2.3 можно оформить более красиво, если ещё и вывести на экран позиции найденных элементов:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
//C++ STL Листинг #2.4 find_if #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {7, 88, 99, 111, 2222}; vector<int>::iterator it; //Итератор для сохранения результатов работы алгоритма vector<int>::iterator beg; //Итератор для отслеживания последней найденной позиции beg = v.begin(); //Устанавливаем отслеживатель позиции на начало вектора int number = 100; //число для сравнения while (it != v.end()){ it = find_if(beg, v.end(), [number](int value){ return value > number; }); if (it != v.end()){ cout << "v[" << it - v.begin() << "]" << "==" << *it << " > " << number << '\n'; //будут выведены все элементы, большие 100 } beg = it + 1; //Устанавливаем отслеживатель за найденный элемент } } |
Я для примеров использую лямбда-выражения. Это просто короче, чем если бы я приводил примеры на функторах, да и использование лямбда-выражений в таких ситуациях после принятия С++11 довольно популярное занятие. Вот, например, так может выглядеть поиск по диапазону:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//C++ STL Листинг #2.5 find_if и лямбда-выражение #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {7, 88, 99, 111, 2222}; vector<int>::iterator it; //Итератор для сохранения результатов работы алгоритма vector<int>::iterator beg; //Итератор для отслеживания последней найденной позиции beg = v.begin(); //Устанавливаем отслеживатель позиции на начало вектора int left = 100; //Левая и правая границы диапазона int right = 200; it = find_if(beg, v.end(), [left, right](int value){ return value >= left && value <= right; }); if (it !=v.end()){ cout << "нашлось вхождение: " << *it << '\n'; //нашлось вхождение x, где [100 <= x <= 200] } } |
Без лямбда-выражения #2.5 мог бы выглядеть так:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
//C++ STL Листинг #2.6 find_if и функтор #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; struct MyFunctor{ const int left; const int right; int searching; MyFunctor(const int left_, const int right_):left(left_), right(right_){} bool operator()(int value){ //<-- В value приходит обходимый алгоритмом элемент searching = value; //<-- Запоминаем этот элемент в структуре return value >= left && value <= right; } }; int main(){ setlocale(LC_ALL, ""); vector<int> v = {7, 88, 99, 111, 2222}; vector<int>::iterator it; //Итератор для сохранения результатов работы алгоритма vector<int>::iterator beg; //Итератор для отслеживания последней найденной позиции MyFunctor mf(100, 200); //Будем искать элементы в диапазоне [100..200] it = find_if(v.begin(), v.end(), mf); if (it !=v.end()){ cout << "нашлось вхождение: " << *it << '\n'; //нашлось вхождение x, где [100 <= x <= 200] } } |
У алгоритмов, который не предполагают в своём третьем параметре прямых значений всё вертится вокруг исполняемого кода (функций, функторов, лямбда-выражений). Если человек умеет использовать функции, но не знает ничего про функторы или лямбда-выражения, то он немного ограничен в использовании алгоритмов, в том плане, что, если фрагменту кода надо докинуть кроме элемента обходимой последовательности что-то ещё (как в случае с поиском по диапазону), то нужно использовать такие объекты языка, которые умеют сохранять состояние (функции как раз не умеют, а функторы умеют, а лямбда-выражения умеют подхватывать данные). Иногда может быть нужно ещё использовать и функциональные адаптеры: это когда алгоритм предполагает одно число параметров, а используемый для него фрагмент кода предполагает другое число. Если будет желание проникнуться базовыми знаниями в этой области, то можете почитать:
- Функторы в С++. Начало знакомства
- С++. Лямбда-функции. Знакомство с синтаксисом
- Функциональные адаптеры С++. Ознакомление и описание принципа. Примеры использования std::bind, std::bind1st, std::bind2nd (Сейчас это устаревает, но можно встречать в разных кодах)
В семейство алгоритмов поиска входит алгоритм search. В отличие от файндеров (тех, что начинаются с find), ищет он не значение, а последовательность. Им можно искать, например, подстроку в строке, либо подмассив в массиве. Чтобы его использовать, нужно прежде всего понимать, что нужно будет использовать в параметрах: начало и конец последовательности, в которой ищут, начало и конец последовательности, которую ищут, ну и условие поиска, если оно будет нужно.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
//C++ Листинг #3.1 search (поиск подстроки в строке) #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL #include <string> using namespace std; int main(){ setlocale(LC_ALL, ""); string S = "hello world, "; string text = "llo"; string::iterator it = search(S.begin(), S.end(), text.begin(), text.end()); if (it != S.end()){ cout << "Подстрока " << text << " в строке \"" << S << "\"найдена\n"; cout << "На позиции: " << it - S.begin() << '\n'; } else { cout << "Подстрока " << text << " в строке \"" << S << "\"не найдена\n"; } } |
Вообще у типа string есть свой собственный способ искать подстроки, а #2.3 был приведён только для общего понимания. Предпочитать следует встроенный в string поиск. Обычно search используют для обнаружения подмассивов:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
//C++ STL Листинг #3.2 (search) и (массив []) #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL #include <string> using namespace std; int main(){ setlocale(LC_ALL, ""); const int N = 10; int arr[N] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; //массив, в котором ищем int match[] = {40, 50, 60}; //массив, какой ищем int* it = search(arr, arr + N, match, end(match)); //указатель в роли итератора if (it != (arr + N) ){ cout << "Подмассив match в arr обнаружен на позиции: " << it - arr << '\n'; } else { cout << "Подмассив match в arr не обнаружен\n"; } } |
Итераторы для неклассовых типов — это обычные указатели на типы хранимых в обходимых последовательностях данных. Поскольку в #3.2 массив хранит int'ы (массив [] — это неклассовый тип), то итератор должен быть указателем на int. Тут нужно только ещё уметь понимать, как определять границы последовательностей. Для массивов, что с квадратными скобками, можно либо выводить количество элементов и отталкиваться от результата, либо определять итератор с помощью функций begin или end. Поскольку у match (в #3.2) размер явно не задан, я использовал функцию для определения итератора на последний элемент. Этот трюк может не сработать, если где-то от массива останется только указатель на первый элемент. Но это не меняет сути. В любом случае следует понимать, как определять границы искомого объекта. Для векторов всё намного проще, чем для массивов, потому что у них всегда можно сориентироваться на начало и конец:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//C++ STL Листинг #3.3 (search) и (vector) #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> arr = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; //массив, в котором ищем vector<int> match = {40, 50, 60}; //массив, какой ищем vector<int>::iterator it = search(arr.begin(), arr.end(), match.begin(), match.end()); if (it != arr.end()){ cout << "последовательность match найдена в arr на позиции " << it - arr.begin() << '\n'; } else { cout << "последовательность match не найдена в arr\n"; } } |
В #3.3 в качестве последовательности используется вектор (классовый тип), поэтому итератор уже не обычный указатель.
Иногда может случиться так, что для искомой последовательности и объекта, в котором она ищется, может быть не определена операция сравнения. Тогда алгоритму search будет нужно подсказывать, как производить сравнение. Такую подсказку можно сделать с помощью предикатной функции.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//C++ STL Листинг #3.4 (search) и (отсутствие операции сравнения между искомыми элементами и элементами последовательности) #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; struct A{ int x; A(int x):x(x){} }; int main(){ setlocale(LC_ALL, ""); vector<int> match = {40, 60, 60}; //массив, какой ищем vector<A> v = {10, 20, 30, 40}; search(v.begin(), v.end(), match.begin(), match.end()); //<-- Ошибка в сравнении } |
В #3.4 сравнивается int-значение вектора v и A-значение вектора match. Так мало того, что типы не совпадают, тут ещё и не к значению x обращение идёт. Чтобы исправить это, нужно научить алгоритм сравнивать внешние для структуры элементы с x-значениями структуры. Сделать это можно с помощью вспомогательной функции, которую задействовать как предикат:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
//C++ STL Листинг #3.5 (search) и (вектор структур и вектор целых чисел) #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; struct A{ int x; A(int x):x(x){} }; bool pred(A x, int y){ //Первый параметр x имеет тип A, return x.x == y; //Сравниваем элемент структуры с числом из последовательности целых чисел } int main(){ setlocale(LC_ALL, ""); vector<int> match = {20, 30}; //массив, какой ищем vector<A> v = {10, 20, 30, 40}; vector<A>::iterator it = search(v.begin(), v.end(), match.begin(), match.end(), pred); /* ЭТО ДЛЯ КРАСОТЫ */ cout << "v ==> "; for (const auto &i: v){ cout << i.x << " "; } cout << '\n'; cout << "match ==> "; for (const auto &i: match){ cout << i << " "; } cout << '\n'; /* КОНЕЦ КРАСОТЫ */ if (it != v.end()){ cout << "Последовательность найдена\n"; } else { cout << "Последовательность не найдена\n"; } } |
Благодаря возможности использовать предикаты, мы смогли подсказать нуждающемуся в подсказке алгоритму, как нужно делать сравнение, после чего алгоритм с лёгкостью исполнил свою задачу.
Есть еще бинарный поиск: binary_search: он ищет значение, не последовательность. Бинарный поиск в разы быстрее find, но выполняется он, только если диапазон значений, в котором ищется элемент, отсортирован по возрастанию. Этот поиск не возвращает итератор на найденный элемент, а возвращает булево значение, нашёлся элемент или нет. Из-за этого нельзя понять позицию найденного. Чтобы использовать бинарный поиск с возможностью определения позиций, следует использовать одну из разновидностей бинарного поиска вхождения последовательности: lower_bound, upper_bound, equal_range.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//C++ STL Листинг #4.1 binary_search #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {77, 20, 88, 30}; //массив, какой ищем sort(v.begin(), v.end()); //алогритм сортировки for (const auto &i:v){ cout << i << ' '; } cout << '\n'; int number = 77; //искомое значение bool result = binary_search(v.begin(), v.end(), number); //Бинарный поиск возвращает булев тип if (result){ cout << number << " найдено\n"; } else{ cout << number << " не найдено\n"; } } |
Особое внимание, что перед поиском вектор сортируется по возрастанию, а результат поиска — это обычное булево значение.
Бинарный поиск в отличие от find умеет работать с предикатом. Поэтому, как и в случае с search, если будет нужно докинуть способ сравнения, организовать это можно с помощью вспомогательной функции. Только нужно иметь в виду, что если тогда использовалась операция на равенство (искались одинаковые элементы), то здесь уже используется операция сравнения, ну и что требуется подать четыре параметра: начало и конец последовательности, в которой ищем, искомое значение и только потом предикат.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
//C++ STL Листинг #4.1 binary_search c предикатом #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; bool pred(int x, int y){ return x < y; // проверяем, что искомое значение больше какого-нибудь значения последовательности } int main(){ setlocale(LC_ALL, ""); vector<int> v = {77, 20, 88, 30, 99}; //массив, какой ищем sort(v.begin(), v.end()); //алгоритм сортировки for (const auto &i:v){ cout << i << ' '; } cout << '\n'; int number = 30; cout << "=====\n"; bool result = binary_search(v.begin(), v.end(), number, pred); //Бинарный поиск возвращает булев тип cout << "=====\n"; if (result){ cout << number << " найдено\n"; } else{ cout << number << " не найдено\n"; } } |
lower_bound — это разновидность бинарного поиска. Помогает найти первое вхождение, не меньшее, чем заданный элемент. А upper_bound помогает найти первое вхождение, большее, чем заданный элемент:
[0, 5, 10]
lower_bound(3)
первый элемент, не меньший 3?
5
[0, 5, 10]
upper_bound(3)
первый элемент, больший 3?
5
[0, 3, 3, 3, 10]
lower_bound(3)
первый элемент, не меньший 3?
3
[0, 3, 3, 3, 10]
upper_bound(3)
первый элемент, больший 3?
10
В коде это выглядит так:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
//C++ STL Листинг #5.1 lower_bound, upper_bound #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); //vector<int> v = {77, 20, 88, 30, 30, 30, 30, 99}; //массив, какой ищем vector<int> v = {0, 3, 3, 10}; sort(v.begin(), v.end()); //алгоритм сортировки for (const auto &i:v){ cout << i << ' '; } cout << '\n'; //////////////////////////////////////////////////////////////////////////////// int number = 3; cout << "number == " << number << "\n======================\n"; vector<int>::iterator result_low = lower_bound(v.begin(), v.end(), number); //low_bound возвращает итератор if ( result_low != v.end() ){ cout << " найдено: " << *result_low << '\n'; } else{ cout << number << " не найдено\n"; } //////////////////////////////////////////////////////////////////////////////// vector<int>::iterator result_up = upper_bound(v.begin(), v.end(), number); //Бинарный поиск возвращает булев тип if ( result_up != v.end() ){ cout << " найдено: " << *result_up << '\n'; } else{ cout << number << " не найдено\n"; } } |
Если нужно вытащить итератор на позицию найденного элемента, то можно сделать так:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//C++ STL Листинг #5.2 low_bound, итератор на первое вхождение #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {0, 3, 3, 10}; sort(v.begin(), v.end()); //алгоритм сортировки for (const auto &i:v){ cout << i << ' '; } cout << '\n'; int number = 3; cout << "number == " << number << "\n======================\n"; vector<int>::iterator result_low = lower_bound(v.begin(), v.end(), number); //low_bound возвращает итератор if ( (result_low != v.end()) && (*result_low == number) ){ //<-- добавили проверку, что элемент есть в последовательности cout << " найдено: " << *result_low << " на позиции " << result_low - v.begin() << '\n'; } else{ cout << number << " не найдено\n"; } } |
equal_range — это алгоритм поиска, который объединяет в себе работу lower_bound и upper_bound и отдаёт как результат пару итератора: один итератор — это итератор lower_bound, другой — это итератор от upper_bound. Если вы поняли пятые листинги, то и этот алгоритм поймёте.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
//C++ STL Листинг #5.3 equal_range #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {0, 3, 3, 10}; sort(v.begin(), v.end()); //алгоритм сортировки for (const auto &i:v){ cout << i << ' '; } cout << '\n'; int number = 3; cout << "number == " << number << "\n======================\n"; pair<vector<int>::iterator, vector<int>::iterator> result_bound = equal_range(v.begin(), v.end(), number); // if (result_bound.first != v.end()){ cout << "Получили выборку: "; for (vector<int>::iterator it = result_bound.first; it != result_bound.second; it++){ cout << *it << ' '; } } else { cout << "пусто\n"; } } |
#5.3 опирается на #5.2 b #5.1. В #5.3 получаем левую границу и правую границу. Левая граница — это первый элемент последовательности, не меньший, чем зававаемое значение в алгоритм, а правая — это первый элемент, что больше, чем задаваемый. То, что обяснялось в таблице выше. Опираясь на границы, можно получить диапазон значений, такой диапазон значений и выводится в результате работы на экран. Т. е. мы делаем обход от левого итератора к правому, а попутно вытаскиваем все значения из обходимой области данных.
Теперь отвлечёмся от алгоритмов поиска и посмотрим на популярные и не такие сложные. На алгоритм сортировки sort и алгоритмы счёта: count и count_if.
Алгоритм sort не возвращает ничего, поэтому его результаты никуда не запомнить. Он просто модифицирует последовательность так, чтоб элементы были упорядочены. Когда нет цели использовать конкретный вид сортировки, обычно выбирают из семейства алгоритмов сортировок именно этот.
АЛГОРИТМ СОРТИРОВКИ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
//C++ STL Листинг #6.1 sort #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); vector<int> v = {0, 3, 3, 10}; sort(v.begin(), v.end()); //сортировка по возрастанию copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //выводим вектор на экран cout << '\n'; sort(v.begin(), v.end(), greater<int>()); //сортировка по убыванию copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //выводим вектор на экран cout << '\n'; sort(v.begin(), v.end(), less<int>()); //сортировка по возрастанию copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //выводим вектор на экран cout << '\n'; } |
greater<int>() и less<int>() — это функторы, встроенные в язык. На их места вы можете вставить свои предикаты. В предикатах определить условия, что должно быть больше чего
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//C++ STL Листинг #6.2 sort #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; bool my_pred(int x, int y){ return x > y; //по убыванию //return x < y; //по возрастанию } int main(){ setlocale(LC_ALL, ""); vector<int> v = {0, 3, 3, 10}; sort(v.begin(), v.end(), my_pred); //сортировка по предикату copy(v.begin(),v.end(),ostream_iterator<int>(cout," ")); //выводим вектор на экран cout << '\n'; } |
Сортировать можно массив, только для этого нужно знать, где его границы.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
//C++ STL Листинг #6.3 sort #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; bool my_pred(int x, int y){ return x > y; //по убыванию //return x < y; //по возрастанию } int main(){ setlocale(LC_ALL, ""); int arr[] = {56, 77, 99, 22}; sort(begin(arr), end(arr), my_pred); //сортировка по предикату copy(begin(arr), end(arr), ostream_iterator<int>(cout," ")); //выводим вектор на экран cout << '\n'; } |
Из-за того, что иногда от массива остается только указатель на первый элемент, функции получения итераторов начала и конца не работают. Пример можно увидеть в #6.4.В таких ситуациях мы должны использовать арифметику указателей (что и сделано в коде).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
//C++ STL Листинг #6.4 sort #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; bool my_pred(int x, int y){ return x > y; //по убыванию //return x < y; //по возрастанию } /*Из-за того, что от массива остался олько указатель, begin(arr) и end(arr) не сработают*/ void foo(int *arr, const int N){ sort(arr, arr+N, my_pred); //сортировка по предикату copy(arr, arr+N, ostream_iterator<int>(cout," ")); //выводим вектор на экран cout << '\n'; } int main(){ setlocale(LC_ALL, ""); int arr[] = {56, 77, 99, 22}; foo(arr, end(arr) - arr); //второй аргумент — это вычисление числа элементов в массиве } |
Алгоритмы счёта могут помочь посчитать число каких-то значений в последовательности. Как и у алгоритма find, алгоритмы счёта разделяются на алгоритм простого счёта (count) и алгоритм счёта по условию (count_if. Алгоритм простого счёта не умеет работать с предикатами, а алгоритм счёта по условию умеет, поэтому, если нужно посчитать что-то, согласно какому-то условию, то нужно использовать count_if, а если просто посчитать число вхождений какого-то элемента в последовательность, то можно использовать count.
АЛГОРИТМЫ СЧЁТА
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
//C++ STL Листинг #7.1 count #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL using namespace std; int main(){ setlocale(LC_ALL, ""); int arr[] = {56, 77, 99, 56, 22}; cout << count(begin(arr), end(arr), 56) << '\n'; //выводим на экран число вхождений 56 в массив arr vector<int> v = {99, 4, 55, 9, 55, 1, 99}; cout << count(v.begin(), v.end(), 55) << '\n'; //выводим на экран число вхождений 55 в вектор v } |
Для того, чтобы искать не одно значение, а группу значений, согласно какому-то условию, то используем count_if. Посчитаем число гласных в строке:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
//C++ STL Листинг #7.2 count_if Число гласных в строке #include <vector> #include <iostream> #include <algorithm> //будем использовать алгоритмы STL #include <cstring> //для strchr (поиск символа в С-строке) using namespace std; bool vowels(char ch){ const char alphabet[255] = "аояэеуёиыю"; ch = tolower(ch); //чтоб учитывались большие буквы, приводим их к маленьким return strchr(alphabet, ch); } int main(){ setlocale(LC_ALL, ""); string S = "ПривЕт"; cout << count_if(S.begin(), S.end(), vowels) << '\n'; //иЕ ==>2 S = "ПривЕт и как ты там?"; cout << count_if(S.begin(), S.end(), vowels) << '\n'; //иЕиаыа ==>6 } |
В #7.2 считаются русские буквы. Следует понимать, что русская 'а' и латинская 'а' — это разные коды в таблице символов. Функцию определения гласных символов можете переписать в свою, суть её должна быть сведена к тому, что возвращать она должна истинну, если ch гласная.
Есть ещё много алгоритмов, но все в этой публикации поместиться не могут. На этом я остановлюсь. Надеюсь, вы узнали много полезной информации, что-то нашли или чему-то научились.
НЕКОТОРЫЕ ОБОБЩЕННЫЕ АЛГОРИТМЫ
АЛГОРИТМЫ ПОИСКА
АЛГОРИТМЫ СОРТИРОВКИ И УПОРЯДОЧИВАНИЙ
АЛГОРИТМЫ УДАЛЕНИЯ
ЧИСЛЕННЫЕ АЛГОРИТМЫ
АЛГОРИТМЫ ГЕНЕРАЦИИ И ИЗМЕНЕНИЙ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
АЛГОРИТМЫ СРАВНЕНИЯ
find()
sort()
unique()
accumulate()
generate()
equal()
find_if()
partial_sort()
remove()
partial_sum()
fill()
min()
search()
merge()
inner_product()
transform()
max()
binary_search()
partition()
adjacent_difference()
copy()
count()
rotate()
count_if()
reverse()
random_shuffle()
Вот пример поиска максимально и минимального значений в последовательности:
АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО И МИНИМАЛЬНОГО ЗНАЧЕНИЙ
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//C++ Листинг #8.1 Поиск максимального и минимального элементов #include <algorithm> #include <iostream> #include <vector> using namespace std; int main(){ int A[]={1,2,3,4,49,100,49}; vector<int> v(A,A+7); cout<<*max_element(v.begin(), v.end())<<endl; //Выводим тот индекс где максимальный элемент cout<<max_element(v.begin(),v.end())-v.begin()<<endl; //Выводим значение максимального элемента cout<<endl; cout<<*min_element(v.begin(),v.end())<<endl; //Выводим индекс где минимальный элемент cout<<min_element(v.begin(),v.end())-v.begin()<<endl; //Выводим значение минимального элемента } |
В #8.1 в одном случае используется указатель, в другом указатель не используется. Код маленький и должен быстро уложиться в вашей голове. Предлагаю вам решить несложную задачу. Выведите на экран все индексы вектора, в которых лежит минимальный элемент. Т.е. например вектор содержит [0 1 0 0 1] —-> на экран [1 4] (отсчет индексов с нуля). Приблизительный код я приводил, нужно просто создать аналогию программы.
Статья обновлена 31.12.2021
Один комментарий на «“C++. Для начинающих несколько примеров использования обобщённых алгоритмов”»
Добавить комментарий
Случайная книга в электронном формате
В Код C++ Алгоритм max_element и Алгоритм min_element небольшая ошибка: перепутани коментарии. Правильно будет так: