algorithms stl
Експлицитна студија алгоритама и његових врста у СТЛ-у.
најбољи софтвер за управљање задацима за Виндовс
СТЛ подржава разне алгоритме који делују на контејнере преко итератора. Како ови алгоритми делују на итераторе, а не директно на контејнере, могу се користити на било којој врсти итератора.
СТЛ алгоритми су уграђени и на тај начин штеде пуно времена, а такође су и поузданији. Такође побољшавају поновну употребу кода. Ови алгоритми су обично само један позив функције и не треба нам писати исцрпан код да бисмо их применили.
=> Овде потражите целу серију обука за Ц ++.
Шта ћете научити:
Типови СТЛ алгоритама
СТЛ подржава следеће типове алгоритама
- Алгоритми претраге
- Алгоритми сортирања
- Нумерички алгоритми
- Алгоритми који се не трансформишу / модификују
- Трансформирање / модификовање алгоритама
- Минимум и Макимум операција
О свакој од ових врста детаљно ћемо разговарати у следећим пасусима.
Претражите и сортирајте алгоритме
Истакнути алгоритам претраживања у СТЛ-у је бинарно претраживање. Бинарни алгоритам претраживања делује на сортираном низу и тражи елемент дељењем низа на пола.
То се постиже тако што се прво упореди елемент који треба претражити са средњим елементом низа, а затим ограничи претрагу на 1стпола или 2ндполовина низа у зависности од тога да ли је елемент који се тражи мањи или већи од средњег елемента.
Бинарна претрага је најчешће коришћени алгоритам претраживања.
Његова општа синтакса је:
binary_search(startaddr, endaddr, key) Где,
стартаддр: адреса првог елемента низа.
ендаддр: адреса последњег елемента низа.
кључ: елемент који треба претражити.
СТЛ нам пружа алгоритам „Сортирање“ који се користи за распоређивање елемената у контејнеру у одређеном редоследу.
Општа синтакса алгоритма сортирања је:
sort(startAddr, endAddr); Где,
стартАддр: почетна адреса низа који се сортира.
ендАддр: крајња адреса низа за сортирање.
Интерно СТЛ користи Куицксорт алгоритам за сортирање низа.
Узмимо пример за демонстрацију бинарног алгоритма за претрагу и сортирање:
#include #include using namespace std; int main() { int testAry() = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int arysize = sizeof(testAry) / sizeof(testAry(0)); sort(testAry, testAry + arysize); cout<<'
Sorted Array is
'; for(int i=0;i Излаз:
Сортирани низ је
0 1 2 3 4 5 6 7 8 9
Кључ = 2 пронађен у низу
Кључ = 10 није пронађен у низу
У датом коду обезбедили смо низ у којем треба да претражимо кључни елемент помоћу бинарне претраге. Пошто бинарна претрага захтева сортирани низ, прво сортирамо низ помоћу алгоритма „сортирај“, а затим упућујемо позив функције „бинарни_тражење“ давањем потребних параметара.
Прво позивамо алгоритам бинарног_тражења за кључ = 2, а затим за кључ = 10. На овај начин са само једним позивом функције можемо на једноставан начин извршити бинарно претраживање низа или га сортирати.
Нумерички алгоритми
Заглавље у СТЛ-у садржи разне функције које делују на нумеричке вредности. Ове функције се крећу од проналаска лцдс-а, гцдс-а до чак израчунавања збира елемената у контејнеру попут низова, вектора у датом опсегу итд.
Овде ћемо размотрити неколико важних функција са примерима.
(и) акумулирају
Општа синтакса функције акумулирања је:
accumulate (first, last, sum); Ова функција враћа збир свих елемената у опсегу (први, последњи) у променљивој суми. У горњој синтаксној нотацији фирст и ласт су адресе првог и последњег елемента у контејнеру, а сум је почетна вредност променљиве сум.
(ии) делимична_сума
Општа синтакса функције парцијалне_суме је:
partial_sum(first, last, b) Ево
прво: адреса почетног елемента контејнера.
Последње: адреса последњег елемента контејнера.
Б: низ у коме ће се чувати делимични збир одговарајућих елемената низа.
Дакле, функција парт_сум израчунава делимичну суму одговарајућег низа или векторских елемената и чува их у другом низу.
Ако а представља елемент у опсегу (први, последњи), а б представља елемент у резултујућем низу, тада ће парцијални_зброј бити:
б0 = а0
б1 = а0 + а1
б2 = а0 + а1 + а2… и тако даље.
Погледајмо пример за демонстрацију оба Ове функције у програму:
#include #include using namespace std; int main() { int A() = {21,25,64,32}; int sum = 0; int b(4); cout<<'
Result of accumulate function is: '< Излаз:
Резултат функције акумулације је: 142
делимични_збир низа А: 21 46 110 142
Као што је приказано у горњем програму, прво израчунавамо зброј елемената помоћу функције акумулирања, а затим позивамо функцију делимична_сума за израчунавање делимичне суме одговарајућих елемената низа.
Остали алгоритми подржани од СТЛ-а и заглавља:
- иота: Попуњава опсег узастопним повећањем почетне вредности.
- смањити: Слично акумулирању, осим ван реда.
- унутрашњи производ: Израчунава унутрашњи производ два опсега елемената.
- адјацент_дифференце: Израчунава разлике између суседних елемената у опсегу.
- инцлусиве_сцан: Слично делу_сум, укључује и-ти улазни елемент у и-том збиру.
- екцлусиве_сцан: Слично као делимична_сума, искључује и-и улазни елемент из и-тог збира.
Алгоритми који се не мењају
Алгоритми који не мењају или не трансформишу су они који не мењају садржај контејнера у којем раде. СТЛ подржава многе алгоритме који се не мењају.
Неке од њих смо навели у наставку:
- цоунт: Враћа број вредности у датом опсегу.
- једнако: Поређује елементе у два опсега и враћа логичку вредност.
- неусклађеност: Враћа пар итератора када се упореде два итератора и дође до неусклађености.
- Претрага: Претражује дати низ у датом опсегу.
- сеарцх_н: Претражује у задатом опсегу секвенцу вредности бројања.
Разрадимо више о функцијама „бројања“ и „једнаких“ !!
цоунт (прва, последња, вредност) враћа колико се пута вредност појављује у опсегу (прва, последња).
#include #include using namespace std; int main () { int values() = {5,1,6,9,10,1,12,5,5,5,1,8,9,7,46}; int count_5 = count(values, values+15, 5); cout<<'The number of times '5' appears in array= '< Излаз:
Број појављивања „5“ у низу = 4
Као што видите у овом коду, дефинишемо вредност низа, а затим позивамо функцију цоунт пружајући опсег вредности и вредност 5. Функција враћа број пута (цоунт) вредности 5 која се појављује у опсегу.
Узмимо пример за демонстрацију функције „једнаке“.
једнак (фирст1, ласт1, фирст2) упоређује елементе у опсегу (фирст1, ласт1) са првим елементом на који показује фирст2 и враћа труе ако су сви елементи у супротном фалсе.
#include #include using namespace std; int main() { int inputs1() = { 1,2,3,4,5,6,7,8}; int inputs2() = { -1,2,1,2,3,4,6,7,8,9}; if (equal( inputs1 , inputs1+8 , inputs2 )==1) cout<<'Elements in Two ranges are equal'; else cout<<'Elements in two ranges are not equal'; } Излаз:
Елементи у два опсега нису једнаки.
У горњем коду дефинишемо два целобројна низа и упоређујемо њихове одговарајуће елементе помоћу функције „једнако“. Како елементи низа нису исти, једнак враћа фалсе.
Модификовање алгоритама
Измена алгоритама модификује или трансформише садржај контејнера када се извршавају.
Најпопуларнији и најчешће коришћени алгоритми за модификовање укључују „замену“ и „обрнуто“, који замењују две вредности и преокрећу елементе у контејнеру.
Погледајмо примере за ове функције:
#include #include #include #include using namespace std; int main () { vector vec1 = {1,1,2,3,5}; vector vec2 = {2,4,6,8,10}; swap(vec1,vec2); cout<<'Vector 1 : '; for (auto it = vec1.begin(); it < vec1.end(); ++it) cout << *it << ' '; cout< Излаз:
Вектор 1: 2 4 6 8 10
Вектор 2: 1 1 2 3 5
Обрнути вектор 1: 10 8 6 4 2
Обрнути вектор 2: 5 3 2 1 1
Као што се види, у програму су дефинисана два вектора. Прво помоћу функције замене замењујемо садржај вектора1 и вектора2. Даље, преокрећемо садржај сваког вектора користећи функцију обрнуто.
Програм избацује Вецтор 1 и Вецтор 2 након замене њиховог садржаја, а такође и након обрнутог садржаја.
Минималне и максималне операције
Ова категорија се састоји од мин и мак функција које из дате две вредности сазнају минималну и максималну вредност.
Општа синтакса ових функција је:
max(objecta, objectb); min(objecta, objectb); Такође можемо да пружимо трећи параметар за пружање функције „упореди_функцију“ или критеријуме који ће се користити за проналажење мин / макс вредности. Ако ово није наведено, тада функција мак користи оператор>> за поређење док функција мин користи „<’ operator for comparison.
Покажимо ове функције помоћу програма.
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< Излаз:
Максимално 4 и 5: 5
Мин од 4 и 5: 4
Макс. Низ: мањи низ
Мин стринг: дужи низ
Горњи програм је саморазумљив јер прво користимо мин и мак функције на бројевима, а затим на жицама. Како нисмо обезбедили опционалну функцију упоређивања, функције мин / мак су деловале на операторе „“.
Закључак
Овим смо дошли до краја овог водича о главним алгоритмима који се користе у СТЛ-у.
У нашим следећим водичима детаљно ћемо расправљати о итераторима заједно са уобичајеним функцијама које се користе у СТЛ-у, без обзира на контејнере.
=> Прочитајте серију Еаси Ц ++ Траининг Сериес.
како отворити .дат датотеку на мац-у
Препоручено читање