Алгоритми. 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)
рейтинг
51зірка1зірка1зірка1зірка1зірка
Olej

Про Olej

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

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

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

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