Алгоритми. STL (частина 10)




розмір алгоритми, знайти(), копія(), copy_if(), рух(), swap_ranges(), remove_copy(), remove_copy_if(), зливатися(), set_intersection(), set_difference()Контейнери STL представляли б собою красиву вигадку досить далеку від практичного використання (як і було в перші роки існування STL), якби не таку обставину: через єдиної загальної природи всіх контейнерів основні алгоритми, що представляють інтерес на практиці, можуть бути реалізовані в узагальненому вигляді, застосовне до будь-яким типам контейнерів. Алгоритми - це сама об'ємна і найбільш затребувана частина бібліотеки. Надається настільки багато алгоритмів, що для детального опису їх всіх не вистачить і об'ємної книги. Нижче ми абсолютно умовно поділимо їх на групи і назвемо по іменах (і теж далеко не все), і тільки за деякими побудуємо приклади використання.

для кожного() Найбільш часто використовуваний алгоритм - це для кожного(): виконання дії для групи елементів (можливо всіх) контейнера. Нижче показано кілька прикладів роботи алгоритму для кожного() для масиву і вектора, точно також цей алгоритм може використовуватися з будь-яким СТЛ контейнером:

розмір алгоритми, знайти(), count(), count_if(), пошук(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), рівний()

Примітка: рядком 3 показана робота нової (введена стандартом C ++ 11) конструкції for( автоматичний &x : …), яка має подібний ефект присвоєння і може застосовуватися і до масивів і до контейнерів (в функції-операторі виведення вектора в потік показаний такий варіант). ця конструкція, взагалі то кажучи, не є складовою частиною бібліотеки STL або алгоритмів, але має той же ефект, що і алгоритм for_each(): застосувати послідовно до всіх елементів колекції.

Цей приклад показує основну логіку організації всіх алгоритмів: до зазначеного діапазону (не обов'язково до всієї колекції), обмеженому ітератором початку і кінця (часто вказуються першими 2-мя параметрами) застосовується по черзі функція, функтор, или предикат (функція, повертає логіxческій результат, дозволяє зробити відбір по будь-якою ознакою).

знайти() Наступний за значимістю алгоритм - це знайти(). Як інтуїтивно зрозуміло з імені, це пошук деякого елемента в колекції. Зверніть увагу, що багато контейнери мають метод знайти(), який для об'єкта буде викликатися як obj.find(…), в той час як алгоритм буде викликатися як знайти( OBJ:iteator, ... ).

власне, це навіть не один цей алгоритм, а ціла велика їх група, яку можна об'єднати за ознакою того, що вони відбирають елементи колекції по якомусь ознакою, умові, предикату: знайти(), find_if(), find_if_not(), find_first_of(), find_end(), adjacent_find(). У цю ж групу, з деякою натяжкою, можна віднести і count(), count_if(), пошук(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), рівний() та ін.

Ще одна умовна група - це алгоритми, деяким чином «тасующіе» колекцію, переставляють елементи місцями, змінюють значення: заповнити(), replace_copy(), зворотний(), обертати(), rotate_copy(), тасування(), random_shuffle(), перетворення(), заміщати(), replace_if() та ін.

Ще група - це алгоритми працюють з 2-ма колекціями, доСпираючись і переміщують вміст (причому, возможно, між колекціями різного виду, например, vector<> в комплект<>): копія(), copy_if(), рух(), swap_ranges(), remove_copy(), remove_copy_if(), зливатися(), set_intersection(), set_difference() та ін.

И, нарешті, зовсім особлива група алгоритмів пов'язана з різноманітними угрупованнями елементів всередині колекції: сортувати(), stable_sort(), параметр відсортовано(), is_sorted_until() та ін. Цю цікаву групу ми відкладемо на потім, для окремої докладної розгляду.

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

  • Всі об'єкти STL (контейнери, алгоритми) описані в синтаксисі шаблонів (template). Тому їх опису обов'язково повинні включатися в компільований код в складі своїх заголовків файлів (файли заголовків).

  • Відправляйтеся в стандартний каталог </USR / вмикати / C ++> і знайдіть там хедер-файли файли виду stl_algo * - В них ви знайдете все прототипи функцій алгоритмів. Більш того, там же кожному прототипу передує ґрунтовний комментарий, яка пояснювала б призначення алгоритму, і пояснює параметри виклику.

  • Розгляньте приклади коду, використовують кілька основних засх алгоритмів STL - в мережі їх безліч. За аналогією елементарно просто відтворити поведінку і всіх інших алгоритмів.

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

Як і було сказано вище, вивчення прикладів зніме безліч питань, а тому приступимо до коду … Тепер уважно стежте за руками (алгоритмів STL таку силу-силенну, що коментувати кожен – за межами розумного обсягу викладу, але всі вони працюють як один другому):

Тут використані контейнери для char (як компактні, але найнеприємніші в роботі), над якими виконуються різноманітні алгоритми практично всіх позначених груп:

розмір алгоритми, знайти(), count(), count_if(), пошук(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), рівний()

Нові уроки з програмування:

дата
сторінка
Алгоритми. STL (частина 10)
рейтинг
5
Olej

Про Olej

Стаж практичних програмних розробок близько 40 лет. Викладач міжнародної софтверної компанії Global Logic. Постійний автор публікацій IBM Developer Works. Науковий редактор книжкового видавництва комп'ютерної літератури "Символ-Плюс", Санкт-Петербург.

2 думки про "Алгоритми. STL (частина 10)

залишити коментар

Код розміщуйте в тегах: <pre class="lang:C ++ декодуванням:true ">ВАШ КОД</заздалегідь>