Ποια είναι η πολυπλοκότητα της εργασίας με τους κοντέινερς map και unordered_map σε C++;

std::map (Κόκκινο-μαύρο δέντρο)

• Εισαγωγή, διαγραφή, αναζήτηση: O(log N) κατά μέσο όρο και στη χειρότερη περίπτωση. N — ο αριθμός των στοιχείων.
• Πρόσβαση μέσω κλειδιού με operator[] ή at(): O(log N).
• Λήψη δείκτη αρχής/τέλους: O(1).
• Επανάληψη σε όλα τα στοιχεία: O(N).
• Μνήμη: O(N).

std::unordered_map (Πίνακας κατακερματισμού)

• Εισαγωγή, διαγραφή, αναζήτηση: O(1) κατά μέσο όρο. O(N) στην χειρότερη περίπτωση (όταν υπάρχουν ισχυρές συγκρούσεις κατακερματισμού). N — ο αριθμός των στοιχείων.
• Πρόσβαση μέσω κλειδιού με operator[] ή at(): O(1) κατά μέσο όρο. O(N) στη χειρότερη περίπτωση.
• Λήψη δείκτη αρχής/τέλους: O(1).
• Επανάληψη σε όλα τα στοιχεία: O(N) κατά μέσο όρο. Η σειρά επανάληψης δεν εγγυάται.
• Μνήμη: O(N). Εξαρτάται από τον συντελεστή φόρτωσης και την υλοποίηση του πίνακα κατακερματισμού.

Σύγκριση:

Ενέργεια	std::map (O)	std::unordered_map (O)
Εισαγωγή, διαγραφή	log N	1 (μέσος όρος), N (χειρότερη)
Αναζήτηση	log N	1 (μέσος όρος), N (χειρότερη)
Πρόσβαση με κλειδί	log N	1 (μέσος όρος), N (χειρότερη)
Επανάληψη σε όλα τα στοιχεία	N	N (μέσος όρος)

Το std::unordered_map γενικά είναι ταχύτερο για μεμονωμένες λειτουργίες (εισαγωγή, αναζήτηση, διαγραφή) χάρη στο O(1) κατά μέσο όρο, αλλά απαιτεί καλή συνάρτηση κατακερματισμού και είναι ευαίσθητο σε συγκρούσεις. Το std::map εγγυάται λογαριθμική πολυπλοκότητα ανεξάρτητα από τα δεδομένα, διατηρεί τα στοιχεία ταξινομημένα και δεν απαιτεί συνάρτηση κατακερματισμού για τον τύπο κλειδιού.