C++-da map və unordered_map konteynerləri ilə işləməyin mürəkkəbliyi nədir?

std::map (Qırmızı-qaranlıq ağac)

• Əlavə etmə, silmə, axtarış: O(log N) orta və ən pis halda. N — elementlərin sayı.
• Açar ilə giriş operator[] və ya at() metodu ilə: O(log N).
• Başlanğıc/son üçün iterator əldə etmək: O(1).
• Bütün elementlər üzərində iterasiya: O(N).
• Yaddaş: O(N).

std::unordered_map (Hash cədvəli)

• Əlavə etmə, silmə, axtarış: O(1) orta halda. Ən pis halda O(N) (hash-də güclü toqquşmalar zamanı). N — elementlərin sayı.
• Açar ilə giriş operator[] və ya at() metodu ilə: O(1) orta halda. Ən pis halda O(N).
• Başlanğıc/son üçün iterator əldə etmək: O(1).
• Bütün elementlər üzərində iterasiya: O(N) orta halda. İterasiya sırası təmin edilmir.
• Yaddaş: O(N). Yükləmə faktoru və hash cədvəlinin tətbiqinə bağlıdır.

Müqayisə:

Əməliyyat	std::map (O)	std::unordered_map (O)
Əlavə etmə, silmə	log N	1 (orta), N (ən pis)
Axtarış	log N	1 (orta), N (ən pis)
Açar ilə giriş	log N	1 (orta), N (ən pis)
Bütün elementlər üzərində iterasiya	N	N (orta)

std::unordered_map ümumiyyətlə tək-tək əməliyyatlar üçün (əlavə etmə, axtarış, silmə) daha sürətlidir, çünki orta hesabla O(1). Ancaq yaxşı hash funksiyası və toqquşmalara qarşı həssasdır. std::map isə verilənlərdən asılı olmayaraq logaritmik mürəkkəbliyi təmin edir, elementləri sıralı saxlayır və hash funksiyasına ehtiyac yoxdur.