algorithms stl
Явне вивчення алгоритмів та їх типів у STL.
найкраще програмне забезпечення для управління завданнями для Windows -
STL підтримує різні алгоритми, які діють на контейнери за допомогою ітераторів. Оскільки ці алгоритми діють на ітератори, а не безпосередньо на контейнери, їх можна використовувати на будь-яких типах ітераторів.
Алгоритми STL вбудовані і, таким чином, економить багато часу і є також більш надійними. Вони також покращують повторне використання коду. Ці алгоритми, як правило, є лише одним викликом функції, і нам не потрібно писати вичерпний код для їх реалізації.
=> Шукайте тут цілу серію навчальних програм C ++.
Що ви дізнаєтесь:
Типи алгоритмів STL
STL підтримує наступні типи алгоритмів
- Алгоритми пошуку
- Алгоритми сортування
- Числові алгоритми
- Алгоритми, що не перетворюють / модифікують
- Трансформування / модифікація алгоритмів
- Мінімум і Максимум операцій
Ми будемо детально обговорювати кожен із цих типів у наступних параграфах.
Пошук та сортування алгоритмів
Найвидатніший алгоритм пошуку в STL - це двійковий пошук. Алгоритм двійкового пошуку працює на відсортованому масиві та здійснює пошук елемента, розділивши масив навпіл.
Для цього спочатку порівнюють шуканий елемент із середнім елементом масиву, а потім обмежують пошук до 1вулполовина або 2йполовина масиву залежно від того, чи є елемент, який потрібно шукати, меншим чи більшим за середній елемент.
Бінарний пошук - це найбільш широко використовувані алгоритми пошуку.
Його загальний синтаксис:
binary_search(startaddr, endaddr, key)
Де,
startaddr: адреса першого елемента масиву.
endaddr: адреса останнього елемента масиву.
ключ: елемент для пошуку.
STL надає нам алгоритм 'Сортування', який використовується для розташування елементів у контейнері в певному порядку.
Загальний синтаксис алгоритму сортування:
sort(startAddr, endAddr);
Де,
startAddr: початкова адреса сортуваного масиву.
endAddr: кінцева адреса сортуваного масиву.
Внутрішньо STL використовує алгоритм Quicksort для сортування масиву.
Візьмемо приклад для демонстрації алгоритму двійкового пошуку та сортування:
#include #include 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<<'
Sorted Array is
'; for(int i=0;i Вихід:
Відсортований масив - це
0 1 2 3 4 5 6 7 8 9
Ключ = 2, знайдений у масиві
Ключ = 10 не знайдено в масиві
У наведеному коді ми надали масив, в якому нам потрібно шукати ключовий елемент за допомогою двійкового пошуку. Оскільки двійковий пошук вимагає відсортованого масиву, ми спочатку сортуємо масив, використовуючи алгоритм “сортування”, а потім робимо виклик функції “binary_search”, надаючи необхідні параметри.
Спочатку ми викликаємо алгоритм binary_search для ключа = 2, а потім для ключа = 10. Таким чином, лише за допомогою одного виклику функції ми можемо зручно виконувати двійковий пошук масиву або сортувати його.
Числові алгоритми
Заголовок у STL містить різні функції, які працюють з числовими значеннями. Ці функції варіюються від пошуку lcds, gcds до навіть обчислення суми елементів у контейнері, таких як масиви, вектори над заданим діапазоном тощо.
Тут ми обговоримо кілька важливих функцій на прикладах.
(i) накопичувати
Загальний синтаксис функції накопичення:
accumulate (first, last, sum);
Ця функція повертає суму всіх елементів у межах (першого, останнього) змінної суми. У наведеному вище позначенні синтаксису first і last - це адреси першого та останнього елементів у контейнері, а sum - початкове значення змінної sum.
(ii) часткова_сума
Загальний синтаксис функції part_sum:
partial_sum(first, last, b)
Ось
перший: адреса початкового елемента контейнера.
Остання: адреса останнього елемента контейнера.
B: масив, в якому буде зберігатися часткова сума відповідних елементів масиву.
Таким чином, функція part_sum обчислює часткову суму відповідного масиву або векторних елементів і зберігає їх в іншому масиві.
Якщо a представляє елемент у діапазоні (перший, останній), а b представляє елемент у результуючому масиві, то парциальна_сума буде:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... і так далі.
Давайте подивимось приклад, щоб продемонструвати обидва Ці функції в програмі:
#include #include using namespace std; int main() { int A() = {21,25,64,32}; int sum = 0; int b(4); cout<<'
Result of accumulate function is: '< Вихід:
Результат накопичувальної функції: 142
часткова_сума масиву A: 21 46110142
Як показано у наведеній вище програмі, спочатку ми обчислюємо суму елементів за допомогою функції накопичення, а потім викликаємо функцію парциальна_сума для обчислення часткової суми відповідних елементів масиву.
Інші алгоритми, що підтримуються STL та заголовком:
- йота: Заповнює діапазон послідовними кроками початкового значення.
- зменшити: Подібно накопичуватися, за винятком несправності.
- внутрішній_продукт: Обчислює внутрішній добуток двох діапазонів елементів.
- adjacent_difference: Обчислює різницю між сусідніми елементами в діапазоні.
- включно_сканування: Подібно до часткової_суми, включає i-й елемент введення в i-ту суму.
- ексклюзивне_сканування: Подібно до часткової_суми, виключає i-й елемент введення з i-ї суми.
Немодифікуючі алгоритми
Немодифікуючі або нетрансформуючі алгоритми - це ті, які не змінюють вміст контейнера, в якому вони працюють. STL підтримує багато немодифікуючих алгоритмів.
Деякі з них ми перерахували нижче:
- рахувати: Повертає кількість значень у заданому діапазоні.
- дорівнює: Порівнює елементи у двох діапазонах і повертає логічне значення.
- невідповідність: Повертає пару ітераторів, коли два ітератори порівнюються та виникає невідповідність.
- пошук: Шукає задану послідовність у заданому діапазоні.
- search_n: Шукає в заданому діапазоні послідовність значення підрахунку.
Давайте детальніше детальніше розглянемо функції «рахувати» та «рівні» !!
count (first, last, value) повертає кількість разів, коли ‘value’ з’являється в діапазоні (first, last).
#include #include 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= '< Вихід:
Кількість випадків, коли в масиві відображається „5“ = 4
Як ви бачите в цьому коді, ми визначаємо значення масиву, а потім викликаємо функцію count, надаючи діапазон значень і значення 5. Функція повертає кількість разів (count), значення 5 з'являється в діапазоні.
Давайте візьмемо приклад, щоб продемонструвати функцію «дорівнює».
Equal (first1, last1, first2) порівнює елементи в діапазоні (first1, last1) з першим елементом, на який вказує first2, і повертає true, якщо всі елементи рівні в іншому випадку false.
#include #include 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'; }
Вихід:
Елементи в двох діапазонах не рівні.
У наведеному вище коді ми визначаємо два цілочисельні масиви та порівнюємо відповідні їм елементи, використовуючи функцію 'дорівнює'. Оскільки елементи масиву неоднакові, рівне повертає false.
Модифікація алгоритмів
Модифікуючі алгоритми змінюють або перетворюють вміст контейнерів під час їх виконання.
Найбільш популярні та широко використовувані модифікуючі алгоритми включають 'обмін' та 'зворотний', який міняє місцями два значення та реверсує елементи в контейнері відповідно.
Давайте подивимося приклади для цих функцій:
#include #include #include #include using namespace std; int main () { vector vec1 = {1,1,2,3,5}; vector vec2 = {2,4,6,8,10}; swap(vec1,vec2); cout<<'Vector 1 : '; for (auto it = vec1.begin(); it < vec1.end(); ++it) cout << *it << ' '; cout< Вихід:
Вектор 1: 2 4 6 8 10
Вектор 2: 1 1 2 3 5
Зворотний вектор 1: 10 8 6 4 2
Зворотний вектор 2: 5 3 2 1 1
Як видно, у нас є два вектори, визначені в програмі. Спочатку за допомогою функції обміну ми поміняємо місцями вміст vector1 та vector2. Далі ми змінюємо вміст кожного вектора за допомогою функції реверсу.
Програма виводить Vector 1 і Vector 2 після обміну їх вмісту, а також після зміни тексту.
Мінімальні та максимальні операції
Ця категорія складається з функцій min та max, які визначають мінімальне та максимальне значення відповідно з даних двох значень.
Загальний синтаксис цих функцій:
max(objecta, objectb); min(objecta, objectb);
Ми також можемо надати третій параметр, щоб надати 'порівняти_функцію' або критерії, за допомогою яких можна було б знайти мінімальне / максимальне значення. Якщо цього не передбачено, тоді функція max використовує оператор ‘>’ для порівняння, тоді як функція min використовує ‘<’ operator for comparison.
найкраще програмне забезпечення для створення ігор для початківців
Давайте продемонструємо ці функції за допомогою програми.
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< Вихід:
Макс. 4 і 5: 5
Мінімум 4 і 5: 4
Макс. Рядок: менший рядок
Мінімальний рядок: довший рядок
Наведена вище програма є зрозумілою, оскільки ми спочатку використовуємо функції min та max на числах, а потім на рядках. Оскільки ми не надали додаткову функцію порівняння_, функція min / max діяла відповідно на оператори.
Висновок
На цьому ми закінчили цей посібник з основних алгоритмів, що використовуються в STL.
У наступних підручниках ми детально обговоримо ітератори разом із загальними функціями, що використовуються в STL, незалежно від контейнерів.
=> Прочитайте серію навчальних програм Easy C ++.
Рекомендована література