Questions from Week 6
Q: Will using strcat append the null terminator at the end of the concatonated string for me?
A: As it turns out, yes! You're fine assuming null termination after using strcat, assuming of course that both your concatonating and concatonated cstrings are both valid and null-terminated themselves!
Q: What is a string literal and how is it treated in C++?
A: A string literal is simply a sequence of null-terminated characters that we can write in-line in our code. It is essentially a cstring, but with one major difference: we cannot modify the memory it occupies once we use it.
So, for example:
// [!] "testing" is a string literal // So, the following is OK: char c[] = "testing"; // [!] We can even do the following, although // we never would: cout << "test"[0] << endl; // [X] "testing" is a string literal, // which occupies no writable memory, // so the following is NOT OK: "test"[0] = 'b';
You can therefore think of string literals as read-only cstrings, which also explains why we can use them with the C++ string library.
Remember Main Memory?
Pointers put us closer to the memory than we've seen in the past, so let's start with a review of how our code and variables are stored in memory.
Main Memory consists of a contiguous sequence of bytes (8 bits) that each have a memory address associated with them.
Memory Addresses are just like indexes in an array; they are a sequential numbering of the memory cells.
Pictorially, we think of main memory looking like the following, with each cell being 1 byte:
Now, the problem is that whenever I declare a variable on different computers with different types and possibly different compilers, I allocate a certain amount of memory.
Because the amount of memory allocated might be different depending on these distinctions, I want an easy way of "moving around" memory and its contents (pointers!).
Take the following simple statement for example: int x = 16;
Do I, as the programmer, know where the compiler is going to reserve space for x in memory?
No! The compiler will allocate space for x somewhere that is big enough to hold an int, and then place the value 16 inside.
So imagine that on some computer, an int takes up 4 bytes of memory (WARNING: We are NOT guaranteed this!), and our compiler sticks it at memory address 1000, then in memory we have:
We'll leave the specifics of how x is stored in memory to an architecture class, but because we know it took up 4 bytes on our system, we know that it spans addresses 1000 - 1003.
Similarly, when we declare an array of some type, we know a couple of things about how it gets represented in memory.
Take the following initialization for example: char c[] = "cat";
We are guaranteed a couple of things:
We know that each cell holding a character of the cstring "cat" will take up the same amount of space on any given system.
Each character in the cstring "cat" will be located contiguously in memory, meaning that if a
chartakes up 1 byte on our system, then above, c will take up 4 bytes of space in a row in memory (don't forget about the null terminator!).
Pictorially, if our compiler decided to stick c starting at memory location 1000:
Pointers: You'll Love Them or You'll Hate Them
And no, there's no middle ground... But first, a relevant XKCD:
Let's start off small... what is a pointer?
A variable that stores a reference (memory address) to another variable, or more generally, to some location in memory.
So, Andrew... why do we even have pointers (i.e., what's the point?)
To make you suffer! Just kidding (kinda, but really):
Interfacing with C libraries and other low-level programming requires that we deal with pointers a lot to access the memory more directly.
Pointers can be used to talk about types and classes (as we'll see later) in terms of other types and classes, which is useful for typecasting.
They can conveniently traverse a variety of collections like linked-lists and trees (both useful data structures introduced in CS32).
Alright, well why do men have nipples?
I don't have *all* the answers...
But what I *do* have are some programmatic tools to help us with pointers in C++:
Basics: Declaration and Initialization
The address-of operator (&): The address-of operator says "give me the memory address of my rvalue," or the expression to the right of the ampersand.
Specifically, in the case where the item we're requesting spans multiple bytes, the address-of operator returns the memory address of the first byte of that object.
We can look at our previous examples from the memory section:
Say we made the following variable initialization and our compiler gave us this picture:
What, then, is the value of &x?
1000, because &x says, "Give me the memory address of x, my rvalue." Here, 1000 is the memory address of the start of x, so that's what we return.
But now we should talk about pointers... I guess...
Pointers store memory addresses and are assigned a type corresponding to the type of variable that they point to.
We declare and initialize pointers using the * symbol:
<type>* <name>; // Declares a pointer of the given <type> and calls it <name>.
So, here are some legal pointer declarations:
int* pointy; bool* sharp; char* thorny;
To initialize pointers, we give them memory addresses corresponding to locations of variables.
// The variable being pointed at int pointedAt = 16; // The pointer that saves the memory location // of pointedAt, and so now effectively, points // at pointedAt int* pointer = &pointedAt;
Alright, great, so we've stored the memory addresses of some variables, how can pointers access the values that they point to?
The dereference operator (*): The dereference operator says "Give me the value of whatever's at the address my rvalue is pointing to." NOTE: This means the rvalue must be a pointer, i.e., a memory address!
What will the following code print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
int pointedAt = -100;
int* pointer = &pointedAt;
cout << *pointer << endl;
}
Assuming our system is representing ints with 4 bytes and the compiler reserved memory for pointedAt at address 1000, then:
Alright, so how about some nifty memory tricks for these operators?
To remember when to use & and when to use *, think:
Ampersand: Address
Star: Substance
But Andrew, * is technically an Aster--well fine then! Make your own damn memory trick!
So let's see some information about the pointer we've constructed:
#include <iostream>
#include <string>
using namespace std;
int main () {
int pointedAt = -100;
int* pointy = &pointedAt;
cout << "The value of what pointy points at: "
<< *pointy << endl;
cout << "The address of what pointy points at: "
<< pointy << endl;
cout << "The address of where pointy is stored: "
<< &pointy << endl;
// Will the above two be the same?
}
How about some examples?
Will the following code compile? Will it have any undefined behavior? If "No" to both questions, what will it print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
int ruhRoh;
int* pointy = &ruhRoh;
cout << *pointy << endl;
}
Will the following code compile? Will it have any undefined behavior? If "No" to both questions, what will it print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
int imAnInt = -100;
int* pointy = imAnInt;
cout << *pointy << endl;
}
WARNING: Unlike with types such as int, double, bool, and char, which, when given another type can sometimes convert to the other, pointers have their own conversion rules.
In this class, be aware that pointers should point to objects of their own type, or you'll likely get an error.
Will the following code compile? Will it have any undefined behavior? If "No" to both questions, what will it print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
int imAnInt = 2;
double imADouble = 2.2;
int* pointy = &imAnInt;
cout << *pointy << endl;
pointy = &imADouble;
cout << *pointy << endl;
}
We'll see why we have this type rigidity for pointers in a later section, and the issue is explored more in CS32.
Note: Reference and dereference operators could be considered inverses of one another, i.e., they "undo" each other.
Will the following code compile? Will it have any undefined behavior? If "No" to both questions, what will it print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
int imAnInt = -100;
int* pointy = &*&imAnInt;
cout << *pointy << endl;
}
Will the following code compile? Will it have any undefined behavior? If "No" to both questions, what will it print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
int imAnInt = 2;
int* pointy = &imAnInt;
cout << *(&(*pointy)) << endl;
}
Basics: Assigning to Pointers
Knowing when to use the reference and dereference operators is a bit tricky, and so the best thing to do is to translate your intent into English first.
Whenever we want to assign a value to the memory location that a pointer is pointing to, we use the following syntax:
*ptr = value;
Translate the following pointer statements into English analyses of what they're doing. The first is done for you:
#include <iostream>
#include <string>
using namespace std;
int main () {
// Variables to be pointed at
int i = 0;
double d = 3.3;
bool b;
// Pointers
// An integer pointer that points to the memory address
// at which int i is located
int* iPtr = &i;
// What's happening here?
double* dPtr = &*&d;
// Is this going to be a problem? If so, when?
bool* bPtr = &b;
// What's happening here?
*iPtr = 20;
// What's happening here?
*&*dPtr = 3.33;
b = (*iPtr % 2 == 0) || (*dPtr > 4);
cout << i << endl;
cout << *iPtr << endl;
cout << d << endl;
cout << *dPtr << endl;
cout << b << endl;
cout << *bPtr << endl;
}
It's also perfectly legal to assign pointers to each other (i.e., store the same memory address in two pointers), so long as the types agree:
What will the following code print out? Answer the questions in the comments below.
#include <iostream>
#include <string>
using namespace std;
int main () {
int pointedAt = 1;
int* pointy = &pointedAt;
// ditto used point!
int* ditto = pointy;
// Will these 2 be equal?
cout << *pointy << endl;
cout << *ditto << endl;
// Will these 2 be equal?
cout << pointy << endl;
cout << ditto << endl;
}
But what about uninitialized pointers?
Will the following code compile? Will it have any undefined behavior? If "No" to both questions, what will it print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
// To what is lamePointz pointing after this line?
int* lamePointz;
// To what address are we making this assignment?
*lamePointz = 5;
cout << *lamePointz << endl;
}
So be careful! Uninitialized pointers can lead to undefined behavior or illegal memory accesses when they haven't been assigned somewhere first.
What can we do to be safe about uninitialized pointers?
There is a special keyword called nullptr that represents "the pointer that points at nothing."
Andrew, that's very zen, we should stop and ponder life.
Nonsense! There are pointers to discuss!
The nullptr keyword is a pointer literal that indicates a pointer that isn't pointing anywhere. We use it for safety (to not dereference an undefined pointer) and clarity.
WARNING: attempting to dereference a nullptr will result in undefined behavior, though many compilers are optimzed to spot dereference of nullptrs and handle them appropriately.
#include <iostream>
#include <string>
using namespace std;
int main () {
// lamePointz is now safely pointing at nothing
int* lamePointz = nullptr;
// ...so later when we try to dereference and assign...
*lamePointz = 5;
// ...our code will break, but it will break reliably,
// indicating that we have an error in the code, rather
// than continuing blissfully unaware of our mistake
// as we may have possibly done in the example above
cout << *lamePointz << endl;
}
Just because dereference is undefined for nullptrs, we can still check to make sure a pointer is or is not the null pointer (test for equivalence):
#include <iostream>
#include <string>
using namespace std;
int main () {
int i = 50;
int* latePointer = nullptr;
if (latePointer == nullptr) {
latePointer = &i;
} else {
cout << "<_< >_>" << endl;
}
cout << *latePointer << endl;
}
Will the following code compile? Will it have any undefined behavior? If "No" to both questions, what will it print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
int* possiblyLame;
int x = 50;
possiblyLame = &x;
cout << *possiblyLame << endl;
}
What will the following code print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
int i[][3] = {
{1, 2, 3},
{4, 5, 6}
};
int* pointy = &i[1][1];
int* copyPointy = pointy;
// [!] This is a pointer reference! i.e., refPointy
// is just another name for pointy
int*& refPointy = pointy;
*pointy = 100;
pointy = &i[0][2];
cout << *pointy << endl;
cout << *copyPointy << endl;
cout << *refPointy << endl;
}
This example segues into our discussion of pointers and arrays quite nicely...
Pointers & Arrays
Pointers may have felt like an exercise in futility before now, but they make a little more sense when it comes to arrays.
Let's return with our simple example from before, this time, assuming the compiler has placed the array c at index 4000, but still treats characters as 1 byte a piece:
But wait a second... I drew an arrow from c to the start of the array in memory... could it be?
Could our array identifiers actually be... pointers?!
In a twist more dramatic than the conclusion of Survivor XXI, the answer is: yes, with one difference: once we've declared an array to an identifier (i.e., using the [] notation and reserving memory for it), we can't reassign it (seen later).
So what has our bracket notation for array indecies meant this whole time?
The bracket notation of pointers can be thought of as "dereference with offset," meaning that, if ptr is a pointer:
ptr[offset] is equivalent to saying *(ptr + offset), meaning "Give me the value at offset locations away from memory address ptr."
A pointer offset is a number indicating how many x bytes away the next or previous value is, depending on the type of the pointer.
For example, if an int is treated as 4 bytes, and I want to access the int directly following the int at address 1000 (as in an int array starting at address 1000), then
an int pointer offset of 1 tells me to look 4 bytes later, at memory address 1004. Similarly, an int pointer offset of -2 tells me to look 8 bytes before, at memory address 992, etc.
So let's look at our example again in terms of offsets:
A couple things to note above:
Notice how c is an array of chars, and so c is a char pointer, meaning that its offsets assume the next char is 1 byte away.
The bracket c[i] notation is equivalent to the offset *(c + i) notation.
Although we could generate a pointer to c[4] by saying &c[4], it would be unsafe to assign anything to c[4] (overflow).
Takeaway message: Every time I use an offset with a pointer, it automatically scales to how large its type is in memory.
Alright, back to our character array example...
Although c is still an identifier used as a pointer, because it was declared as an array, we cannot change its value...
WARNING: Remember that, although an identifier bound to an array upon declaration points to that arrays first element, unlike other pointers, it cannot change to where it points.
For example:char c[] = "cat"; // we can never change what c points tochar* c2 = c; // c2 can change what it points to
We can modify a pointer's memory address through increment and decrement whenever that pointer is modifiable, for example:
char* ptr = c; ptr++; // ptr now points to the address one char-length (1 byte) after c
Will the following code compile? If so, what will it print?
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main () {
char c[] = "cat";
int len = strlen(c);
for (int i = 0; i < len; i++) {
cout << c[0] << endl;
c++; // hey! that's this language!
}
}
So how could we do what the above is trying to do? Well, we can use another pointer to refer to where c starts:
Will the following code compile? If so, what will it print?
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main () {
char c[] = "cat";
char* helper = c;
int len = strlen(c);
for (int i = 0; i < len; i++) {
cout << helper[0] << endl;
helper++;
}
}
I could even condense the above using some pointer dereferences:
Will the following code compile? If so, what will it print?
#include <iostream>
#include <string>
using namespace std;
int main () {
char c[] = "cat";
for (char* helper = c; *helper != '\0'; helper++) {
cout << helper[0] << endl;
}
}
Will the following code compile? If so, what will it print?
#include <iostream>
#include <string>
using namespace std;
int main () {
char c[] = "cat";
for (char* helper = c; *helper != '\0'; helper++) {
// What happens when we just print out c?
cout << helper << endl;
}
}
Will the following code compile? If so, what will it print?
#include <iostream>
#include <string>
using namespace std;
int main () {
char c[] = "cat";
// Notice our new iterator increment...
for (char* helper = c; *helper != '\0'; helper = &helper[1]) {
cout << helper[0] << endl;
}
}
Pointer Arithmetic and Operators
We've seen a couple of pointer operations already, but some are not well defined.
Subtraction and addition to pointers is well defined, such that if I say (ptr + i), it means "refer to the address i times x bytes away from ptr," where x is the size of the type of ptr.
What will the following code output?
#include <iostream>
#include <string>
using namespace std;
int main () {
double d[] = {1.1, 2.2, 3.3, 4.4, 5.5};
double* ptr = d;
// Here, I'm referencing offsets from ptr
cout << *ptr << endl;
cout << *(ptr + 1) << endl;
cout << ptr[2] << endl;
// Note where ptr points now that I've
// reassigned it
ptr += 2;
cout << ptr[2] << endl;
}
WARNING: Be wary of using the postfix increment operator with pointers; remember that they increment the lvalue after everything else is done...
Will the following code compile? Will it have any undefined behavior? If "No" to both questions, what will it print out?
#include <iostream>
#include <string>
using namespace std;
int main () {
int pointedAt = 1;
int* pointy = &pointedAt;
*pointy++;
cout << *pointy << endl;
cout << pointedAt << endl;
}
Pointers are NOT defined on multiplication or division; why would you do that to a memory address? :(
Will the following code compile? If so, what will it print?
#include <iostream>
#include <string>
using namespace std;
int main () {
double d[] = {1.1, 2.2, 3.3, 4.4, 5.5};
double* ptr = d;
// Derp!
cout << *(ptr * 2) << endl;
}
Pointer Comparisons
Pointers can always be compared for equivalence (do they point to the same address), but we must be careful... we still don't know where variables will be placed in memory at runtime.
A consequence of not knowing where our variables live in memory can be undefined behavior:
Will the following code compile? Is there any undefined behavior possible? If "No" to both, what will it print?
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main () {
char c[] = "cat";
char t[] = "dog";
char* cPtr = c;
char* tPtr = t;
int len = strlen(c);
for (int i = 0; i < len; i++) {
if (cPtr < tPtr) {
cout << "cPtr: " << cPtr << endl;
} else {
cout << "tPtr: " << tPtr << endl;
}
}
}
Thus, there is no *guarantee* that tPtr will always be greater than cPtr, even though it might appear to work. Unpredictable behavior!
That said...
Pointers *within* the same array are always guaranteed to be comparable using <, >, etc. because array elements are located contiguously in memory.
Will the following code compile? Is there any undefined behavior possible? If "No" to both, what will it print?
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main () {
char c[] = "catdog";
char* cPtr = c;
int len = strlen(c);
for (int i = 0; i < len; i++) {
if (cPtr < &c[3]) {
cout << *cPtr << endl;
cPtr++;
}
}
}
When two pointers are operating in the same array, we can even subtract them to learn their *offsets,* not their difference in bytes.
For example:
#include <iostream>
#include <string>
using namespace std;
int main () {
int i[] = {1, 2, 3, 4};
int* p1 = i;
int* p2 = (i + 2);
// [?] What gets printed below?
cout << (p1 - p2) << endl;
cout << (p2 - p1) << endl;
}
Will the following code compile? Is there any undefined behavior possible? If "No" to both, what will it print?
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int main () {
int i[] = {5, 6, 7, 8, 9};
int* iPtr = i;
int len = 3;
for (int j = 0; j < len; j++) {
if (iPtr < &i[3]) {
// What will print here?
cout << (&i[3] - iPtr) << endl;
iPtr++;
}
}
}
WARNING: While it is perfectly legal to subtract two pointers, and well defined when they are in the same array, it is NOT legal to add two pointers.
Alright, see if you can get THIS:
What does the following code print out?
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
int main () {
char c[] = "testing";
int len = strlen(c);
for (int i = 0; i < len / 2; i++) {
char* front = &c[i];
char* back = &c[len - i - 1];
char stuff = *front;
*front = *back;
*back = stuff;
}
cout << c << endl;
}
Pointers & Functions
So let's talk about using functions with pointers... we've unlocked a whole new world of return and parameter types.
We can accept pointer parameters using a variety of notations:
void pointerFunc (int* i, int p[]) {
...
}
Above, both i and p refer to int pointer parameters.
What does the following code print out?
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int* findInt (int arr[], int len, int match) {
for (int i = 0; i < len; i++) {
if (arr[i] == match) {
return &arr[i];
}
}
// Case where there is no match!
return nullptr;
};
int main () {
int i[] = {5, 6, 7, 8, 9};
int* ptr = findInt(i, 5, 7);
if (ptr != nullptr) {
cout << *ptr << endl;
} else {
cout << "null!" << endl;
}
}
Note, I could have just as easily written the following parameter definition for the input array:
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
// See the difference?
int* findInt (int* arr, int len, int match) {
for (int i = 0; i < len; i++) {
if (arr[i] == match) {
return &arr[i];
}
}
// Case where there is no match!
return nullptr;
};
int main () {
int i[] = {5, 6, 7, 8, 9};
int* ptr = findInt(i, 5, 7);
if (ptr != nullptr) {
cout << *ptr << endl;
} else {
cout << "null!" << endl;
}
}
Perhaps the most important thing to know about pointer parameters:
Pointer parameters are passed by value, meaning a copy of the address is made and is named by the parameter. The values that pointer can dereference and change are NOT copied.
This explains why we can pass arrays using the pointer notation and still change the individual array elements without changing the pointer itself.
What will the ptr in main point to after the function call to findInt?
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
void findInt (int arr[], int len, int match, int* ptr) {
for (int i = 0; i < len; i++) {
if (arr[i] == match) {
ptr = &arr[i];
return;
}
}
ptr = nullptr;
};
int main () {
int i[] = {5, 6, 7, 8, 9};
int* ptr = i;
findInt(i, 5, 7, ptr);
if (ptr != nullptr) {
cout << *ptr << endl;
} else {
cout << "null!" << endl;
}
}
Side-Notes about Functions
If we wanted to set the ptr in main to what was changed in findInt, we'd just make sure to pass by reference via: int* &ptr
One might ask, then, what the difference is between pointers and references, and the answer is a subtle one (great discussion found here):
A pointer can be reassigned any number of times while a reference can not be after initialization.
A pointer can be set to the nullptr while references can never point to null (they are just names for other variables).
You can not generate the address of a reference like you can with pointers.
There are no "reference arithmetics" like we do with pointers (e.g., *(ptr + 1) or &ptr + 4)
WARNING: What happens to local variables in a function once we return from that function?
They are no longer safely allocated in memory! This means that I cannot guarantee that any variable local to a function will still be there after I've returned.
Take the following for example:
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
void naughtyFunc (int*& n) {
// What happens to i after naughtyFunc returns?
int i[] = {5, 6, 7};
n = i;
}
int main () {
int* n;
naughtyFunc(n);
for (int i = 0; i < 3; i++) {
cout << n[i] << endl;
}
}
The above code has unpredictable behavior because we do not know what has happened to i after naughtyFunc has returned, as i is no longer allocated space in memory (remnants may still remain as junk).
Finally, a couple of examples and exercises:
What will the following code print out? Warning, maturity levels are reaching 0...
#include <iostream>
#include <string>
#include <cctype>
using namespace std;
char* secretDecoder (char c[], int i[], int n) {
for (int j = 0; j < n; j++) {
c[j] = c[*(i+j)];
}
c[n] = '\0';
return c;
}
int main () {
char c[] = "disproportionate";
int i[] = {3, 5, 1, 0};
// :D
char* d = secretDecoder(c, i, 4);
cout << d << endl;
}
Define a function, ptrsToMinMax that takes in an arrays of ints, the size of that array, and two int pointers, and then sets each pointer equal to the address holding the minimum and maximum values within that array.
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
void ptrToMinMax (int arr[], int*& min, int*& max, int n);
int main () {
int arr[] = {1, 5, 0, 2, 4};
int* min;
int* max;
ptrToMinMax(arr, min, max, 5);
assert(*min == 0);
assert(*max == 5);
cerr << "[!] ALL TESTS PASSED!" << endl;
}
void ptrToMinMax (int arr[], int*& min, int*& max, int n) {
// Simply return if n is 0 or below
if (n <= 0) {
return;
}
// [!] We'll start off both of our min max pointers
// at the first element
min = ???
max = ???
// Iterate through all n elements of arr
for (int i = 0; i < n; i++) {
// [!] If the current element is less than the min
// we'll set the min to that element
if ( ??? ) {
min = ???
}
// [!] If the current element is greater than the
// max, we'll set the max to that element
if ( ??? ) {
max = ???
}
}
}
Midterm
Note: although I've seen the format of the past midterms, that may or may not be indicative of future formats!
Studying tips:
Know your syntax, know your syntax, know your syntax. Don't know how to specify arrays and cstrings? Hit the books!
Arrays, cstrings, and functions are the largest portions of the exam.
Try to do the practice examples by hand... you won't have an IDE to tell you that you missed a semi-colon!
Be comfortable spotting bugs! Pay careful attention to uninitialized variables and syntax errors!
You MUST sign up for a midterm time on the course website under "Announcements."
The midterm covers everything in the past weeks up until pointers (pointers will NOT be on the exam). Reviewing my lecture notes and doing the practice examples will set you on the right path.
You are allowed to bring a single 8.5" x 11" sheet of notes, double sided, printed or hand-written into the midterm exam. (double check on this -- it's been true in previous years)
I have launched a practice midterm II on my course site, though if you'd like practice on anything more that isn't listed there, let me know and I'll make something up!