map+vector vs. multimap

A std::multimap<Key, Val> 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<Key, std::vector<Val>> 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