std::map operator [] -- undefined behaviour?

Question

I've just stuck myself with the following question: should this cause undefined behaviour or not and why?

std::map<int, int> m;
m[10] += 1;

It compiles and runs perfectly but it doesn't prove anything. It resembles a common UB example i = ++i + i++; since operator[] does have side effects but on the other hand assuming any order of evaluation (left to right and right to left) brings me to the same final state of the map

P.S. possibly related: http://en.cppreference.com/w/cpp/language/eval_order

edit

Sorry guys I should have written

 m[10] = m[10] + 1;

Such questions really show that language became way overcomplicated — Slava
– Slava, Commented Jun 3, 2016 at 13:00
@Slava The answer is so simple though... operator[] default constructs a mapped value at key 10 and increases it by one, just as one would expect. I don't see how complicated that is — KABoissonneault
– KABoissonneault, Commented Jun 3, 2016 at 13:33
If something like m[10] = m[10] + 1; was undefined behavior, then [ ] is seriously broken. — PaulMcKenzie
– PaulMcKenzie, Commented Jun 3, 2016 at 13:35

Smeeheey · Accepted Answer · 2016-06-03 13:26:45Z

3

There is nothing undefined about this. The operator[] returns an lvalue reference to the map entry (which it creates if necessary). You are then merely incrementing this lvalue expression, i.e. the underlying entry.

The rules for evaluation order state that for a modifying assign operation, the side effect is sequenced strictly after the evaluation of both the left (i.e. lvalue reference to the map entry) and right (i.e. the constant 1) operands. There is no ambiguity at all in this example.

UPDATE: In your updated example nothing changes. Again the side effect of modifying m[10] is sequenced strictly after the other operations (i.e. evaluating as an lvalue on the right, evaluating it on the right, and performing the addition).

The relevant sequencing rule, from cppreference:

8) The side effect (modification of the left argument) of the built-in assignment operator and of all built-in compound assignment operators is sequenced after the value computation (but not the side effects) of both left and right arguments, and is sequenced before the value computation of the assignment expression (that is, before returning the reference to the modified object)

edited Jun 3, 2016 at 13:26

answered Jun 3, 2016 at 13:00

Smeeheey

10.4k29 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

DimG Over a year ago

Probably I misleadingly used "side affects" phrase in generalized meaning, I was specifically worried about container structure side effect: the left hand-side part must be somehow evaluated (that lvalue that we want to change). This evaluation is a costly operation since we insert a new value to map. Imagine that this forces underlying search tree to be rebalanced drastically. Besides, as you kindly responded, right hand side part has to be evaluated. The rule you cited (as the others as I can see) doesn't say anything about order of value compuations.

DimG Over a year ago

Therefore, according to the cited page, these tree structure changes can overlap: "evaluations of A and B are unsequenced: they may be performed in any order and may overlap (within a single thread of execution, the compiler may interleave the CPU instructions that comprise A and B) ". Which in turn makes the behaviour being undefined

Smeeheey Over a year ago

"they may be performed in any order and may overlap" - actually that's not strictly speaking true. They may indeed be performed in any order but, because in this case they are function calls (to the overloaded operator[]), then they may NOT overlap (which is stated elsewhere on the same page). As such they are merely indeterminately sequenced rather than unsequenced, and so do not meet the criteria for undefined behaviour.

curiousguy · Accepted Answer · 2016-06-07 02:13:27Z

I am not quite sure what your worry is (and maybe you should clarify your question if that answer isn't sufficient), but m[10] += 1; doesn't get translated to m[10] = m[10] + 1; because m is user defined class type and overloaded operators don't get translated by the compiler, ever. For a and b objects with a user defined class type:

a+=b doesn't mean a = a + b (unless you make it so)
a!=b doesn't mean !(a==b) (unless you make it so)

Also, function calls are never duplicated.

So m[10] += 1; means call overloaded operator[] once; return type is a reference, so the expression is a lvalue; then apply the builtin operator += to the lvalue.

There is no order of evaluation issue. There isn't even multiple possible orders of evaluation!

Also, you need to remember that the std::map<>::operator[] doesn't behave like std::vector<>::operator[] (or std::deque's), because the map is a completely different abstraction: vector and deque are implementations of the Sequence concept (where position matters), but map is an associative container (where "key" matters, not position):

std::vector<>::operator[] takes a numerical index, and doesn't make sense if such index doesn't refer to an element of the vector.
std::map<>::operator[] takes a key (which can be any type satisfying basic constraints) and will create a (key,value) pair if none exists.

Note that for this reason, std::map<>::operator[] is inherently a modifying operation and thus non const, while std::vector<>::operator[] isn't inherently modifying but can allow modification via the returned reference, and is thus "transitively" const: v[i] will be a modifiable lvalue if v is a non-const vector and a const lvalue if v is a const vector.

So no worry, the code has perfectly well defined behavior.

Collectives™ on Stack Overflow

std::map operator [] -- undefined behaviour?

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related