algorithms stl
Изрично изследване на алгоритмите и неговите типове в STL.
какво е ударна вълна флаш файл
STL поддържа различни алгоритми, които действат върху контейнери чрез итератори. Тъй като тези алгоритми действат върху итератори, а не директно върху контейнери, те могат да се използват за всякакъв вид итератори.
STL алгоритмите са вградени и по този начин спестяват много време и са по-надеждни. Те също така подобряват повторната употреба на кода. Тези алгоритми обикновено са само едно извикване на функция и не е необходимо да пишем изчерпателен код, за да ги приложим.
=> Потърсете тук цялата серия за обучение на C ++.
Какво ще научите:
Видове алгоритми на STL
STL поддържа следните типове алгоритми
- Алгоритми за търсене
- Алгоритми за сортиране
- Числени алгоритми
- Нетрансформиращи / модифициращи алгоритми
- Трансформиране / модифициране на алгоритми
- Минимални и Максимални операции
Ще обсъдим подробно всеки от тези видове в следващите параграфи.
Търсене и сортиране на алгоритми
Изтъкнатият алгоритъм за търсене в STL е двоично търсене. Алгоритъм за двоично търсене работи върху сортиран масив и търси елемента, като разделя масива наполовина.
Това се прави чрез първо сравняване на елемента, който ще се търси, със средния елемент на масива и след това ограничаване на търсенето до 1улполовината или 2ndполовината от масива в зависимост от това дали търсеният елемент е по-малък или по-голям от средния елемент.
Двоичното търсене е най-широко използваните алгоритми за търсене.
Основният му синтаксис е:
binary_search(startaddr, endaddr, key)
Където,
startaddr: адрес на първия елемент от масива.
endaddr: адрес на последния елемент от масива.
ключ: елементът, който ще се търси.
STL ни предоставя алгоритъм „Сортиране“, който се използва за подреждане на елементите в контейнер в определен ред.
Общият синтаксис на алгоритъма за сортиране е:
sort(startAddr, endAddr);
Където,
startAddr: начален адрес на масива, който ще се сортира.
endAddr: краен адрес на масива, който ще се сортира.
Вътрешно STL използва алгоритъма Quicksort за сортиране на масива.
Нека вземем пример за демонстриране на двоичен алгоритъм за търсене и сортиране:
#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 не е намерен в масива
В дадения код сме предоставили масив, в който трябва да търсим ключов елемент с помощта на двоичното търсене. Тъй като двоичното търсене изисква сортиран масив, първо сортираме масива, използвайки алгоритъма „сортиране“ и след това правим извикване на функция към „binary_search“, като предоставяме необходимите параметри.
Първо извикваме алгоритъма binary_search за ключ = 2 и след това за ключ = 10. По този начин само с едно извикване на функция можем удобно да извършим двоично търсене на масив или да го сортираме.
Числови алгоритми
заглавката в STL съдържа различни функции, които работят с цифрови стойности. Тези функции варират от намиране на lcds, gcds до дори изчисляване на сумата на елементите в контейнер като масиви, вектори в даден диапазон и т.н.
Тук ще обсъдим няколко важни функции с примери.
(i) се натрупват
Общият синтаксис на функцията акумулиране е:
accumulate (first, last, sum);
Тази функция връща сумата от всички елементи в диапазон (първи, последен) в променлива сума. В горната синтаксисна нотация first и last е адресът на първия и последния елемент в контейнер, а sum е началната стойност на променливата sum.
(ii) частична_сума
Общият синтаксис на функцията part_sum е:
partial_sum(first, last, b)
Тук
първо: адрес на началния елемент на контейнера.
Последно: адрес на последния елемент на контейнера.
B: масив, в който ще се съхранява частичната сума на съответните елементи на масива.
По този начин функцията part_sum изчислява частичната сума на съответния масив или векторните елементи и ги съхранява в различен масив.
Ако a представлява елемента в диапазона (първи, последен), а b представлява елемента в резултантния масив, тогава part_sum ще бъде:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... и така нататък.
Нека да видим пример, за да демонстрираме и двете Тези функции в програма:
#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
частична_сума на масив A: 21 46 110 142
Както е показано в горната програма, първо изчисляваме сумата на елементите, като използваме функцията акумулиране и след това извикваме функцията парциална_сума, за да изчислим частичната сума на съответните елементи на масива.
Други алгоритми, поддържани от STL и заглавката:
- йота: Запълва диапазон с последователни стъпки от началната стойност.
- намаляване: Подобно на натрупване, освен извън строя.
- вътрешен продукт: Изчислява вътрешния продукт на два диапазона от елементи.
- adjacent_difference: Изчислява разликите между съседни елементи в диапазон.
- включващо_сканиране: Подобно на парциална_сума, включва i-ия входен елемент в i-тата сума.
- изключително_сканиране: Подобно на парциална_сума, изключва i-ия входен елемент от i-тата сума.
Немодифициращи алгоритми
Немодифициращи или нетрансформиращи се алгоритми са тези, които не променят съдържанието на контейнера, в който работят. STL поддържа много немодифициращи алгоритми.
По-долу сме изброили някои от тях:
- броя: Връща броя на стойностите в дадения диапазон.
- равно: Сравнява елементите в два диапазона и връща булева стойност.
- несъответствие: Връща двойка итератор, когато се сравняват два итератора и възникне несъответствие.
- Търсене: Търси дадена последователност в даден диапазон.
- search_n: Търси в даден диапазон последователност от стойността на броенето.
Нека да разгледаме повече за функциите „брой“ и „равни“ !!
count (first, last, value) връща броя на появата на ‘value’ в диапазона (first, last).
#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 се появява в диапазона.
Нека вземем пример, за да демонстрираме функцията „равна“.
jednak (first1, last1, first2) сравнява елементите в диапазона (first1, last1) с първия елемент, посочен от first2 и връща true, ако всички елементи са равни иначе false.
#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'; }
Изход:
Елементите в два диапазона не са равни.
В горния код дефинираме два целочислени масива и сравняваме съответните им елементи, като използваме функцията „равно“. Тъй като елементите на масива не са еднакви, равното връща false.
Модифициране на алгоритми
Модифициращите алгоритми променят или трансформират съдържанието на контейнерите, когато се изпълняват.
Най-популярните и широко използвани модифициращи алгоритми включват “суап” и “реверс”, които разменят две стойности и обръщат съответно елементите в контейнера.
Нека да видим примерите за тези функции:
#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
Както се вижда, имаме два вектора, дефинирани в програмата. Първо използвайки функцията за суап, ние сменяме съдържанието на vector1 и vector2. След това обръщаме съдържанието на всеки вектор, използвайки обратната функция.
Програмата извежда Vector 1 и Vector 2 след размяна на тяхното съдържание, а също и след обръщане на съдържанието.
Минимални и максимални операции
Тази категория се състои от min и max функции, които откриват минималните и максималните стойности съответно от дадените две стойности.
Общият синтаксис на тези функции е:
max(objecta, objectb); min(objecta, objectb);
Можем да предоставим и трети параметър за предоставяне на „сравнение_функция“ или критерии, които биха били използвани за намиране на минимална / максимална стойност. Ако това не е предоставено, тогава функцията max използва оператора ‘>’ за сравнение, докато функцията min използва ‘<’ 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
Max String: по-малък низ
Мин низ: по-дълъг низ
жизнен цикъл на развитие на системата на водопада
Горната програма се обяснява сама по себе си, тъй като първо използваме функции min и max върху числата, а след това върху низове. Тъй като не предоставихме незадължителна функция „сравнение_функция“, функциите min / max действаха съответно на операторите „.
Заключение
С това стигнахме до края на този урок за основните алгоритми, използвани в STL.
В следващите ни уроци ще обсъдим подробно итераторите, заедно с общите функции, използвани в STL, независимо от контейнерите.
=> Прочетете серията Easy C ++ Training.
Препоръчително четене