რა არის C++-ში map და unordered_map კონტეინერებთან მუშაობის სირთულე?

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 უზრუნველყოფს ლოგარითმიკულ სირთულეს მონაცემებისგან დამოუკიდებლად, ინახავს ელემენტებს სორტირებულად და არ საჭიროებს ჰეშ-ფუნქციას გასაღების ტიპისთვის.