Explain the differences between std::map and std::vector data structures in C++ in terms of their usage and internal implementation.

std::vector is a dynamic array that stores elements in a contiguous block of memory. It provides fast index-based access (O(1)) and efficient appending of elements at the end. However, inserting or deleting elements in the middle or at the beginning of the vector can be costly operations (O(n)), as it requires shifting elements.

std::map is an associative container, typically implemented as a balanced tree (e.g., red-black tree). It stores key-value pairs sorted by key. Access to elements is logarithmic in time (O(log n)). Insertion and deletion also have a complexity of O(log n). Unlike vector, map does not store elements in contiguous memory.

Summary:

• Use std::vector when fast indexed access and element order are important, and the number of elements changes infrequently or appending at the end.
• Use std::map when you need to store key-value pairs with fast key-based lookup and sorted order by key.