A std::multimap typically uses an RB tree with duplicate keys. Fetch is O(log N + log M) Insert is O(log N + log M) Delete is O(log N + log M) Iteration is O(1) A std::map typically uses an RB tree with unique keys. Fetch is O(log N) Insert is O(log N) Delete is O(log N) Iteration is O(1) reference : http://stackoverflow.com/questions/14932007/map-vs-multimap-in-c-performance