C++-ში map და unordered_map-ს შორის რა განსხვავებაა?

std::map — ასოციაციური კონტეინერი, რომელიც ინახავს წყვილებს "საკვანძო-მნიშვნელობა" და სორტირებულია საკვანძოზე. დაფუძნებულია წითელი-შავი ხის სტრუქტურაზე. წვდომის, ჩაწერის და წაშლის დრო ლოგარითმულია (O(log n)).

std::unordered_map — ასოციაციური კონტეინერი, რომელიც ინახავს წყვილებს "საკვანძო-მნიშვნელობა" ჰეშ-ტაბლეში. ელემენტები არ არის სორტირებულია. საშუალოდ წვდომის, ჩაწერის და წაშლის დრო კონსტანტულია (O(1)), მაგრამ ყველაზე უარესი შემთხვევა შეიძლება იყოს ლინეურული (O(n)) კოლიზიების არსებობისას. მოითხოვს ჰეშ-ფუნქციის არსებობას საკვანძო ტიპისთვის და თანასწორობის ოპერატორს (operator==).

მახასიათებელი	std::map	std::unordered_map
საფუძველი	წითელი-შავი ხე	ჰეშ-ტაბლე
ელემენტების სორტირება	საკვანძოზე	არა
საშუალო სირთულე ოპერაციებისთვის (წვდომა, ჩაწერა, წაშლა)	O(log n)	O(1)
ყველაზე უარესი სირთულე ოპერაციებისთვის (წვდომა, ჩაწერა, წაშლა)	O(log n)	O(n) (კოლიზიების დროს)
საკვანძოს მოთხოვნები	< ოპერატორი	ჰეშ-ფუნქცია, == ოპერატორი
მეხსიერების მოხმარება	მეტი	ნაკლები (საშუალოდ, მაგრამ შეიძლება განსხვავდებოდეს)

გამოყენების მაგალითი:

#include <map>
#include <unordered_map>
#include <string>

int main() {
    // std::map-ის გამოყენება
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // ელემენტები ინახება სორტირებულია საკვანძოზე (apple, banana, orange)

    // std::unordered_map-ის გამოყენება
    std::unordered_map<std::string, int> my_unordered_map;
    my_unordered_map["apple"] = 1;
    my_unordered_map["banana"] = 2;
    my_unordered_map["orange"] = 3;
    // ელემენტები ინახება უცნობი წესრიგით
    
    return 0;
}