Ερωτήσεις σχετικά με το queue<int>

Question

α) Έστω ότι έχω μια ουρά απο την STL δηλωμένη ως queue<int> q; και θέλω να υλοποιήσω μια στοίβα με μια ουρά. Για να προσθέσω ένα στοιχείο πρέπει να γράψω κάτι της μορφής q.push(x). Ωστόσο, στη στοίβα η προσθήκη γίνεται μόνο απο πάνω απ' όπου γίνεται και η εξαγωγή ενώ στην ουρά έχουμε αφαίρεση απο πάνω και προσθήκη απο κάτω. Για να μπορέσω να υλοποιήσω κάτι τέτοιο θα μπορούσα να γράψω το παρακάτω;

for (int i = q.size() - 1; i > 0; i--) {
  q.push(q.front());
}

β) Έστω ότι έχω γράψει εγώ μια συνδεδεμένη λίστα και δεν έχω χρησιμοποιήσει απο την STL πχ. το list. Μπορώ και σε αυτή την περίπτωση να χρησιμοποιήσω απο την STL π.χ. το sort για να σορτάρω τη λίστα ή αυτό γίνεται μόνο στις λίστες της STL;

Answer 1

α) Υποθέτω ότι θες σε κάθε εισαγωγή να αντιστρέφεις την ουρά ώστε να προσομοιώσεις λειτουργία στοίβας. Αν όντως αυτό θες να κάνεις τότε πρέπει να κάνεις και ένα q.pop() μέσα στο loop, γιατί αυτή τη στιγμή κάνεις push συνέχεια το ίδιο στοιχείο (το front δε μεταβάλλει την ουρά).

Η παραπάνω προσέγγιση δεν είναι καθόλου αποδοτική, γιατί για κάθε εισαγωγή στη στοίβα θα πρέπει να κάνεις q.size()-1 εισαγωγές και διαγραφές από την ουρά.

Οπότε: ναι, μπορείς να το γράψεις έτσι (αν κάνεις και την παραπάνω διόρθωση), αλλά είναι πολύ κακή λύση. (Φαντάζομαι ξέρεις οτι υπάρχει και stack στο stl.)

β) Αν χρησιμοποιούσες STL λίστα τότε θα έπρεπε να τη σορτάρεις με τη list::sort(), την οποία δεν μπορείς να χρησιμοποιήσεις για custom λίστα νομίζω.

Οπότε είτε φτιάξε δική σου sort, είτε χρησιμοποίησε την list της stl με τη list::sort().

---

Σημείωση: Ο λόγος που υπάρχει άλλη sort για τις λίστες είναι ότι ο τρόπος που σορτάρει η std::sort δεν είναι αποδοτικός για αυτές. Παρ' όλα αυτά μπορείς υλοποιώντας έναν random access iterator να χρησιμοποιήσεις την std::sort στην δικιά σου linked list, αλλά και πολύ κόπο θα κάνεις και δε θα πάρεις καλό αποτέλεσμα.

Comments

Super! Ευχαριστώ πολύ!

Answer 2

Συμφωνώ με την απάντηση του @lykmast. Θέλω όμως να προσθέσω το παρακάτω στο (β).

---

H list<T>::sort προφανώς μπορεί να χρησιμοποιηθεί μόνο για λίστες που έχουν προκύψει από το list της STL. Μάλλον όμως η ερώτηση αναφερόταν στο γενικό αλγόριθμο std::sort.

Το παρακάτω πρόγραμμα δεν κάνει compile:

#include <algorithm>
#include <list>

using namespace std;

int main() {
  list<int> l;
  l.push_back(17);
  l.push_back(42);
  l.push_back(7);
  sort(l.begin(), l.end());
}

Στη γραμμή με την κλήση στην std::sort προκύπτει μία τεράστια σειρά από περίεργα μηνύματα σφάλματος, τα οποία, αν τα αποκρυπτογραφήσει κανείς, σημαίνουν ότι η δομή list<int> δεν υποστηρίζει ό,τι χρειάζεται για να μπορεί να εκτελεστεί η std::sort, και συγκεκριμένα:

1. Τελεστή αφαίρεσης δύο iterators, για να βρεθεί το πλήθος των στοιχείων που παρεμβάλλονται.
2. Τελεστές σύγκρισης δύο iterators, για να βρεθεί ποιο στοιχείο προηγείται στη λίστα.
3. Τελεστή πρόσθεσης ακεραίου σε iterator, για να προσπελάσουμε οποιοδήποτε στοιχείο της λίστας σε $O(1)$.

Το πρόβλημα λοιπόν δεν είναι ότι τα παραπάνω δεν υποστηρίζονται αποδοτικά, είναι ότι δεν υποστηρίζονται καθόλου. Αυτό είναι επιλογή σχεδίασης της STL, να μην υλοποιήσει τα παραπάνω ακριβώς επειδή δε θα μπορούσε να τα υλοποίησει αποδοτικά (δηλαδή σε $O(1)$).

Αν θέλεις να υλοποιήσεις τις δικές σου λίστες που να μπορούν να χρησιμοποιηθούν με την std::sort, μπορείς να το κάνεις υπό την προϋπόθεση ότι θα έχεις υλοποιήσει τα παραπάνω. Δε βλέπω γιατί θα ήθελες να το κάνεις αυτό --- ο αλγόριθμος που χρησιμοποιεί η std::sort βασίζεται στην υπόθεση ότι έχεις random access στα στοιχεία του container. Αυτό δεν ισχύει για τις λίστες και εκεί έχεις άλλους τρόπους να τις ταξινομήσεις αποδοτικά (βλ. list<T>::sort).

Comments

Ευχαριστώ κ. Παπασπύρου. Ναι, η ερώτηση ήταν για τη sort γενικά και για το αν αυτή θα μπορούσε να χρησιμοποιηθεί σε custom λίστες ή μόνο σε STL λίστες.