Скачать или смотреть CMPG121: Arrays and pointer arithmetic – Some theory

Explaining some of the theory behind pointer arithmetic and arrays. I recommend watching at 1.5x speed.

00:00 Video
00:55 Types in memory
02:48 Pointers
04:30 bytes.c: Memory representation of types
09:10 Pointer arithmetic
10:40 void pointer
12:20 pointers.c: Pointer arithmetic
17:00 Pointer arithmetic in C++
17:45 Arrays
19:52 arrays.c: Arrays, indexing, and pointer arithmetic
21:35 Looking at the output of the program
22:30 Pointer arithmetic on arrays
23:34 Useless yapping (I think it's interesting tho)
23:45 Commutativity of C's array indexing
25:05 C++ has operator overloading!
27:40 Compiler yells at me
30:05 Build your own cursed indexing
31:50 That's all folks!

Files can be found at paste.sr.ht/~ruan_p at paste fc43e4d
(Direct link not given because youtube won't allow me unless I send them my ID or something...)

Script:

== Pointers and Arrays ==

Sitting in class today, the lecturer was lecturing about pointers and arrays but taught very little theory, only giving example programs.

So in this video I just want to give some theoretical background to help you understand how pointers and arrays work.

First, to understand pointers we need to understand what values are and how they're represented in memory.

When C is compiled, all values are just a sequence of bytes in memory, just a bunch of numbers between 0 and 255, nothing more. What the type does is say how to interpret that sequence of bytes: 0x00 00 28 42 can be interpreted as the floating point number 42.0, or it can be the integer 1109917696. Because of the type attached, the compiler knows which addition function or display function to use to interpret the bytes correctly.

These bytes are stored in memory somewhere. You can think of memory as a very big list of bytes. Then the index of a byte in this list is called its "address". The "address" of a multi-byte value is simply the address of its first byte.

A pointer then, is a value (typically an eight byte unsigned number; minimum 0 maximum 2^64-1) that is interpreted as an index into the memory list (an address).

However, the compiler makes pointers quite convenient to use, rather than just giving us a number: with the pointer, it also keeps track of the type the pointer is pointing to*. This means that if we ask for the value the pointer is pointing to, the compiler knows to treat it as, say, an integer or a floating point number, rather than a byte. Another convenience is that you can do what's known as "pointer arithmetic" where you add and subtract numbers from the pointer, but the number added/subtracted is adjusted for the type: because an integer uses four bytes, adding one to an integer pointer will actually add *four to the pointer!

There is however the void pointer (`void*`), which is a pointer with no type information: it is purely an index into memory. It has various uses [...].


Arrays, then, can be thought of as a collection of values, each one after another in memory. You can index an array to access its elements, with element 0 being the first element, and the last element being length-1. The values of the array can be *any* type, provided that **all values are the same type**: You can have an array of integers, of characters, of a structure, even of pointers to functions!

So what does an array look like in memory? Obviously it is just the bytes of its first value, then that of its second, then that of its third and so on, right? Well yes, but also no. The contents of the array is indeed just the bytes of the values one after the other, but for various reasons the array value itself is actually a pointer: a pointer to the first value of the array.

In fact, with some very few exceptions, an array is just a pointer, nothing more and nothing less. Indexing into an array is just adding a number to that pointer, and then dereferencing it. That means that the following code is equivalent: `arr[5]` ←→ `*(arr + 5)`.
As a bit of trivia, this also means that `arr[5]` == `*(arr + 5)` == `*(5 + arr)` == `5[arr]`! Of course, I would not recommend using the `index[array]` format in a test ;)

#cmpg121 #computerscience #pointers #c #cpp