The usual implementation is a self-balancing binary search tree (but any other data structure that respects the complexity constraints can be used, like a skip list). |
Searching for an element takes O(log n) time Inserting a new element takes O(log n) time Incrementing/decrementing an iterator takes O(log n) time Iterating through every element of a map takes O(n) time Removing a single map element takes O(log n) time Copying an entire map takes O(n log n) time. |