Αντικειμενοστραφής Προγραμματισμός

User Tools

Site Tools

Trace: • vector_overloading_binary_operators • vector_overloading_unary_operators • copy_constructors • constructors_destructors • toc • functions • file_io • osteams • exception • containers
cpp:stl:deque

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision 		Previous revision
Next revision Both sides next revision
cpp:stl:deque [2020/05/27 18:04]
gthanos 		cpp:stl:deque [2020/05/29 11:34]
gthanos [Επίδοσης της δομής]
Line 2: Line 2:
  
  
-H συγκεκριμένη κλάση περιγράφει ένα //double-ended queue//, δηλαδή μία ουρά η οποία επιδέχεται γρήγορης εισαγωγής και διαγραφής στοιχείων στην αρχή και στο τέλος της. Η διπλοουρά είναι δομή ανάλογη με τη δομή [[cpp:stl:vector|vector]].+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]] για ένθεση και διαγραφή ενός στοιχείου από την αρχή της ουράς.
  
-{{ :cpp:stl:deque01.png?400 |}}+Όσον αφορά την εσωτερική υλοποίηση της [[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 |}}
  
 ===== Επίδοσης της δομής ===== ===== Επίδοσης της δομής =====
Line 11: Line 13:
   * Η πράξη της ένθεσης ή της διαγραφής από το μέσο του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται αριστερότερα ή δεξιότερα κατά μία θέση και η επίδοσης τη εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με την αρχή ή το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**.   * Η πράξη της ένθεσης ή της διαγραφής από το μέσο του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται αριστερότερα ή δεξιότερα κατά μία θέση και η επίδοσης τη εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με την αρχή ή το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**.
   * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**.   * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**.
 +  * Η πρόσβαση στο i-στο στοιχείο της λίστας έχει κόστος 1.
  
cpp/stl/deque.txt · Last modified: 2021/06/07 12:55 (external edit)

Page Tools

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution 4.0 International
CC Attribution 4.0 International Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki