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

ძირითადი განსხვავება იმაშია, როგორ ინახება და მიიღება ელემენტები:

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

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

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

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

int main() {
    // std::map: ელემენტები კილტზე სორტირებულია
    std::map<std::string, int> სორტირებული_გრაფა;
    სორტირებული_გრაფა["ბანანი"] = 3;
    სორტირებული_გრაფა["ვაშლი"] = 1;
    სორტირებული_გრაფა["ჩერი"] = 2;

    // გამოტანა: ვაშლი 1, ბანანი 3, ჩერი 2 (სორტი მნიშვნელოვანია)
    for (const auto& წყვილი : სორტირებული_გრაფა) {
        std::cout << წყვილი.first << " " << წყვილი.second << std::endl;
    }

    std::cout << "---" << std::endl;

    // std::unordered_map: ელემენტების წესრიგი არ არის გარანტირებული
    std::unordered_map<std::string, int> თავისუფალი_გრაფა;
    თავისუფალი_გრაფა["ბანანი"] = 3;
    თავისუფალი_გრაფა["ვაშლი"] = 1;
    თავისუფალი_გრაფა["ჩერი"] = 2;

    // გამოტანა შეიძლება იყოს განსხვავებული (მაგალითად, ჩერი 2, ვაშლი 1, ბანანი 3)
    for (const auto& წყვილი : თავისუფალი_გრაფა) {
        std::cout << წყვილი.first << " " << წყვილი.second << std::endl;
    }

    return 0;
}