Урок №101. Алгоритми в Стандартній бібліотеці С++

  Юрій  | 

  Оновл. 17 Січ 2021  | 

 95

На даному уроці ми розглянемо використання алгоритмів зі Стандартної бібліотеки С++.

Бібліотека алгоритмів

Початківці зазвичай витрачають досить багато часу на написання користувацьких циклів для виконання відносно простих завдань, таких як: сортування, пошук або підрахунок елементів масивів. Ці цикли можуть стати проблематичними як з точки зору того, наскільки легко в них можна зробити помилку, так і з точки зору загальної надійності і зручності використання.

Оскільки пошук, підрахунок і сортування є дуже поширеними операціями в програмуванні, то до складу Стандартної бібліотеки C++ вже додано великий набір функцій, які виконують ці завдання за всього лише декілька рядків коду. На додаток до цього, ці функції вже попередньо протестовані, ефективні і мають підтримку безлічі різних типів контейнерів. А деякі з цих функцій підтримують і розпаралелювання — можливість виділяти кілька потоків ЦП для однієї і тієї ж задачі, щоб виконати її швидше.

Функціонал, що надається бібліотекою алгоритмів, зазвичай відноситься до однієї з наступних 3-х категорій:

   Інспектори — використовуються для перегляду (без змін) даних в контейнері (наприклад, операції пошуку або підрахунку елементів).

   Мутатори — використовуються для зміни даних в контейнері (наприклад, операції сортування або перестановки елементів).

   Фасилітатори — використовуються для генерації результату на основі значень елементів даних (наприклад, об’єкти, які множать значення, або об’єкти, які визначають, в якому порядку пари елементів повинні бути відсортовані).

Дані алгоритми розташовані в бібліотеці алгоритмів (заголовок algorithm). На цьому уроці ми розглянемо деякі з найбільш поширених алгоритмів.

Примітка: Всі ці алгоритми використовують ітератори.

Алгоритм std::find() і пошук елемента по значенню

Функція std::find() виконує пошук першого входження заданого значення в контейнері. В якості аргументів std::find() приймає 3 параметри:

   ітератор для початкового елементу в послідовності;

   ітератор для кінцевого елементу в послідовності;

   значення для пошуку.

В результаті повернеться ітератор, який вказує на елемент з шуканим значенням (якщо він знайдений) або кінець контейнера (якщо елемент не знайдено). Наприклад:

Примітка: Для коректної роботи всіх прикладів даного уроку ваш компілятор повинен підтримувати стандарт С++17. Детально про те, як використовувати функціонал C++17 у вашій IDE, читайте тут.

Приклад, в якому елемент знайдено:

Enter a value to search for and replace with: 5 234
13 90 99 234 40 80

Приклад, в якому елемент не знайдено:

Enter a value to search for and replace with: 0 234
Could not find 0
13 90 99 5 40 80

Алгоритм std::find_if() і пошук елемента з умовою

Іноді ми хочемо побачити, чи є в контейнері значення, яке відповідає певній умові (наприклад, рядок, що містить задану частину).

У таких випадках функція std::find_if() буде ідеальним помічником. Вона працює аналогічно функції std::find(), але замість того, щоб передавати значення для пошуку, ми передаємо об’єкт, що викликається, наприклад, вказівник на функцію (або лямбду — про це трохи пізніше), який перевіряє, чи знайдено збіг. Функція std::find_if() буде викликати цей об’єкт для кожного елемента, поки не знайде шуканий елемент (або в контейнері більше не залишиться елементів для перевірки).

Ось приклад використання функції std::find_if() для перевірки того, чи містять будь-які елементи частину "nut":

Результат виконання програми:

Found walnut

Якби ми вирішували це завдання звичайним стандартним способом, то нам би знадобилося, принаймні, два цикли (один для циклічного перебору масиву і один для порівняння шуканої частини). Функції Стандартної бібліотеки С++ дозволяють зробити те ж саме лише за декілька рядків коду!

Алгоритми std::count()/std::count_if() і підрахунок входжень елемента

Функції std::count() і std::count_if() шукають всі входження елементу або елемент, який відповідає заданим критеріям.

