| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| cpp:stl:containers [2020/05/28 17:51] – [Αναζήτηση στοιχείου] gthanos | cpp:stl:containers [2022/05/26 16:49] (current) – gthanos |
|---|
| ====== Κοινές συναρτήσεις για όλους τους containers ====== | |
| |
| ==== Εισαγωγή στοιχείου ==== | ===== STL Containers ===== |
| |
| Με εξαίρεση την κλάση [[array|std::array]] που το μέγεθος των πινάκων που δημιουργεί είναι σταθερό και δηλώνεται κατά τη δήλωση του πίνακα, οι υπόλοιποι //containers// μπορούν να μεταβάλλουν το αριθμό των στοιχείων που αποθηκεύουν. Για την εισαγωγή ενός στοιχείου σε έναν //container// υπάρχουν οι συναρτήσεις //insert// για την εισαγωγή ενός αντιγράφου του στοιχείου στον container και //emplace// για την δημιουργία ενός αντικειμένου και εισαγωγή του στον //container//. Επιπλέον, μόνο για τους //sequence containers// η //insert// λαμβάνει ως πρώτο όρισμα έναν //iterator// που δηλώνει τη θέση εισαγωγής του στοιχείου στον container. | Στο παρακάτω διάγραμμα περιέχονται το σύνολο των //containers// που παρέχει η βιβλιοθήκη //STL//. |
| |
| Παραδείγματα: | {{ :cpp:stl:stl.png?800 |}} |
| === A. Ένθεση σε λίστα === | |
| |
| <code cpp student_list_insert.cpp> | Οι //containers// της STL διακρίνονται στις εξής κατηγορίες: |
| #include <iostream> // std::cout | |
| #include <algorithm> // std::copy | |
| #include <list> // std::list | |
| #include "Student.hpp" | |
| |
| int main () { | * **Sequence containers:** Αποθηκεύουν τα δεδομένα σειριακά, οδηγώντας σε χρόνους αναζήτησης γραμμικούς στο μέγεθος του πλήθους των στοιχείων που είναι αποθηκευμένα. Παραδείγματα τέτοιων //containers// είναι |
| Student students[] = { Student("Peter_Pan", 1234), Student("Tinker_Bell", 1235) }; | * **array:** Πίνακας σταθερού μεγέθους το οποίο προσδιορίζεται κατά τη δήλωση του πίνακα. |
| | * **vector:** Πίνακας μεταβλητού μεγέθους. Παρέχει δυνατότητα εισαγωγής στοιχείων σε οποιαδήποτε θέση του πίνακα. Η εισαγωγή/διαγραφή στο/από το τέλος του πίνακα είναι πράξη σταθερού κόστους, ενώ η εισαγωγή σε ή η διαγραφή από ενδιάμεση θέση συνεπάγεται την αντιγραφή των αποθηκευμένων στοιχείων που βρίσκονται μετά από τη συγκεκριμένη εγγραφή κατά μία θέση. Το κόστος είναι ανάλογο του μήκους αυτού. |
| std::cerr << "----- Init list -----" << std::endl; | * **dequeue:** Πρόκειται για την γνωστή διπλοουρά που επιτρέπει την γρήγορη ένθεση και διαγραφή από την αρχή και το τέλος της ουράς. Για την εισαγωγή ή διαγραφή από ενδιάμεση θέση απαιτείται η αντιγραφή των στοιχείων που βρίσκονται πριν ή μετά τη συγκεκριμένη θέση κατά μία θέση. Όπως και στην κλάση //vector// το κόστος είναι ανάλογο του μήκους αυτού. |
| std::list<Student> mylist; | * **list:** Πρόκειται για διπλά συνδεδεμένη λίστα. Η λίστα δίνει την δυνατότητα διάτρεξης της δομής και προς τις δύο κατευθύνσεις, την εισαγωγή σε συγκεκριμένη θέση ή την διαγραφή στοιχείου από συγκεκριμένη θέση (δείτε σε αντιδιαστολή τη forward_list). Το κόστος αναζήτησης είναι ανάλογο των στοιχείων που είναι αποθηκευμένα στη λίστα, ενώ το κόστος εισαγωγής στοιχείου και διαγραφής στοιχείου είναι σταθερό. Η επιπλέον ευελιξία που παρέχεται σε σχέση με την forward list, έχει ως κόστος την διαχείριση ενός επιπλέον δείκτη σε κάθε κόμβο της λίστας. |
| for(int i=0; i<2; i++) { | * **forward_list:** Πρόκειται για απλά συνδεδεμένη λίστα. Η λίστα δίνει την δυνατότητα διάτρεξης της δομής μόνο προς τη μία κατεύθυνση (από την αρχή προς το τέλος). Για την εισαγωγή και διαγραφή θα πρέπει οπωσδήποτε να γνωρίζουμε τον προηγούμενο κόμβο (θέση). Το κόστος αναζήτησης είναι ανάλογο των στοιχείων που είναι αποθηκευμένα στη λίστα, ενώ το κόστος εισαγωγής στοιχείου και διαγραφής στοιχείου είναι σταθερό. |
| mylist.insert(mylist.begin(),students[i]); // copy-constructor, insert first | * **Container Adapters:** Χρησιμοποιούν εσωτερικά ένα //sequence container// για να υλοποιήσουν την λειτουργικότητα τους. Οι βασικές κλάσεις είναι οι εξής: |
| mylist.insert(mylist.end(),students[i]); // copy-constructor, insert last | * **stack:** Υλοποιεί μία δομή Last-In-First-Out (LIFO) με την βοήθεια ενός //vector// ή //deque//. |
| } | * **queue:** Υλοποιεί μία δομή First-In-First-Out (FIFO) με την βοήθεια ενός //deque//. |
| | * **priority_queue:** Υλοποιεί μία ουρά προτεραιότητας. Προκειμένου να επιτευχθεί η προτεραιότητα κατά την εισαγωγή και διαγραφή στοιχείου εφαρμόζεται ο αλγόριθμος make_heap για την επίτευξη σωρού με λογαριθμικό κόστος στο μέγεθος των αποθηκευμένων στοιχείων της δομής. |
| mylist.emplace(mylist.end(), "Mickey_Mouse", 1237); // argument construct, insert last | * **Associative Containers:** Πρόκειται για δομές που τα στοιχεία εισάγονται ταξινομημένα σε αύξουσα σειρά. Η αποθήκευση γίνεται σε ένα ισοζυγισμένο δέντρο αναζητήσεως (π.χ.[[wp>Red–black_tree]]) και ο χρόνος αναζήτησης, εισαγωγής και διαγραφής είναι λογαριθμικός στο μέγεθος των αποθηκευμένων στοιχείων. Διακρίνονται σε [[cpp:stl:set|sets]] που είναι σύνολα από __μοναδικά__ στοιχεία-κλειδιά και [[cpp:stl:map|maps]] που είναι σύνολα από απεικονίσεις __μοναδικών__ στοιχείων-κλειδιών σε τιμές. Παραλλαγές των παραπάνω κλάσεων είναι τα **multiset** και **multimap** όπου δίνεται η επιπλέον δυνατότητα αποθήκευσης περισσότερων του ενός ίδιων κλειδιών στην υφιστάμενη δομή. |
| | * **Unordered Associative Containers:** Δομές ανάλογες με τους //Associative Containers// με την διαφορά ότι η αποθήκευση δεν γίνεται σε ισοζυγισμένο δέντρο αναζητήσεως, αλλά σε πίνακα κατακερματισμού ([[wp>Hash_table]]). Για τον λόγο αυτό, τα στοιχεία δεν αποθηκεύονται ταξινομημένα, αλλά με "τυχαία" σειρά. Η σειρά διάτρεξης τους αντιστοιχεί στη σειρά που τα κλειδιά είναι αποθηκευμένα στον πίνακα κατακερματισμού. Ο μέσος χρόνος αναζήτησης, εισαγωγής και διαγραφής είναι σταθερός στο μέγεθος των αποθηκευμένων στοιχείων. Οι κλάσεις **unordered_set** και **unordered_map** επιτρέπουν την αποθήκευση μοναδικών κλειδιών, ενώ οι δομές **unordered_multiset** και **unordered_multimap** επιτρέπουν την αποθήκευση περισσότερων του ενός ιδίων στοιχείων-κλειδιών στη δομή. |
| std::cerr << "-------------------------\n"; | |
| std::cerr << "mylist contains:"; | |
| for (std::list<Student>::iterator it = mylist.begin(); it!=mylist.end(); ++it) | |
| std::cerr << ' ' << *it; | |
| std::cerr << std::endl; | |
| std::cerr << "-------------------------\n"; | |
| | |
| return 0; | |
| } | |
| </code> | |
| |
| === Β. Ένθεση σε set === | |
| |
| <code cpp string_set_insert.cpp> | |
| #include <iostream> // std::cout | |
| #include <algorithm> // std::copy | |
| #include <set> // std::set | |
| #include <string> | |
| |
| int main () { | |
| std::string strings[] = { std::string("gamma"), std::string("beta"), std::string("delta") }; | |
| | |
| std::cerr << "----- Init set -----" << std::endl; | |
| std::set<std::string> myset; | |
| for(int i=0; i<3; i++) | |
| myset.insert(strings[i]); | |
| | |
| myset.emplace("alpha"); // argument construct, insert last | |
| | |
| std::cerr << "-------------------------\n"; | |
| std::cerr << "myset contains:"; | |
| for (std::set<std::string>::iterator it = myset.begin(); it!=myset.end(); it++) | |
| std::cerr << ' ' << *it; | |
| std::cerr << std::endl; | |
| std::cerr << "-------------------------\n"; | |
| | |
| return 0; | |
| } | |
| </code> | |
| |
| ==== Διαγραφή στοιχείου ==== | |
| |
| Η διαγραφή στοιχείου είναι ανάλογη της εισαγωγής και γίνεται μέσω της συνάρτησης //erase//. H συνάρτηση επιστρέφει έναν //iterator// στο επόμενο στοιχείο από αυτό που έχει διεγραφεί. Για τους //sequence containers// σε αναλογία με την διαδικασία εισαγωγής, η συνάρτηση λαμβάνει ως όρισμα έναν //iterator// που δηλώνει τη θέση διαγραφής από τον container. Για τους //associative containers// η διαγραφή γίνεται παρέχοντας ως όρισμα τη θέση του κλειδιού (μέσω //iterator//) ή την τιμή του κλειδιού που επιθυμούμε να διαγράψουμε. | |
| |
| === Διαγραφή από λίστα === | |
| |
| Το παρακάτω παράδειγμα είναι από τη σελίδα [[http://www.cplusplus.com/reference/list/list/erase/|http://cplusplus.com/list/erase]] | |
| |
| <code cpp list_erase.cpp> | |
| #include <iostream> | |
| #include <list> | |
| |
| int main () { | |
| std::list<int> mylist; | |
| std::list<int>::iterator it1, it2; | |
| |
| // insert values: | |
| for (int i=1; i<10; ++i) mylist.push_back(i*10); | |
| |
| // 10 20 30 40 50 60 70 80 90 | |
| it1 = it2 = mylist.begin(); // ^^ | |
| advance (it2,6); // ^ ^ | |
| ++it1; // ^ ^ | |
| |
| it1 = mylist.erase (it1); // 10 30 40 50 60 70 80 90 | |
| // ^ ^ | |
| |
| it2 = mylist.erase (it2); // 10 30 40 50 60 80 90 | |
| // ^ ^ | |
| // 10 30 40 50 60 80 90 | |
| ++it1; // ^ ^ | |
| --it2; // ^ ^ | |
| |
| it1=mylist.erase (it1,it2); // 10 30 60 80 90 | |
| // ^ | |
| |
| std::cout << "mylist contains:"; | |
| for (it1=mylist.begin(); it1!=mylist.end(); ++it1) | |
| std::cout << ' ' << *it1; | |
| std::cout << '\n'; | |
| |
| return 0; | |
| </code> | |
| |
| |
| === Διαγραφή από set === | |
| |
| Το παρακάτω παράδειγμα είναι από τη σελίδα [[http://www.cplusplus.com/reference/set/erase/|http://cplusplus.com/set/erase]] | |
| |
| <code cpp set_erase.cpp> | |
| // erasing from set | |
| #include <iostream> | |
| #include <set> | |
| |
| int main () | |
| { | |
| std::set<int> myset; | |
| std::set<int>::iterator it; | |
| |
| // insert some values: | |
| for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90 | |
| |
| it = myset.begin(); // 10 20 30 40 50 60 70 80 90 | |
| // ^ | |
| ++it; // 10 20 30 40 50 60 70 80 90 | |
| // ^ | |
| |
| myset.erase (it); // 10 30 40 50 60 70 80 90 | |
| |
| myset.erase (40); // 10 30 50 60 70 80 90 | |
| |
| it = myset.find (60); // 10 30 50 60 70 80 90 | |
| // ^ | |
| myset.erase (it, myset.end()); // 10 30 50 | |
| |
| std::cout << "myset contains:"; | |
| for (it=myset.begin(); it!=myset.end(); ++it) | |
| std::cout << ' ' << *it; | |
| std::cout << '\n'; | |
| |
| return 0; | |
| } | |
| </code> | |
| |
| ==== Αναζήτηση στοιχείου ==== | |
| |
| Η αναζήτηση ενός στοιχείου είναι διαφορετικά εάν αναζητούμε σε //sequence container// ή σε άλλου τύπου //container//. | |
| |
| === Αναζήτηση σε sequence container === | |
| |
| H αναζήτηση σε sequence container γίνεται μέσω της συνάρτησης [[http://www.cplusplus.com/reference/algorithm/find/|std::find]]. Όπως θα δείτε και από τον ενδεικτικό κώδικα στο link η συνάρτηση λειτουργεί διατρέχοντας τον //container// με την βοήθεια ενός //iterator//. Το κόστος αναζήτησης είναι γραμμικό στο πλήθος των στοιχείων του //container// και για αυτό δεν αποτελεί βέλτιστη επιλογή για //associative// και //unordered associative containers//. Δείτε το παρακάτω ενδεικτικό παράδειγμα αναζήτησης σε μία λίστα. Η συνάρτηση [[http://www.cplusplus.com/reference/algorithm/find/|std::find]] επιστρέφει έναν //iterator// που δείχνει στην πρώτη θέση που εμφανίζεται το στοιχείο που αναζητούμε (μπορεί να εμφανίζεται σε περισσότερες θέσεις). Εάν δεν υπάρχει το στοιχείο που αναζητούμε η συνάρτηση //find// επιστρέφει έναν //iterator// που δείχνει στο σημείο του //container// που δείχνει και η συνάρτηση //end//. Το παρακάτω παράδειγμα είναι ενδεικτικό. | |
| |
| <code cpp find_in_vector.cpp> | |
| //find example | |
| #include <iostream> // std::cout | |
| #include <algorithm> // std::find | |
| #include <vector> // std::vector | |
| |
| int main () { | |
| // using std::find with array and pointer: | |
| int myints[] = { 10, 40, 30, 30, 40, 50, 30, 60, 30 }; | |
| int *p; | |
| int search_int; | |
| | |
| std::cout << "Enter an integer to search for: "; | |
| std::cin >> search_int; | |
| |
| p = std::find (myints, myints+9, search_int); | |
| | |
| if (p != myints+9) | |
| std::cout << "First occurance of " << search_int << " in myints: " << *p << '\n'; | |
| else | |
| std::cout << search_int << " not found in myints: " << '\n'; | |
| |
| std::vector<int> myvector (myints,myints+9); | |
| auto it = myvector.begin(); | |
| bool found = false; | |
| while(true) { | |
| it = find (it , myvector.end(), search_int); | |
| if (it != myvector.end()) { | |
| std::cout << search_int << " found in myvector at pos: " << it - myvector.begin() << '\n'; | |
| it++; | |
| found = true; | |
| } else { | |
| if(!found) | |
| std::cout << search_int <<" not found in myvector\n"; | |
| break; | |
| } | |
| } | |
| |
| return 0; | |
| } | |
| </code> | |
| |
| === Αναζήτηση σε associative container και unordered associative container === | |
| |
| Επειδή η συνάρτηση //find// ψάχνει γραμμικά μέσα στο περιεχόμενο του container δεν είναι βέλτιστή για containers που περιγράφονται από δέντρα ή από πίνακα κατακερματισμού. Αυτοί οι //containers// διαθέτουν δικές τους εξειδικευμένες //find// που ταιριάζουν στα χαρακτηριστικά της δομής που εξυπηρετούν. | |
| |
| === Αναζήτηση σε set === | |
| |
| <code cpp find_in_set.cpp> | |
| #include <iostream> | |
| #include <set> | |
| |
| int main () | |
| { | |
| std::set<int> myset; | |
| std::set<int>::iterator it; | |
| |
| // set some initial values: | |
| for (int i=1; i<=5; i++) myset.insert(i*10); // set: 10 20 30 40 50 | |
| |
| it=myset.find(20); | |
| myset.erase (it); | |
| myset.erase (myset.find(40)); | |
| |
| std::cout << "myset contains:"; | |
| for (it=myset.begin(); it!=myset.end(); ++it) | |
| std::cout << ' ' << *it; | |
| std::cout << '\n'; | |
| |
| return 0; | |
| } | |
| </code> | |
| |
| |
| === Αναζήτηση σε unordered set === | |
| |
| <code cpp find_in_unordered_set.cpp> | |
| // unordered_set::find | |
| #include <iostream> | |
| #include <string> | |
| #include <unordered_set> | |
| |
| template<typename T> | |
| void print_set(std::unordered_set<T>& myset) { | |
| std::cout << "myset contains:"; | |
| for (auto it=myset.begin(); it!=myset.end(); ++it) | |
| std::cout << ' ' << *it; | |
| std::cout << '\n'; | |
| } | |
| |
| int main () { | |
| std::unordered_set<std::string> myset; | |
| std::unordered_set<std::string>::iterator it; | |
| char* word[] = { "sugar", "choco", "milk", "banana", "coffee" }; | |
| |
| // unordered_set some initial values: | |
| for (int i=0; i<5; i++) | |
| myset.emplace(word[i]); | |
| | |
| print_set(myset); | |
| | |
| it=myset.find(std::string("biscuits")); | |
| if(it != myset.end()) { | |
| myset.erase (it); | |
| std::cout << "'buiscuits' erased\n"; | |
| } | |
| else | |
| std::cout << "'buiscuits' not found\n"; | |
| | |
| print_set(myset); | |
| myset.erase (myset.find(std::string("milk"))); | |
| std::cout << "'milk' erased\n"; | |
| print_set(myset); | |
| |
| return 0; | |
| } | |
| </code> | |
| |
| <WRAP important 80% center round> | |
| Όλες οι παραλλαγές της συνάρτησης find επιστρέφουν έναν //iterator// που δείχνει στην πρώτη (ή στη μοναδική) εμφάνιση του στοιχείου που ψάχνουμε στον //container//. Σε περίπτωση που δεν βρεθεί το στοιχείο ο //iterator// δείχνει μετά το τέλος του //container// εκεί που δείχνει και ο //iterator// που επιστρέφεται από τη συνάρτηση //end//. | |
| </WRAP> | |
| | |
