| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| cpp:stl:deque [2020/05/29 11:14] – [std::deque] gthanos | cpp:stl:deque [Unknown date] (current) – external edit (Unknown date) 127.0.0.1 |
|---|
| |
| |
| H συγκεκριμένη κλάση περιγράφει ένα //double-ended queue//, δηλαδή μία ουρά η οποία επιδέχεται γρήγορης εισαγωγής και διαγραφής στοιχείων στην αρχή και στο τέλος της. Η διπλοουρά είναι δομή ανάλογη με τη δομή [[cpp:stl:vector|vector]] ως προς τον τρόπο που την διαχειριζόμαστε προγραμματιστικά. Η βασική διαφορά από τη [[cpp:stl:vector|vector]] είναι ότι επιτρέπει την γρήγορη ένθεση και διαγραφή όχι μόνο στο τέλος, αλλά και στην αρχή της δομής. Για τον λόγο αυτό, εκτός από τις συναρτήσεις [[http://www.cplusplus.com/reference/deque/deque/push_back/|push_back]] και [[http://www.cplusplus.com/reference/deque/deque/pop_back/|pop_back]], παρέχει και τις συναρτήσεις [[http://www.cplusplus.com/reference/deque/deque/push_front/|push_front]] και [[http://www.cplusplus.com/reference/deque/deque/pop_front/|pop_fron]] για ένθεση και διαγραφή ενός στοιχείου από την αρχή της ουράς. | H συγκεκριμένη κλάση περιγράφει ένα //double-ended queue//, δηλαδή μία ουρά η οποία επιδέχεται γρήγορης εισαγωγής και διαγραφής στοιχείων στην αρχή και στο τέλος της. Η διπλοουρά είναι δομή ανάλογη με τη δομή [[cpp:stl:vector|vector]] ως προς τον τρόπο που την διαχειριζόμαστε προγραμματιστικά. Η βασική διαφορά από τη [[cpp:stl:vector|vector]] είναι ότι επιτρέπει την γρήγορη ένθεση και διαγραφή όχι μόνο στο τέλος, αλλά και στην αρχή της δομής. Για τον λόγο αυτό, εκτός από τις συναρτήσεις [[http://www.cplusplus.com/reference/deque/deque/push_back/|push_back]] και [[http://www.cplusplus.com/reference/deque/deque/pop_back/|pop_back]], παρέχει και τις συναρτήσεις [[http://www.cplusplus.com/reference/deque/deque/push_front/|push_front]] και [[http://www.cplusplus.com/reference/deque/deque/pop_front/|pop_front]] για ένθεση και διαγραφή ενός στοιχείου από την αρχή της ουράς. |
| |
| Όσον αφορά την εσωτερική υλοποίηση της [[http://www.cplusplus.com/reference/deque/deque/|deque]] αυτή είναι αρκετά διαφορετική σε σχέση με το [[cpp:stl:vector|vector]]. Κατά κανόνα, αποτελείται από ένα σύνολο πινάκων οι οποίοι δεσμεύονται διακριτά μεταξύ τους, καθώς αυξάνονται οι ανάγκες αποθήκευσης περιεχομένου στη δομή. Επιπλέον, διαθέτει ένα πίνακα δεικτών που χρησιμεύει στη διαχείριση των επιμέρους πινάκων που αποτελούν το περιεχομενο της δομής και του δείκτες //begin// και //end// που προσδιορίζουν την αρχή και το τέλος των περιεχομένων (δες το παρακάτω ενδεικτικό σχήμα). Η δομή υποστηρίζει //Random Access Iterators//, όπως και ο //container// [[cpp:stl:vector|vector]]. | Όσον αφορά την εσωτερική υλοποίηση της [[http://www.cplusplus.com/reference/deque/deque/|deque]] αυτή είναι αρκετά διαφορετική σε σχέση με το [[cpp:stl:vector|vector]]. Κατά κανόνα, αποτελείται από ένα σύνολο πινάκων οι οποίοι δεσμεύονται διακριτά μεταξύ τους, καθώς αυξάνονται οι ανάγκες αποθήκευσης περιεχομένου στη δομή. Επιπλέον, διαθέτει ένα πίνακα δεικτών που χρησιμεύει στη διαχείριση των επιμέρους πινάκων που αποτελούν το περιεχόμενο της δομής και του δείκτες //begin// και //end// που προσδιορίζουν την αρχή και το τέλος των περιεχομένων (δες το παρακάτω ενδεικτικό σχήμα). Η δομή υποστηρίζει //Random Access Iterators//, όπως και ο //container// [[cpp:stl:vector|vector]]. |
| |
| {{ :cpp:stl:deque01.png?250 |}} | {{ :cpp:stl:deque01.png?250 |}} |
| * Η πράξη της ένθεσης ή της διαγραφής από το μέσο του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται αριστερότερα ή δεξιότερα κατά μία θέση και η επίδοσης τη εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με την αρχή ή το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**. | * Η πράξη της ένθεσης ή της διαγραφής από το μέσο του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται αριστερότερα ή δεξιότερα κατά μία θέση και η επίδοσης τη εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με την αρχή ή το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**. |
| * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**. | * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**. |
| | * Η πρόσβαση στο i-στο στοιχείο της δομής έχει σταθερό κόστος **Ο(1)**. |
| |
