What is the difference between map and unordered_map in C++?

std::map is an associative container that stores pairs of "key-value" sorted by key. It is based on a red-black tree. The time complexity for access, insertion, and deletion of elements is logarithmic (O(log n)).

std::unordered_map is an associative container that stores pairs of "key-value" in a hash table. Elements are not sorted. On average, the time for access, insertion, and deletion is constant (O(1)), but in the worst case, it can be linear (O(n)) due to collisions. It requires a hash function for the key type and an equality operator (operator==).

Characteristic	std::map	std::unordered_map
Basis	Red-black tree	Hash table
Element sorting	By key	No
Average operation complexity (access, insertion, deletion)	O(log n)	O(1)
Worst-case operation complexity (access, insertion, deletion)	O(log n)	O(n) (with collisions)
Key requirements	< operator	Hash function, == operator
Memory consumption	Larger	Smaller (on average, but can vary)

Example usage:

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

int main() {
    // Using std::map
    std::map<std::string, int> my_map;
    my_map["apple"] = 1;
    my_map["banana"] = 2;
    my_map["orange"] = 3;
    // Elements are stored in sorted order by key (apple, banana, orange)

    // Using 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;
    // Elements are stored without a specific order
    
    return 0;
}