Алгоритмы в STL

Алгоритмы в STLSTL поддерживает различные алгоритмы, которые воздействуют на контейнеры через итераторы. Поскольку эти алгоритмы воздействуют на итераторы, а не непосредственно на контейнеры, их можно использовать с итераторами любого типа.

Алгоритмы STL являются встроенными и поэтому экономят много времени, а также более надежны. Они также повышают возможность повторного использования кода. Эти алгоритмы обычно представляют собой всего один вызов функции, и нам не нужно писать сложный код для их реализации.

Типы алгоритмов STL

STL поддерживает следующие типы алгоритмов:

  • Алгоритмы поиска
  • Алгоритмы сортировки
  • Численные алгоритмы
  • Непреобразующие/немодифицирующие алгоритмы
  • Преобразующие/модифицирующие алгоритмы
  • Алгоритмы поиска минимального и максимального элемента

Давайте подробно обсудим каждый из этих типов:

Алгоритмы поиска и сортировки

Известным алгоритмом поиска в STL является бинарный поиск. Алгоритм бинарного поиска работает с отсортированным массивом и ищет элемент, разделив массив пополам.

Для этого сначала сравнивают искомый элемент со средним элементом массива, а затем ограничивают поиск 1-й половиной или 2-й половиной массива в зависимости от того, является ли искомый элемент меньше или больше среднего элемента.

Такой двоичный поиск является наиболее широко используемым поисковым алгоритмом.

Его общий синтаксис:

binary_search(startaddr, endaddr, key)

Где,

startaddr: адрес первого элемента массива.

endaddr: адрес последнего элемента массива.

key: элемент для поиска.

Также STL предоставляет нам алгоритм «Сортировки», который используется для упорядочения элементов в контейнере в определенном порядке.

Общий синтаксис алгоритма сортировки:

sort(startAddr, endAddr);

Где,

startAddr: начальный адрес сортируемого массива.

endAddr: конечный адрес сортируемого массива.

Внутри STL использует алгоритм Quicksort для сортировки массива.

Давайте возьмем пример, для демонстрации алгоритмов поиска и сортировки:

Вывод данных:

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», предоставляя необходимые параметры.

Читать также:  Виртуальная машина Java

Сначала мы вызываем алгоритм 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 … и так далее.

Вот пример, демонстрирующий обе эти функции в программе:

Вывод данных:

Result of the accumulate function is: 142
partial_sum of array A: 21 46 110 142

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

Читать также:  Язык Java в сравнении с другими языками

Есть и другие алгоритмы, поддерживаемые заголовком 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].

Вывод данных:

The number of times ‘5’ appears in an array= 4

Как вы можете видеть в этом коде, мы определяем значение массива, а затем вызываем функцию подсчета, предоставляя диапазон значений и значение 5. Функция возвращает количество раз (счетчик), когда значение 5 появляется в диапазоне.

Давайте возьмем пример, демонстрирующий функцию «equal».

equal(first1, last1, first2) сравнивает элементы в диапазоне [first1, last1] с первым элементом, на который указывает first2, и возвращает true (истина), если все элементы равны, иначе false (ложь).

Вывод данных:

Elements in two ranges are not equal.

В приведенном выше коде мы определяем два целочисленных массива и сравниваем их соответствующие элементы с помощью функции «equal». Поскольку элементы массива не совпадают, функция equal возвращает false.

Читать также:  Строки, пары и кортежи в STL

Модифицирующие алгоритмы

Алгоритмы модификации изменяют или преобразовывают содержимое контейнеров при их выполнении.

Наиболее популярные и широко используемые алгоритмы модификации включают в себя «swap» и «reverse», которые меняют местами два значения и меняют местами элементы в контейнере соответственно.

Давайте посмотрим пример для этих функций:

Вывод данных:

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 использует для сравнения оператор ‘<‘.

Давайте посмотрим на работу этих функций с помощью программы:

Вывод данных:

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 независимо от контейнеров.

С Уважением, МониторБанк

Добавить комментарий