insert function

[thair]

hi guys could someone explain me how this function work

void insert(float a[], int& n, float x)
{ int j=n;
while (j>0 && a[j-1]>x)
a[j--] = a[j-1];
a[j] = x;
++n;
}

[Gaminic]

The input is a number (float x) and a (I assume) sorted list of numbers (float a[]) of size 'n'. It then proceeds to insert x on the first spot j where a[j-1] > x. To do this, it starts at the back (j = n) it copies all elements <= x to the next slot.

Be careful though; it doesn't check for bounds.

[thair]

thank you Gaminic ,the a is sorted arry but still not so clear for me how a[j--]=a[j-1] is work plus is it at each ittraration incremant the n !!??

[ciphermagi]

a[j--] = a[j-1] moves the element before a[j] into a[j], and then after the command is evaluated, it changes j to one element before where it is (decrements).

It can be represented as:

a[j] = a[j-1];
j--;

[JLBorges]

> not so clear for me how a[j--]=a[j-1] is work

a[j--] = a[j-1]; may work or may not work, or may sometimes work and sometimes not work. The behaviour is undefined.

With its current implementation, the function insert() does not work. If it appears to have worked correctly during a particular run of the program, that was happenstance,

[Stewbond]

a[j--] = a[j-1];

Let's say that j starts out at 10. Remember that j-- will return j and then decrement by 1. so....

a[10] = a[9-1];
or
a[10] = a[8];

Then next iteration we have:
a[9] = a[7];

Then:
a[8] = a[6];
and so on...

Once j is 0 then or x>a[j-1] then we insert the value: (lets say x>a[7])
a[7] = x;

Once we've inserted the value, then we increment n, which I assume represents the size of the array.

[ciphermagi]

I think you're jumping the gun, Stewbond. Wouldn't that be the same as a[10] = a[10-1]? I thought post (in/de)crementing happened after the evaluation of the entire line.

[Disch]

JLBorges is right. a[j--] = a[j-1]; is extremely ill formed and is asking for trouble.

The compiler might evaluate it as either of these:

oldj = j;
--j;
a[oldj] = a[j - 1];

or

oldj = j;
--j;
a[oldj] = a[oldj - 1];

So if j=10 you might get a[10] = a[9] or you might get a[10] = a[8]

[ciphermagi]

I thought it would be a[10] = a[9] because the j-- would not get evaluated until after the assignment, since assignments always evaluate rhs before they start on lhs.

[Stewbond]

Hmmm, I thought that the suffix increment took priority over the assignement operator.

(See order of precedence on this page):
http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B

[ciphermagi]

I guess you're right, Stew. Either way, I believe that it demonstrates the importance of what JLBorges and Disch were saying...it's better to just write clear code that's easily understandable, and let the compiler optimize it.

[Disch]

since assignments always evaluate rhs before they start on lhs.

This isn't true.

The compiler is free to evaluate any part of the expression in any order as long as it obeys operator precedence rules. In this case, all that means is that:

1) [j-1] is evaluated before the '='
2) [j--] is evaluated before the '='

There is nothing in operator precedence rules that says [j-1] must be evaluated before/after [j--] as they are kind of entirely different expressions.


Here's another example:

x = foo() + bar();

Which function is called first? foo or bar?

Again it's undefined. The only thing that's guaranteed is that:
1) foo() will be called before the + operator is evaluated
2) bar() will be called before the + operator
3) the + operator will be evaluated before the = operator

Anything else is up for grabs.

[Disch]

Hmmm, I thought that the suffix increment took priority over the assignement operator.

It does. But all that means is that the suffix operator will be evaluated before the assignment operator.

It says nothing about when the suffix operator will be evaluated in relation to the expression on the other side of the assignment operator.