У наступному прикладі ми підрахуємо, скільки елементів містить частину "nut":

Результат виконання програми:

Counted 2 nut(s)

Алгоритм std::sort() і користувацьке сортування

Раніше ми використовували std::sort() для сортування масиву в порядку зростання, але можливості std::sort() цим не обмежуються. Є версія std::sort(), яка приймає допоміжну функцію в якості третього параметру, що дозволяє виконувати сортування так, як нам цього захочеться. Дана допоміжна функція приймає два параметри для порівняння і повертає true, якщо перший аргумент повинен бути впорядкований перед другим. За замовчуванням, std::sort() сортує елементи в порядку зростання.

Давайте спробуємо використати std::sort() для сортування масиву в зворотному порядку за допомогою допоміжної користувацької функції для порівняння greater():

Результат виконання програми:

99 90 80 40 13 5

Знову ж таки, замість того, щоб самостійно писати з нуля свої цикли/функції, ми можемо впорядкувати наш масив так, як нам подобається, з використанням всього лише декількох рядків коду!

Порада: Оскільки сортування в порядку спадання також дуже поширене, то C++ надає користувацький тип std::greater{} для цього завдання (який знаходиться в заголовку functional). У прикладі, наведеному вище, ми можемо замінити:

на

Зверніть увагу, std::greater{} потребує фігурні дужки, тому що це не функція, що викликається, а тип даних, і для його використання нам потрібно створити екземпляр. Фігурні дужки створюють анонімний об’єкт даного типу (який потім передається в якості аргументу в функцію std::sort()).

Алгоритм std::for_each() і всі елементи контейнера

Функція std::for_each() приймає список в якості вхідних даних і застосовує користувацьку функцію до кожного елементу цього списку. Це корисно, коли нам потрібно виконати одну і ту ж операцію з усіма елементами списку.

Ось приклад, де ми використовуємо std::for_each() для подвоєння всіх чисел масиву:

Результат виконання програми:

2 4 6 8

Новачкам даний спосіб може здатися непотрібним алгоритмом, тому що еквівалентний код з використанням циклу for з явним зазначенням діапазону буде коротшим і простішим. Але плюс std::for_each() полягає в тому, що у нас є можливість повторного використання тіла циклу і застосування розпаралелювання при його обробці, що робить std::for_each() більш підходящим інструментом для великих проектів з великим об’ємом даних.

Порядок виконання

Зверніть увагу, що більшість алгоритмів з бібліотеки алгоритмів не гарантують певного порядку виконання. Для використання таких алгоритмів вам потрібно подбати про те, щоб будь-які функції, що передаються, не мали заданого порядку виконання, так як порядок виклику цих функцій може бути різним у залежності від використовуваного компілятора.

Наступні алгоритми гарантують послідовне виконання:

   std::for_each()

   std::copy()

   std::copy_backward()

   std::move()

   std::move_backward()

Порада: Якщо не вказано інше, то вважайте, що для алгоритмів зі Стандартної бібліотеки С++ порядок виконання є невизначеним. Вищенаведені алгоритми дають гарантію послідовного виконання.

Діапазони в C++20

Необхідність для кожного алгоритму явно передавати arr.begin() і arr.end() може трохи дратувати. Але в стандарті C++20 доданий такий інструмент, як діапазони, який дозволяє просто передавати arr. Завдяки цьому ми можемо зробити наш код коротшим і читабельнішим.

Висновки

Бібліотека алгоритмів має багато корисних функцій, які можуть зробити ваш код простішим і надійнішим. На цьому уроці ми розглянули лише невелику частину алгоритмів, але, оскільки більшість з них працюють схожим чином, то як тільки ви розберетеся з деякими з них, ви зможете без великих труднощів використовувати і всі інші.

Порада: Надавайте перевагу використанню функцій з бібліотеки алгоритмів, ніж самостійному написанню власного функціоналу для виконання даних завдань.

Оцінити статтю:

1 Зірка2 Зірки3 Зірки4 Зірки5 Зірок (2 оцінок, середня: 5,00 з 5)
Loading...

Залишити відповідь

Ваш E-mail не буде опублікований. Обов'язкові поля відмічені *