Map in C++ is of three different types the one which you are talking about is ordered map and there is two other kinds known as unordered map and multimap if you want to know about these three and how they differ I would suggest you to go through this article by http://www.scaler.com/topics/map-in-cpp/ . Now coming back to your question the maps are actually not using any sort of algorithm it is implemented with the help of self balancing binary search tree mostly using Red Black trees in which the value at the root node is always greater than or equal to the left child and always less than or equal to the value than the right child. It also ensures that the difference between heights of the left subtree and right subtree is at most one. Therefore the time complexity of various operations on the map in C++ is the same as that of Red Black trees.