56474862da7b417cd7c7fc463de04751 by 2024

Author:2024
Language: eng
Format: epub
Published: 2024-06-09T13:23:35+00:00

Dive 11

The Array and Pointer Arithmetic

Real programmers count from zero.

Anonymous programmer

The array is the first data structure every programmer meets. It is essential and basic and is the prototype for every other data structure that attempts to usurp it. The array is basic because it’s just a section of memory, almost without any additional structure.

The Storage Mapping Function

Most C programmers know about arrays, but it is worth recalling what lies behind. An array is a set of identical data types accessed by an index. In C

the only type of index allowed is an integer and the storage is contiguous –

i.e. with no gaps. This is because of the way that an array is implemented using a storage mapping function, SMF.

Suppose you have an array of five integers and each is four bytes. Assume that the ints of the array are laid out in a contiguous block of memory: If each int takes four bytes, then the first int is stored at base, the address of the start of the array. The second is stored at base+4, the third is stored at base+8 or base+2*4. You can see that in general the ith element is stored at: address = base + (i-1)*4

You can get a slight simplification by starting to count the elements from 0: address = base + i*4

Now element 0 is at base, element 1 at base+4 and so on.

And, yes, this is the reason that programmers count from zero not one.

119

Going beyond the simple int array, you can see that, in general, if the repeated element in the array takes B bytes to store then the SMF for the array is:

address = base + i*B

The same idea works for multi-dimensional arrays.

For example, a two-dimensional array with n rows and m columns can be implemented using the SMF:

address = base + i *m *B +j*B

as m*B is the size of a single row – this is often called the “stride” because it’s the amount you have to jump to move to the same element in the next row.

That’s it, that’s all there is to arrays. Things really only get more complicated when you need an array that is bigger than the available memory or when there is some special requirement to be able to reorganize the array efficiently. Large arrays are generally broken down into pages, each of which will fit into memory. In this case the SMF is factored into an expression that gives the page number and the offset within the page. Arrays that need to be reorganized are generally implemented as linked lists, another major use case for pointers.

In C, an array is a contiguous block of storage that fits into memory i.e. does not need to use secondary storage.

Index Notation

All you need to implement an array is a block of memory and a pointer to the start. You can then use a storage mapping function to access any particular element. This is easy, but most computer languages, C included, provide some syntactic sugar to make working with arrays possible, even before you meet pointers.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.