What is the difference between ’std::map’ and ’std::unordered_map’? When would you use each?

Both std::map and std::unordered_map are associative containers in the C++ Standard Template Library (STL) that allow you to store and retrieve key-value pairs.

The key difference between std::map and std::unordered_map is the way they organize and access the elements:

std::map stores the elements in a sorted tree structure, usually a red-black tree, which maintains the order of the elements according to the keys. This makes it efficient for range queries and operations that require ordered access to the elements.

std::unordered_map stores the elements in an unordered hash table, which uses a hash function to compute the index of each element. This allows for faster lookups and insertions, especially for large datasets, but does not maintain the order of the elements.

Here is an example of how to use std::map and std::unordered_map in C++:

    #include <iostream>
    #include <map>
    #include <unordered_map>
    
    int main() {
        // Create a std::map and insert some key-value pairs
        std::map<int, std::string> myMap = {{3, "three"}, {1, "one"}, {4, "four"}};
        myMap.insert({2, "two"});
        
        // Print the elements of the std::map in sorted order
        for (auto& element : myMap) {
            std::cout << element.first << ": " << element.second << std::endl;
        }
        
        // Create a std::unordered_map and insert some key-value pairs
        std::unordered_map<int, std::string> myUnorderedMap = {{3, "three"}, {1, "one"}, {4, "four"}};
        myUnorderedMap.insert({2, "two"});
        
        // Print the elements of the std::unordered_map (order is not guaranteed)
        for (auto& element : myUnorderedMap) {
            std::cout << element.first << ": " << element.second << std::endl;
        }
        
        return 0;
    }

In this example, we create both a std::map and a std::unordered_map and insert some key-value pairs. We then iterate through the elements of each container and print them to the console. Note that the elements of the std::map are printed in sorted order, while the order of the elements in the std::unordered_map is not guaranteed.

In general, you would choose std::map if you need ordered access to the elements or if you need to perform range queries (such as finding all elements between two keys). You would choose std::unordered_map if you need faster lookups and insertions, especially for large datasets. However, keep in mind that the hash function used by std::unordered_map can affect performance and collisions can occur if the hash function is poorly designed.