Ποια είναι η πολυπλοκότητα της λειτουργίας push_back στο std::vector;

Κατά μέσο όρο, η αποσβεστική είναι O(1).

Στην χειρότερη περίπτωση, O(N), όπου N είναι το τρέχον μέγεθος του διανύσματος. Αυτό συμβαίνει κατά την επαναπροσαρμογή μνήμης, όταν η τρέχουσα χωρητικότητα του διανύσματος δεν επαρκεί για ένα νέο στοιχείο. Σε αυτήν την περίπτωση, δημιουργείται ένας νέος buffer μεγαλύτερης χωρητικότητας, αντιγράφονται εκεί τα στοιχεία και ο παλιός buffer απελευθερώνεται.