Why is std::map::operator[] so counter-intuitive?

Question

It seems to me 'evil' (in the C++ FAQ sense of the word), for an operator which is generally used to access a data structure to suddenly be defined to insert data into a data structure.

I guess the issue is 'what would be better'? This question is answered easily for certain types of mapped value; for example, if we map keys to pointers, you might really like operator[] to return nullptr for a non-existent key, but that clearly doesn't work for other types.

It could throw an exception on non-existent key, or even default construct a temporary and return that without adding it to the map. What is the good reason for turning [] from read semantics to write semantics for this container type?

Answer 1

The basic problem is that there is no syntactic way to reliably distinguish:

dosomething(collection[foo]);

from

collection[foo] = something;

in the operator's definition. Because it may appear in either location, the class makes sure that it can handle both, providing a default to overwrite, if necessary. If you find this to be unconscionable, then you need to avoid std::map::operator[] altogether.

Another reason for this is there must be some defined behavior for when the key is not in the list. Since operator[] must return a value (either LValue or RValue), then it cannot return a null pointer, past-the-end iterator, or any other sentinel value. The only remaining option would be to raise an exception. The STL doesn't raise very many exceptions, because it is intended to be used even in cases where exceptions are not. Some other behavior must be chosen, and this is the result.

The best way around this is to use a member function of std::map that doesn't have this behavior. That would be map::find(), which returns map::end if the key is not found.

Answer 2

"What is the good reason for turning [] from read semantics to write semantics for this container type?"

Having thought about it for a bit longer I can think of two reasons. The first reason is efficiency. It helps to reflect on actual algorithms and whether the semantics make life easier or harder. One algorithms where the current semantics shine is in accumulating values associated with keys.

void f(std::vector<std::pair<std::string, double> > const& v)
{
        std::map<std::string, double> count;

        for (size_t i = 0, sz = v.size(); i < sz; ++i) {
                count[v[i].first] += v[i].second;
        }
}

The map semantics are nice in this case because you can rely on each value in count being initialised with zero which is likely to be what you want. In this case we only do one search into the map for each key and value pair.

If you compare that with Python (which throws an exception if the key is absent as you suggest), you get messier and less efficient code that looks like:

def f(vec):
        count = {}
        for (k, v) in vec:
                if count.has_key(k):
                        count[k] += v
                else:
                        count[k] = v

Or a slightly neater version using get() and default values.

def g(vec):
        count = {}
        for (k, v) in vec:
                count[k] = count.get(k, 0) + v
        return count

Note that in both these version two searches into the dictionary are performed for each key and value pair. Which can be a severe penalty depending on your requirements. So the C++ map semantics are necessary for efficient code in this case.

C++ has const which is a wonderful facility for protecting things from changing. I sometimes suspect that const is massively under-appreciated. In your case using const will protect you from changing the contents of your map using operator[].

The second good reason for this behaviour is that it is the same as the behaviour of associative arrays in a number of languages. Languages like Awk and Perl have had the same behaviour for associative arrays for decades. If you are coming from these languages, the behaviour of std::map is probably very intuitive.