Indeed - exceptions are very expensive in many C++ implementations, and the standard explicitly encourages implementors to optimize the non-exception case at the expense of the exception case. (Or was it the Speed TR? Not sure.)

If [] threw an exception on a missing element, you couldn't do this:
Code:
m[key] = value;
and have it set the map element at key to value, no matter if it's already there or not.