Parallel Assignment

[NewProgrammer]

Hi guys,
I just came across this code fragment. The part in bold is the part of interest

void DLinkedList::add(DNode* v, const Elem& e) {	// insert new node before v
	DNode* u = new DNode; u -> value = e;		// create a new node for e
	u -> next = v;					// link u in between v
	u -> prev = v -> prev;				// ...and v -> prev
	v -> prev -> next = v -> prev = u;
}

DLinkedList is a Doubly Linked List. prev is a pointer to the previous node in the list, and next is a pointer to the next node in the list.

I want to confirm that the bold/italic statement is a parallel assignment - that is, u is simultaneously assigned to v's prev and v's (old) prev -> next.

[NewProgrammer]

Or is it explained this way:

The rvalue (u) is assigned to the left-most value first (v -> prev -> next), then the next lvalue (v -> prev)

[Disch]

No. There isn't such a thing as parallel assignment in a single thread.

Don't try to compress code like that.

This:

a = b = c;

is the same as this:

b = c;
a = b;

There's no benefit to smooshing it all on one line. Especially not if you're changing one of the values mid-statement. That code is broken as a result.

New lines and semicolons don't cost anything. Use them!

[NewProgrammer]

If your explanation is correct, then the last statement looks inaccurate.

The first three lines in the function body are clear:
- Allocate a node in memory, set its value to e
- Have its 'next' pointer point to v
- Have its 'prev' pointer point to v's 'prev' pointer

Then we get to the last statement. Going off your explanation:

- First 'u' is assigned to v's 'prev' pointer. Makes sense since the goal is to insert u in front of v.

- Then v's 'prev' pointer (which now equals u, according to your explanation) is assigned to v -> prev -> next, which means 'u' now points to itself.

Perhaps the textbook made a mistake

[Disch]

If your explanation is correct, then the last statement looks inaccurate.

It is.

Perhaps the textbook made a mistake

It must have.

The exact behavior here is undefined. maybe it will work and maybe it won't.

The rule here is you can't use something in the same line that you modify it.

Consider this classic example:

int i = 0;
int j = ++i + i++;

What is j? C++ says it's undefined. Maybe you'll get 2, maybe 1, maybe 3, maybe something else entirely. The compiler is free to evaluate that any number of ways.

You have a similar problem here:

v -> prev -> next = v -> prev = u;

Maybe the compiler will extract prev->next before assigning prev. Or maybe it won't. There's no way to know. C++ doesn't say the compiler has to do it any particular way.

[NewProgrammer]

Thanks. For now, I'll chalk that statement up as undefined.

[writetonsharma]

@kbw, I think v -> prev -> next = v -> prev = u; statement is fine. There would not be any problems in that.

The previous one you gave has confusion. int j = ++i + i++;

when there is increment and assignment at once, than we cannot be sure what will be the outcome of the final result.

[Disch]

It was me, not kbw, but anyways...

I think v -> prev -> next = v -> prev = u; statement is fine

I'm sure you're incorrect. The compiler could compile it to either of the following:

Node* p = v->prev;
v->prev = u;
p->next = u;

or

v->prev = u;
v->prev->next = u;

But as you can see, those do 2 very different things.

Or, the compiler might decide to do something completely different.

when there is increment and assignment at once, than we cannot be sure what will be the outcome of the final result.

You have the same problem here. v->prev is being both read and written at once. You can't know which one the compiler will do first because you didn't give it a sequence point (semicolon).

[z05DSL3A]

+1 Disch

v->prev->next = v->prev = u; is bad because of the unknown order of evaluation. For the sake of a few more keystrokes you have something that works in a predicable manner.


Edit:
u->prev->next = v->prev = u; would probably be okay.

[writetonsharma]

@Disch, the assignment would always be from right to left, so there is no confusion.

[z05DSL3A]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include<iostream> struct Node { Node(char id = 'z'): prev(0), next(0), id(id){} Node * prev; Node * next; char id; }; int main() { Node *a, *b, *c; a = new Node('a'); b = new Node('b'); a->next = b; b->prev = a; // c = new Node('c'); c->next = b; c->prev = b->prev; b->prev->next = b->prev = c; std::cout << "a.next: " << a->next->id << std::endl; std::cout << "b.prev: " << b->prev->id << std::endl; std::cout << "c.prev: " << c->prev->id << std::endl; std::cout << "c.next: " << c->next->id << std::endl; delete a; delete b; delete c; return 0; }

a.next: b b.prev: c c.prev: a c.next: c

[NewProgrammer]

Thanks Grey Wolf. I compiled that on Visual Studio 2010 and got the same result, serving as evidence to Disch's claim.

[webJose]

@Grey Wolf: Wouldn't that be the same result in all compilers? I'll test in VS2008 and ideone.com (gcc 4.3.4). I always thought that assignment was evaluated from right to left as writeonsharma stated.

The result is wrong yes, but because the line was poorly constructed. If you write b->prev = b->prev->next = c; then you get the correct result because you first make b->prev (which is a) point to c, the element being inserted, and then you make b point backwards to c, which is also correct.

I'll compile after breakfast. :D

[writetonsharma]

Ain't Grey Wolf's coding going from right to left as the output show's? I think it's what is expected.

[z05DSL3A]

Yes, assignment is right associative that is not in question here.

In v->prev->next = v->prev = u; is v->prev->next evaluated before or after u is assigned to v->prev? This is the bit that is undefined behavior.

Logically; yes, changing the order may make the code work correctly but I wouldn't bet the farm on it for all compilers. Reading and writing of the same variable in a single execution line should never be trusted. The code was written that way because it matches the original question, thus showing that code is wrong.

[m4ster r0shi]

I get this:

a.next: c
b.prev: c
c.prev: a
c.next: b

EDIT: I got the above compiling without optimizations.
Compiling with any speed optimization yields Grey Wolf's output.

[NewProgrammer]

@m4ster r0shi - Weird. You got a different one for a.next and c.next. Did you copy/paste the program?

[m4ster r0shi]

NewProgrammer wrote:

Did you copy/paste the program?

Yes.

[writetonsharma]

aaah.... I just tried this on paper and got the thing. I didn't realized Disch and your point as I didn't see what exactly the list is looking like. Although I was saying what you were saying and thought you are saying something else.

+1Disch, +1Grey Wolf, -5writetonsharma...

[kbw]

It's a construct used a lot in C but I don't see it used much in C++.

BTW, the assignment operator returns a reference to the object to support this chained assignment (and for no other reason).