What is the complexity of working with map and unordered_map containers in C++?

std::map (Red-Black Tree)

• Insertion, deletion, search: O(log N) on average and in the worst case. N is the number of elements.
• Access by key using operator[] or at(): O(log N).
• Getting iterator to beginning/end: O(1).
• Iterating over all elements: O(N).
• Memory: O(N).

std::unordered_map (Hash Table)

• Insertion, deletion, search: O(1) on average. O(N) in the worst case (with high hash collisions). N is the number of elements.
• Access by key using operator[] or at(): O(1) on average. O(N) in the worst case.
• Getting iterator to beginning/end: O(1).
• Iterating over all elements: O(N) on average. The iteration order is not guaranteed.
• Memory: O(N). Depends on load factor and hash table implementation.

Comparison:

Operation	std::map (O)	std::unordered_map (O)
Insertion, Deletion	log N	1 (average), N (worst)
Search	log N	1 (average), N (worst)
Access by key	log N	1 (average), N (worst)
Iterating all	N	N (average)

std::unordered_map is usually faster for single operations (insertion, search, deletion) due to O(1) average complexity, but requires a good hash function and is sensitive to collisions. std::map guarantees logarithmic complexity regardless of data, maintains elements in sorted order, and does not require a hash function for the key type.