algorithms stl
Μια ρητή μελέτη των αλγορίθμων και των τύπων του στο STL.
πώς να εξαγάγετε αρχεία .7z σε mac
Το STL υποστηρίζει διάφορους αλγόριθμους που δρουν σε κοντέινερ μέσω επαναληπτών. Καθώς αυτοί οι αλγόριθμοι δρουν σε επαναληπτικά και όχι απευθείας σε κοντέινερ, μπορούν να χρησιμοποιηθούν σε οποιονδήποτε τύπο επαναληπτών.
Οι αλγόριθμοι STL είναι ενσωματωμένοι και έτσι εξοικονομούν πολύ χρόνο και είναι επίσης πιο αξιόπιστοι. Ενισχύουν επίσης την επαναχρησιμοποίηση κώδικα. Αυτοί οι αλγόριθμοι είναι συνήθως μόνο μία κλήση λειτουργίας και δεν χρειάζεται να γράψουμε εξαντλητικό κώδικα για την εφαρμογή τους.
=> Αναζητήστε ολόκληρη τη σειρά προπόνησης C ++ εδώ.
Τι θα μάθετε:
Τύποι αλγορίθμων STL
Το STL υποστηρίζει τους ακόλουθους τύπους αλγορίθμων
- Αναζήτηση αλγορίθμων
- Αλγόριθμοι ταξινόμησης
- Αριθμητικοί αλγόριθμοι
- Μη μετασχηματισμός / τροποποίηση αλγορίθμων
- Μετασχηματισμός / τροποποίηση αλγορίθμων
- Ελάχιστες και μέγιστες λειτουργίες
Θα συζητήσουμε λεπτομερώς καθέναν από αυτούς τους τύπους στις ακόλουθες παραγράφους.
Αναζήτηση και ταξινόμηση αλγορίθμων
Ο εξέχων αλγόριθμος αναζήτησης στο STL είναι μια δυαδική αναζήτηση. Ο αλγόριθμος δυαδικής αναζήτησης λειτουργεί σε έναν ταξινομημένο πίνακα και αναζητά το στοιχείο διαιρώντας τον πίνακα σε μισό.
Αυτό γίνεται πρώτα συγκρίνοντας το στοιχείο προς αναζήτηση με το μεσαίο στοιχείο του πίνακα και στη συνέχεια περιορίζοντας την αναζήτηση σε 1αγμισό ή 2αρΤο ήμισυ του πίνακα εξαρτάται από το αν το προς αναζήτηση στοιχείο είναι μικρότερο ή μεγαλύτερο από το μεσαίο στοιχείο.
Η δυαδική αναζήτηση είναι οι ευρύτερα χρησιμοποιούμενοι αλγόριθμοι αναζήτησης.
Η γενική σύνταξή του είναι:
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 Παραγωγή:
Ταξινόμηση Array είναι
0 1 2 3 4 5 6 7 8 9
Κλειδί = 2 βρέθηκε στον πίνακα
Το κλειδί = 10 δεν βρέθηκε στον πίνακα
Στον δεδομένο κώδικα, έχουμε παράσχει έναν πίνακα στον οποίο πρέπει να αναζητήσουμε ένα βασικό στοιχείο χρησιμοποιώντας τη δυαδική αναζήτηση. Δεδομένου ότι η δυαδική αναζήτηση απαιτεί μια ταξινομημένη συστοιχία, πρώτα ταξινομούμε τον πίνακα χρησιμοποιώντας τον αλγόριθμο «ταξινόμηση» και στη συνέχεια πραγματοποιούμε μια συνάρτηση κλήση στην «δυαδική αναζήτηση» παρέχοντας τις απαιτούμενες παραμέτρους.
Πρώτα, καλούμε τον αλγόριθμο binary_search για το κλειδί = 2 και μετά για το κλειδί = 10. Με αυτόν τον τρόπο με μία μόνο κλήση λειτουργίας μπορούμε εύκολα να κάνουμε μια δυαδική αναζήτηση σε έναν πίνακα ή να την ταξινομήσουμε.
Αριθμητικοί αλγόριθμοι
Η κεφαλίδα στο STL περιέχει διάφορες λειτουργίες που λειτουργούν σε αριθμητικές τιμές. Αυτές οι λειτουργίες κυμαίνονται από την εύρεση lcds, gcds έως και τον υπολογισμό του αθροίσματος των στοιχείων σε ένα κοντέινερ, όπως πίνακες, διανύσματα σε ένα συγκεκριμένο εύρος κ.λπ.
Θα συζητήσουμε εδώ μερικές σημαντικές λειτουργίες με παραδείγματα.
(i) συσσωρεύονται
Η γενική σύνταξη της συνάρτησης συσσώρευσης είναι:
accumulate (first, last, sum); Αυτή η συνάρτηση επιστρέφει το άθροισμα όλων των στοιχείων εντός ενός εύρους (πρώτο, τελευταίο) σε ένα μεταβλητό άθροισμα. Στην παραπάνω συμβολική σύνταξη, το πρώτο και το τελευταίο είναι οι διευθύνσεις του πρώτου και του τελευταίου στοιχείου σε ένα κοντέινερ και το άθροισμα είναι η αρχική τιμή της μεταβλητής αθροίσματος.
(ii) μερικό άθροισμα
Η γενική σύνταξη της συνάρτησης partial_sum είναι:
partial_sum(first, last, b) Εδώ
πρώτο: διεύθυνση του αρχικού στοιχείου του κοντέινερ.
Τελευταίο: διεύθυνση του τελευταίου στοιχείου του κοντέινερ.
B: πίνακας στον οποίο θα αποθηκευτεί το μερικό άθροισμα των αντίστοιχων στοιχείων πίνακα.
Έτσι, η συνάρτηση partial_sum υπολογίζει το μερικό άθροισμα του αντίστοιχου πίνακα ή των διανυσματικών στοιχείων και τα αποθηκεύει σε διαφορετικό πίνακα.
Εάν το σύμβολο αντιπροσωπεύει το στοιχείο στην περιοχή (πρώτο, τελευταίο) και το b αντιπροσωπεύει το στοιχείο στην προκύπτουσα συστοιχία, τότε το partial_sum θα είναι:
b0 = α0
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
διαφορά μεταξύ δοκιμαστικής υπόθεσης και δοκιμαστικού σεναρίου
partial_sum του πίνακα A: 21 46 110 142
Όπως φαίνεται στο παραπάνω πρόγραμμα, πρώτα υπολογίζουμε το άθροισμα των στοιχείων χρησιμοποιώντας τη συνάρτηση συσσώρευσης και μετά καλούμε τη συνάρτηση partial_sum για να υπολογίσουμε το μερικό άθροισμα των αντίστοιχων στοιχείων συστοιχίας.
Άλλοι αλγόριθμοι που υποστηρίζονται από STL και κεφαλίδα:
- ιώτα: Συμπληρώνει ένα εύρος με διαδοχικές αυξήσεις της αρχικής τιμής.
- περιορίζω: Παρόμοια με τη συσσώρευση, εκτός εκτός λειτουργίας.
- εσωτερικο προιον: Υπολογίζει το εσωτερικό προϊόν δύο σειρών στοιχείων.
- δίπλα_διαφορά: Υπολογίζει τις διαφορές μεταξύ γειτονικών στοιχείων σε μια περιοχή.
- inclusive_scan: Παρόμοια με το partial_sum, περιλαμβάνει το στοιχείο εισόδου ith στο άθροισμα ith.
- αποκλειστική σάρωση: Παρόμοια με το partial_sum, εξαιρεί το στοιχείο εισόδου ith από το άθροισμα ith.
Μη τροποποιητικοί αλγόριθμοι
Οι αλγόριθμοι που δεν τροποποιούν ή δεν μετασχηματίζουν είναι εκείνοι που δεν αλλάζουν το περιεχόμενο του κοντέινερ στο οποίο λειτουργούν. Το STL υποστηρίζει πολλούς αλγόριθμους που δεν τροποποιούν.
Παραθέτουμε μερικά από αυτά παρακάτω:
- μετρώ: Επιστρέφει τον αριθμό τιμών στο δεδομένο εύρος.
- ίσος: Συγκρίνει τα στοιχεία σε δύο περιοχές και επιστρέφει μια τιμή Boolean.
- αναντιστοιχία: Επιστρέφει ένα ζεύγος επαναληπτών όταν συγκρίνονται δύο επαναληπτικοί και παρουσιάζεται αναντιστοιχία.
- Αναζήτηση: Αναζητά μια δεδομένη ακολουθία σε ένα συγκεκριμένο εύρος.
- αναζήτηση_n: Αναζητά σε ένα δεδομένο εύρος για μια ακολουθία της τιμής μέτρησης.
Ας επεξεργαστούμε περισσότερα σχετικά με τις λειτουργίες 'μέτρησης' και 'ίσων' !!
Η μέτρηση (πρώτη, τελευταία, τιμή) επιστρέφει τον αριθμό των φορών που εμφανίζεται η «τιμή» στο εύρος (πρώτο, τελευταίο).
#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 εμφανίζεται στο εύρος.
Ας πάρουμε ένα παράδειγμα για να δείξουμε τη συνάρτηση «ίσο».
Το ίσο (first1, last1, first2) συγκρίνει τα στοιχεία στην περιοχή (first1, last1) με το πρώτο στοιχείο που υποδεικνύεται από το first2 και επιστρέφει αληθές εάν όλα τα στοιχεία είναι ίσα αλλιώς ψευδώς.
#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'; } Παραγωγή:
Τα στοιχεία σε δύο περιοχές δεν είναι ίδια.
Στον παραπάνω κώδικα, ορίζουμε δύο ακέραιους πίνακες και συγκρίνουμε τα αντίστοιχα στοιχεία τους χρησιμοποιώντας τη συνάρτηση «ίσο». Καθώς τα στοιχεία του πίνακα δεν είναι τα ίδια, οι ίσες επιστροφές είναι ψευδείς.
Τροποποίηση αλγορίθμων
Οι αλγόριθμοι τροποποίησης τροποποιούν ή μεταμορφώνουν το περιεχόμενο των κοντέινερ όταν εκτελούνται.
Οι πιο δημοφιλείς και ευρέως χρησιμοποιούμενοι αλγόριθμοι τροποποίησης περιλαμβάνουν το 'swap' και το 'reverse' που ανταλλάσσουν δύο τιμές και αντιστρέφουν τα στοιχεία στο κοντέινερ αντίστοιχα.
Ας δούμε τα παραδείγματα για αυτές τις συναρτήσεις:
#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. Στη συνέχεια, αντιστρέφουμε το περιεχόμενο κάθε διανύσματος χρησιμοποιώντας την αντίστροφη συνάρτηση.
Το πρόγραμμα εξάγει τα 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
Μέγιστη συμβολοσειρά: μικρότερη συμβολοσειρά
Ελάχιστη συμβολοσειρά: μεγαλύτερη συμβολοσειρά
Το παραπάνω πρόγραμμα είναι αυτονόητο καθώς χρησιμοποιούμε τις συναρτήσεις min και max στους αριθμούς πρώτα και μετά στις συμβολοσειρές. Δεδομένου ότι δεν παρέχουμε προαιρετική λειτουργία «σύγκρισης_συνάρτησης», οι συναρτήσεις min / max δρούσαν στους χειριστές αντίστοιχα.
συμπέρασμα
Με αυτό, φτάσαμε στο τέλος αυτού του σεμιναρίου σχετικά με τους σημαντικούς αλγόριθμους που χρησιμοποιούνται στο STL.
Στα επόμενα σεμινάρια μας, θα συζητήσουμε λεπτομερώς τους επαναληπτές μαζί με τις κοινές λειτουργίες που χρησιμοποιούνται στο STL ανεξάρτητα από τα κοντέινερ.
=> Διαβάστε το The Easy C ++ Training Series.
Συνιστώμενη ανάγνωση