STL поддерживает различные алгоритмы, которые воздействуют на контейнеры через итераторы. Поскольку эти алгоритмы воздействуют на итераторы, а не непосредственно на контейнеры, их можно использовать с итераторами любого типа.
Алгоритмы STL являются встроенными и поэтому экономят много времени, а также более надежны. Они также повышают возможность повторного использования кода. Эти алгоритмы обычно представляют собой всего один вызов функции, и нам не нужно писать сложный код для их реализации.
Типы алгоритмов STL
STL поддерживает следующие типы алгоритмов:
- Алгоритмы поиска
- Алгоритмы сортировки
- Численные алгоритмы
- Непреобразующие/немодифицирующие алгоритмы
- Преобразующие/модифицирующие алгоритмы
- Алгоритмы поиска минимального и максимального элемента
Давайте подробно обсудим каждый из этих типов:
Алгоритмы поиска и сортировки
Известным алгоритмом поиска в STL является бинарный поиск. Алгоритм бинарного поиска работает с отсортированным массивом и ищет элемент, разделив массив пополам.
Для этого сначала сравнивают искомый элемент со средним элементом массива, а затем ограничивают поиск 1-й половиной или 2-й половиной массива в зависимости от того, является ли искомый элемент меньше или больше среднего элемента.
Такой двоичный поиск является наиболее широко используемым поисковым алгоритмом.
Его общий синтаксис:
| binary_search(startaddr, endaddr, key) |
Где,
startaddr: адрес первого элемента массива.
endaddr: адрес последнего элемента массива.
key: элемент для поиска.
Также STL предоставляет нам алгоритм «Сортировки», который используется для упорядочения элементов в контейнере в определенном порядке.
Общий синтаксис алгоритма сортировки:
| sort(startAddr, endAddr); |
Где,
startAddr: начальный адрес сортируемого массива.
endAddr: конечный адрес сортируемого массива.
Внутри STL использует алгоритм Quicksort для сортировки массива.
Давайте возьмем пример, для демонстрации алгоритмов поиска и сортировки:
|
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 |
#include <algorithm> #include <iostream> using namespace std; int main() { int testAry[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int arysize = sizeof(testAry) / sizeof(testAry[0]); sort(testAry, testAry + arysize); cout<<"\nSorted Array is \n"; for(int i=0;i<arysize;i++) { cout<<testAry[i]<< " "; } if (binary_search(testAry, testAry + arysize, 2)) cout << "\nKey = 2 found in the array"; else cout << "\nKey = 2 not found in the array"; if (binary_search(testAry, testAry + arysize, 10)) cout << "\nKey = 10 found in the array"; else cout << "\nKey = 10 not found in the array"; return 0; } |
Вывод данных:
| Sorted Array is 0 1 2 3 4 5 6 7 8 9 Key = 2 found in the array Key = 10 not found in the array |
В данном коде мы предоставили массив, в котором нам нужно найти ключевой элемент с помощью бинарного поиска. Поскольку для бинарного поиска требуется отсортированный массив, мы сначала сортируем массив, используя алгоритм «сортировки», а затем делаем вызов функции «binary_search», предоставляя необходимые параметры.
Сначала мы вызываем алгоритм binary_search для ключа = 2, а затем для ключа = 10. Таким образом, всего одним вызовом функции мы можем удобно выполнить бинарный поиск в массиве или отсортировать его.
Численные алгоритмы
Заголовок <numeric> в STL содержит различные функции, которые работают с числовыми значениями. Эти функции варьируются от поиска lcds, gcds до даже вычисления суммы элементов в контейнере, таком как массивы, векторы в заданном диапазоне и т. д.
В этой части мы обсудим несколько важных функций с примерами.
accumulate
Общий синтаксис функции accumulate:
| accumulate (first, last, sum); |
Эта функция возвращает сумму всех элементов в диапазоне [первый, последний] в переменной sum. В приведенной выше синтаксической нотации first и last — это адреса первого и последнего элементов в контейнере, а sum — это начальное значение переменной sum.
partial_sum
Общий синтаксис функции partial_sum:
| partial_sum(first, last, b) |
Где,
first: адрес начального элемента контейнера.
last: адрес последнего элемента контейнера.
b: массив, в котором будет храниться частичная сумма соответствующих элементов массива.
Таким образом, функция partial_sum вычисляет частичную сумму соответствующего массива или элементов вектора и сохраняет их в другом массиве.
Если a представляет элемент в диапазоне [first, last], а b представляет элемент результирующего массива, тогда partial_sum будет:
| b0 = a0 b1 = a0+a1 b2 = a0+a1+a2 … и так далее. |
Вот пример, демонстрирующий обе эти функции в программе:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include<numeric> #include<iostream> using namespace std; int main() { int A[] = {21,25,64,32}; int sum = 0; int b[4]; cout<<"\nResult of accumulate function is: "<<accumulate(A,A+4,sum); partial_sum(A,A+4,b); cout<<"\npartial_sum of array A : "; for (int i=0; i<4; i++) cout << b[i] << ' '; cout << '\n'; return 0; } |
Вывод данных:
| Result of the accumulate function is: 142 partial_sum of array A: 21 46 110 142 |
Как показано в приведенной выше программе, сначала мы вычисляем сумму элементов, используя функцию accumulate, а затем вызываем функцию partial_sum для вычисления частичной суммы соответствующих элементов массива.
Есть и другие алгоритмы, поддерживаемые заголовком STL и <numeric>:
- iota: заполняет диапазон последовательными приращениями начального значения.
- reduce: аналогичен накоплению, за исключением того, что идет не по порядку.
- inner_product: вычисляет внутренний продукт двух диапазонов элементов.
- adjacent_difference: вычисляет разницу между соседними элементами в диапазоне.
- inclusive_scan: аналогичен partial_sum, включает i-й элемент ввода в i-ю сумму.
- exclusive_scan: аналогичен partial_sum, исключает i-й элемент ввода из i-й суммы.
Немодифицирующие алгоритмы
Немодифицирующие или непреобразующие алгоритмы — это алгоритмы, которые не изменяют содержимое контейнера, в котором они работают. STL поддерживает множество немодифицирующих алгоритмов.
Мы перечислили некоторые из них ниже:
- count: возвращает количество значений в заданном диапазоне.
- equal: сравнивает элементы в двух диапазонах и возвращает логическое значение.
- mismatch: возвращает пару итераторов, когда два итератора сравниваются и возникает несоответствие.
- search: поиск заданной последовательности в заданном диапазоне.
- search_n: ищет в заданном диапазоне последовательность значений счетчика.
Давайте подробнее остановимся на функциях «count» и «equal»: count(first, last, value) возвращает количество раз, когда «значение» появляется в диапазоне [first, last].
|
1 2 3 4 5 6 7 8 9 10 |
#include <iostream> #include <algorithm> using namespace std; int main () { int values[] = {5,1,6,9,10,1,12,5,5,5,1,8,9,7,46}; int count_5 = count(values, values+15, 5); cout<<"The number of times '5' appears in array= "<<count_5; return 0; } |
Вывод данных:
| The number of times ‘5’ appears in an array= 4 |
Как вы можете видеть в этом коде, мы определяем значение массива, а затем вызываем функцию подсчета, предоставляя диапазон значений и значение 5. Функция возвращает количество раз (счетчик), когда значение 5 появляется в диапазоне.
Давайте возьмем пример, демонстрирующий функцию «equal».
equal(first1, last1, first2) сравнивает элементы в диапазоне [first1, last1] с первым элементом, на который указывает first2, и возвращает true (истина), если все элементы равны, иначе false (ложь).
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <iostream> #include <algorithm> using namespace std; int main() { int inputs1[] = { 1,2,3,4,5,6,7,8}; int inputs2[] = { -1,2,1,2,3,4,6,7,8,9}; if (equal( inputs1 , inputs1+8 , inputs2 )==1) cout<<"Elements in Two ranges are equal"; else cout<<"Elements in two ranges are not equal"; } |
Вывод данных:
| Elements in two ranges are not equal. |
В приведенном выше коде мы определяем два целочисленных массива и сравниваем их соответствующие элементы с помощью функции «equal». Поскольку элементы массива не совпадают, функция equal возвращает false.
Модифицирующие алгоритмы
Алгоритмы модификации изменяют или преобразовывают содержимое контейнеров при их выполнении.
Наиболее популярные и широко используемые алгоритмы модификации включают в себя «swap» и «reverse», которые меняют местами два значения и меняют местами элементы в контейнере соответственно.
Давайте посмотрим пример для этих функций:
|
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 |
#include <iostream> #include <utility> #include <vector> #include <algorithm> using namespace std; int main () { vector<int> vec1 = {1,1,2,3,5}; vector<int> vec2 = {2,4,6,8,10}; swap(vec1,vec2); cout<<"Vector 1 : "; for (auto it = vec1.begin(); it < vec1.end(); ++it) cout << *it << " "; cout<<endl; cout<<"Vector 2 : "; for (auto it = vec2.begin(); it < vec2.end(); ++it) cout << *it << " "; cout<<endl; reverse(vec1.begin(),vec1.end()); cout<<"Reversed Vector 1 :"; for (auto it = vec1.begin(); it < vec1.end(); ++it) cout << *it << " "; cout<<endl; reverse(vec2.begin(),vec2.end()); cout<<"Reversed Vector 2 :"; for (auto it = vec2.begin(); it < vec2.end(); ++it) cout << *it << " "; cout<<endl; return 0; } |
Вывод данных:
| Vector 1 : 2 4 6 8 10 Vector 2 : 1 1 2 3 5 Reversed Vector 1 :10 8 6 4 2 Reversed Vector 2 :5 3 2 1 1 |
Как видно, у нас есть два вектора, определенные в программе. Сначала с помощью функции swap мы меняем местами содержимое vector1 и vector2. Затем мы обращаем содержимое каждого вектора с помощью функции reverse.
Программа выводит vector 1 и vector 2 после замены их содержимого местами, а также после обращения содержимого.
Алгоритмы поиска минимального и максимального элемента
Эта категория состоит из функций min и max, которые находят минимальное и максимальное значения соответственно из заданных двух значений.
Общий синтаксис этих функций:
| max(objecta, objectb); |
Мы также можем указать третий параметр, чтобы предоставить «compare_function» или критерии, которые будут использоваться для поиска минимального/максимального значения. Если это не предусмотрено, то функция max использует для сравнения оператор ‘>’, тогда как функция min использует для сравнения оператор ‘<‘.
Давайте посмотрим на работу этих функций с помощью программы:
|
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 |
#include<iostream> #include<algorithm> using namespace std; int main() { int x=4, y=5; cout<<"Max of 4 and 5 : "; cout << max(x,y); cout<<endl; cout<<"Min of 4 and 5 : "; cout << min(x,y); string s = "smaller string"; string t = "longer string---"; cout<<endl; cout<<"\nMax string : "; string s1 = max(s, t); cout<< s1 <<endl; cout<<endl; cout<<"Min String : "; string s2 = min(s, t); cout<< s2 <<endl; } |
Вывод данных:
| Max of 4 and 5: 5 Min of 4 and 5: 4 Max String: smaller string Min String: longer string |
Приведенная выше программа не требует пояснений, поскольку мы используем функции min и max сначала для чисел, а затем для строк. Поскольку мы не предоставили необязательную ‘compare_function’, функции min/max воздействовали на операторы ‘<‘ и ‘>’ соответственно.
Итог
На этом мы подошли к концу данной статьи по основным алгоритмам, используемым в STL.
В нашей следующей статье мы подробно обсудим итераторы, а также общие функции, используемые в STL независимо от контейнеров.
С Уважением, МониторБанк