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

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== std::deque ======


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]].

{{ :cpp:stl:deque01.png?250 |}}

===== Επίδοσης της δομής =====

  * Η πράξη της ένθεσης ή της διαγραφής από την αρχή ή από το τέλος του πίνακα έχει σταθερό κόστος **(O(1))**. 
  * Η πράξη της ένθεσης ή της διαγραφής από το μέσο του πίνακα συνεπάγεται την μετακίνηση όλων των στοιχείων που βρίσκονται αριστερότερα ή δεξιότερα κατά μία θέση και η επίδοσης τη εξαρτάται από την θέση της ένθεσης ή της διαγραφής σε σχέση με την αρχή ή το τέλος του πίνακα. Ο επιμερισμένος χρόνος της συγκεκριμένης πράξης είναι γραμμικός στο μέγεθος των αποθηκευμένων στοιχείων του πίνακα **(Ο(Ν))**.
  * Η πράξη της αναζήτησης είναι γραμμική στο μέγεθος των στοιχείων του πίνακα **(Ο(Ν))**.
  * Η πρόσβαση στο i-στο στοιχείο της δομής έχει σταθερό κόστος **Ο(1)**.