[Mono-list] for vs. foreach

Scott Wisniewski scottdw2@uwm.edu
19 May 2002 09:51:42 -0500

On Sat, 2002-05-18 at 08:19, Serge wrote:
> More general question: Is it correct to optimize Enumerators away when
> generating foreach code? 

No. This is because its not always possible, and there are situations
where it is not a good thing to do even though it is possible.
An object does not have to implement IList to implement IEnumerable.
Also, even if IEnumerable and IList are implemented, there could be
signifigant differences between the run time complexity of calling item
versus calling the methods in the IEnumerator implementation defined by

Consider a balanced binary tree container (like a Dictionary). Making a
call to Item runs in O(log N), where as making a call to MoveNext runs
in O(1). Executing a for each over the entire dictionary object would
run in O(N). Executing a for loop over the entire dictionary object
would run in O(NLogN). This disparity is even worse with a linked list
structure,  where Item runs in O(N), which would give a for each runtime
of O(N) but a for loop runtime of O(N^2) (here N^2 means N Squared, not
N XOR 2).

-Scott Wisniewski