Контейнери STL представляли б собою красиву вигадку досить далеку від практичного використання (як і було в перші роки існування STL), якби не таку обставину: через єдиної загальної природи всіх контейнерів основні алгоритми, що представляють інтерес на практиці, можуть бути реалізовані в узагальненому вигляді, застосовне до будь-яким типам контейнерів.
Алгоритми - це сама об'ємна і найбільш затребувана частина бібліотеки. Надається настільки багато алгоритмів, що для детального опису їх всіх не вистачить і об'ємної книги. Нижче ми абсолютно умовно поділимо їх на групи і назвемо по іменах (і теж далеко не все), і тільки за деякими побудуємо приклади використання.
для кожного() Найбільш часто використовуваний алгоритм - це для кожного(): виконання дії для групи елементів (можливо всіх) контейнера. Нижче показано кілька прикладів роботи алгоритму для кожного() для масиву і вектора, точно також цей алгоритм може використовуватися з будь-яким СТЛ контейнером:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <iostream> #include <vector> #include <algorithm> using namespace std; inline ostream& operator <<( ostream& out, const vector< unsigned > & obj ) { cout << "< "; for( auto& p: obj ) cout << p << " "; return out << ">"; } void pow2( unsigned& i ) { i *= i; } int main( void ) { const int examples = 4; for( int i = 0; i < examples; i++ ) { unsigned ai[] = { 1, 2, 3, 4 , 5, 6, 7, 8, 9 }, ni = sizeof( ai ) / sizeof( ai[ 0 ] ); vector< unsigned > vi( ai, ai + ni ); cout << vi; switch( i ) { case 0: for_each( vi.begin(), vi.end(), pow2 ); cout << " => " << vi << endl; break; case 1: for_each( ai, ai + ni, pow2 ); cout << " => " << vector< unsigned >( ai, ai + ni ) << endl; break; case 2: for( auto& i : ai ) pow2( i ); cout << " => " << vector< unsigned >( ai, ai + ni ) << endl; break; case 3: for_each( vi.begin() + 2, vi.end() - 2, pow2 ); cout << " => " << vi << endl; break; } } } |
Примітка: рядком 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 таку силу-силенну, що коментувати кожен – за межами розумного обсягу викладу, але всі вони працюють як один другому):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include <iostream> #include <cstring> #include <vector> #include <map> #include <set> #include <algorithm> using namespace std; inline ostream& operator <<( ostream& out, const vector<char>& obj ) { for( auto p: obj ) cout << p; return out; } int main( void ) { char s[] = "The Life and Strange Surprizing Adventures of Robinson \ Crusoe, Of York, Mariner: Who lived Eight and Twenty \ Years, all alone in an un-inhabited Island on the \ Coast of America, near the Mouth of the Great River of \ Oroonoque; Having been cast on Shore by Shipwreck, \ wherein all the Men perished but himself. With \ An Account how he was at last as strangely deliver'd \ by Pyrates"; // название книги vector<string> vs = { "Supercalifragilisticexpialidocious", // cамое длинное слово на английском языке "Pneumonoultramicroscopicsilicovolcanoconiosis" // самый длинный термин на английском языке }; // copy & find : vector<char> v1( strlen( s ) ); copy( s, s + v1.size(), v1.begin() ); int nb = 0; for( auto is = find( v1.begin(), v1.end(), ' ' ); is != v1.end(); is = find( ++is, v1.end(), ' ' ) ) nb++; cout << "в фразе пробелов " << nb << " (" << nb + 1 << " слов)" << endl; // min & max : auto mm = minmax_element( v1.begin(), v1.end() ); cout << "диапазон символов: '" << *mm.first << "' ... '" << *mm.second << "'" << endl; // fill & reverse & rotate & shuffle : vector<char> suv( vs[ 0 ].size() ); copy( vs[ 0 ].begin(), vs[ 0 ].end(), suv.begin() ); cout << suv << endl; random_shuffle( suv.begin(), suv.end() ); cout << suv << endl; reverse( suv.begin(), suv.end() ); cout << suv << endl; rotate( suv.begin(), suv.begin() + suv.size() / 2, suv.end() ); cout << suv << endl; // set_intersection & set_difference set< char > sus, pns; for( char s: vector<char>( vs[ 0 ].begin(), vs[ 0 ].end() ) ) sus.insert( s ); for( char s: vector<char>( vs[ 1 ].begin(), vs[ 1 ].end() ) ) pns.insert( s ); vector<char> outi( 100 ), outd( 100 ); auto ret = set_intersection( sus.begin(), sus.end(), pns.begin(), pns.end(), outi.begin() ); cout << "общих литер " << ( ret - outi.begin() ) << " : " << outi << endl; ret = set_difference( sus.begin(), sus.end(), pns.begin(), pns.end(), outd.begin() ); cout << "уникальных литер " << ( ret - outd.begin() ) << " : " << outd << endl; } |
Тут використані контейнери для char (як компактні, але найнеприємніші в роботі), над якими виконуються різноманітні алгоритми практично всіх позначених груп:
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);
}
Що це було, батько? ;-)
//random_shuffle(suv.begin(), suv.end()); //станд::random_shuffle() функція застаріла, замінений станд::тасування().
міняємо на
srand(time(NULL));
тасування(suv.begin(), suv.end(), std::default_random_engine());