I was reading up on data structures from Code Complete. This is when I stumbled through this piece about arrays:

Think of arrays as sequential structures Some of the brightest people in computer science have suggested that arrays never be accessed randomly, but only sequentially (Mills and Linger 1986). Their argument is that random accesses in arrays are similar to random gotos in a program: Such accesses tend to be undisciplined, error prone, and hard to prove correct. Instead of arrays, they suggest using sets, stacks, and queues, whose elements are accessed sequentially.

Does this hold true for System.Array class in C#?

  • 1
    Do you think it holds true? Can you think of a legitimate reason to randomly access arrays? – Bernard Feb 13 '13 at 13:11
  • 1
    @delnan no it's not, it's a list. I don't care how it was implemented in the background. I think of it as a list of things and not a location in memory with pointer offsets etc. It's how I think of the data structure and not how it actually works. – Benjamin Gruenbaum Feb 13 '13 at 13:24
  • 1
    @BenjaminGruenbaum It provides random access. If you think of it as a sequential structure, as the quote in the question demands, that's fine, but that doesn't make them a priori exempt from the question of whether to use their random access capability. NB I also don't think of a plain array in terms of physical memory or pointers; I think of it as a sequence that provides O(1) random access and (in its basic form) no resizing. – user7043 Feb 13 '13 at 13:29
  • 1
    One thing to bear in mind is that being able to prove correctness is only a concern in specific contexts: e.g. for academic purposes, or for safety-critical systems. For most applications, code clarity is much more important and you won't even attempt to prove correctness. Even gotos can have their uses in making code clearer! – vaughandroid Feb 13 '13 at 13:31
  • 1
    @delnan not at all :) I'm telling you that I rarely use arrays. There are plenty of other data structures with O(1) random access that abstract that from me (like Dictionaries). In C# I don't see what basic arrays give me most of the time. It's very rare that I think of my data as an 'array'. Also, like I said, I think arrays are great for some use cases because they are fast, also they're handy for implementing other data structures. – Benjamin Gruenbaum Feb 13 '13 at 14:23

It certainly does. Arrays in C# are very similar to arrays in other programming languages.

Some differences between dynamically allocated arrays in C and arrays in C#:

  • In C#, array always knows its length.
  • You can't use pointer arithmetic in C# (unless you use unsafe). This means that part of the array can't be represented as (pointer, length), it has be represented as something like (reference, start_index, length).

But none of these differences are relevant to the quote in question.

Also, C# makes it easy to treat array as a sequential structure: it implements IEnumerable<T> and can be used in a foreach (though neither of these allows you to modify the array). This means you can iterate though the array without using indexes. For example:

foreach (var item in array)

Or (using LINQ, which is based on IEnumerable<T>):

var unavailableProducts = products.Where(p => p.InStock == 0);
  • Thanks,svick, your answer is closest to what I was looking for. Especially for pointing out how the array in C# is different from C. Can you please elaborate on how implementing IEnumerable<T> makes it easier to treat the array as sequential? I did not understand the treating as sequential part... – TheSilverBullet Feb 14 '13 at 6:16
  • @TheSilverBullet Examples added. – svick Feb 14 '13 at 10:48
  • But, under the hood, the access continues to be random right? I would presume that the compiler breaks for loop and foreach loop to the same set of instructions. Am I correct? The difference is that here, the user cannot specify wrong or out-of-bounds index. – TheSilverBullet Feb 14 '13 at 11:26
  • @TheSilverBullet Yeah, the important part here is your code, not the implementation. – svick Feb 14 '13 at 11:39
  • 1
    @TheSilverBullet I'm quite sure he was talking about your code. It's similar with gotos: it doesn't matter that the compiled assembly code (or the intermediary IL code) uses them. What matters is that the code you write doesn't contain them. – svick Feb 14 '13 at 12:21

The point is language-unspecific, so as far as it holds, it holds for C#. (The only exception would be if your language has arrays where random access is not O(1), but I can't think of one off-hand.)

But of course there are situations in programing where you definitely don't need to access all items in a collection, but only one particular item per request, and in such situations it can be useful to arrange the items in an array for fast access. I don't think anyone would argue that random access per se is undisciplined and should be avoided in any situation - but in those where looping does the trick, it is indeed easier to program and to verify.

  • 1
    If it doesn't have random access, it's not an array. Unless you're making up terms and ignoring standard CS definitions that are older than most people working in the field. – user7043 Feb 13 '13 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.