Основи програмування на С ++ для початківців

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

Контейнери 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(), рівний()

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


  1. if (color[g[v][i]] == 0)
    {
    a = make_pair(v, g[v][i]);
    b = make_pair(g[v][i], v);
    for (int j = 0; j < res.size(); j++)
    {
    if (res[j] == a || res[j] == b)
    k = false;
    }
    if (k)
    res.push_back(make_pair(v, g[v][i]));
    p[g[v][i]] = v;
    f = false;
    dfs(g, color, p, g[v][i], res);
    }

  2. //random_shuffle(suv.begin(), suv.end()); //станд::random_shuffle() функція застаріла, замінений станд::тасування().

    міняємо на
    srand(time(NULL));
    тасування(suv.begin(), suv.end(), std::default_random_engine());

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

Ваша електронна адреса не буде опублікований. Обов'язкові поля позначені * *