It’s been a while since i’ve posted here but I thought i’d give it a try again. This semester I am getting to take one of the more interesting courses for my CS curriculum: Data Structures. The first few weeks were C++ basics (pointers, etc.) and simple data structures such as arrays and vectors. For the most part, I’ve been fine with C++ and been okay adjusting to it, though there have been a few issues that I’ve managed to correct along the way. One of the most irritating facts is my lab 3. Now this wasn’t a hard lab by any means but a few things have happened:
- I’ve learned that my teacher gave us the code for the methods: pop and top. These weren’t hard methods by any means but I finished the lab before day of the lab so it kind of made my work seem pointless.
- I received a 17/20 on the lab and received feedback on the issues (more on this in just a second
Sigh, a 17/20 is an 85 but I feel like that isn’t good enough. After viewing the comments left on the programming, it left me absolutely livid. Why? because the comment was wrong and the things that were said in the comment was absolutely incorrect and no way of happening. I now have to go and deal with this crap with my professor.. sigh.
Against my better judgement, I am going to post the comment left and I am going to explain why this is incorrect by showing portions of my code: “You’re unnecessarily expanding the size of the stack every time you pop an element. The idea behind resizing the stack is that, because it’s slow, we only do it when we have to – and expand it to double the size so that it’ll be a while before we have to do so again. In addition to being slow, increasing the size of the stack each time you *remove* and element means the stack will eventually be using up a lot of memory it doesn’t need. I.E. If it starts off as 5, and you pop 3 elements, your stack will now be 26 elements long.”
Okay, a few points to be made here:
- He has a point — resizing a vector takes up precious CPU cycles
- My pop() method does NOT expand the size of the vector (as you will see in just a moment) but instead reduces the size to help keep down the memory usage. (This is a perfect example of the Time-Space tradeoff)
- Using my method, starting with 5 elements and popping 3 off leaves you with a stack size 2 and a total capacity of 4 — not the crazy 26 elements long as he so claims (we’re going to see the code for it in just a second)
Let’s break this down:
- if the size of the stack is 0 — do nothing (this is per the instructions but in a real-world scenario, you’d want to throw an exception and handle it gracefully)
- we create a new Integer variable that is unsigned (basically — this is to potentially prevent any negative numbers) which is equal to size() – 1. We do size() – 1 because we want the 2nd element in the stack (since this is a vector implementation, it’d be the 2nd to last in the vector)
- we reset the capacity to newSize * 2 (For example: if we had 5 elements and popped 3, it’d leave us with 2 * 2 which gives us 4)
- We create a generic vector with the new capacity
- We then iterate through the array and place the data from the original values vector into the temp
- We free up the memory used by values to prevent any issues
- We point _values at temp (since arrays/vectors can be treated as pointers in C++)
- At this time, we set the size of the Stack to the new size (For instance, if we pop 1 element off of a 5 element stack the new size is 4)
This one is a little bit more complicated since my pop will allow the stack to go down to 0, we need to handle that correctly:
- Check to see if the size of the stack is equal to the capacity
1) If it is:
1) if size and capacity are equal to 0, delete _values to free up the memory, and reset it to the default of 5 element capacity with a size of 0
2) If size and capacity aren’t equal to 0, grow the stack to a new size in order to accommodate the new values
- Finally, insert the values into the stack
- Increase the size of the stack
My tester file:
The output to that tester file: (As you can see, it’s nowhere near the 26 that was claimed in the comment)
To be honest, I am not really pissed about it as much as I was when I first discovered this since I know it was probably an honest mistake but still, people need to be more careful when grading assignments. In addition, blogging about it helped to let off some steam about it and lets you all have a view into the life of a C.S.
Anywho, my teacher is awesome and the TA is nice enough so I’m fairly sure I’ll get the 3 points back.
On a much better note, we started Big-O notation this week and I have a much clearer understanding of it now than I did when I was doing CSCI 1302. I now understand really how important it is and how it affects algorithms.
Here’s an example of some of the notes I took:
Oh, and since I’ve started C++ I’ve been using the pre increment versus post as I’ve been told it is faster than using post.