Q: Excuse me. What is the effect of using BlueBook for our exams? Does it read our machine’s processes during the exam or something?
A1: What do you mean by the effect on your computer? It is just a program used to adminster digital exams, its not really doing surveilance on your machine, besides making note of when you have it open (it logs switches away for on campus exams but we are ignoring that in the digital learning world)
Q: Oh ok I was just curious if it was made to see if we run other programs during non open book assignments, but I guess it just monitors your behavior on the actual application itself?
A1: Correct
Q: Assignment 5 is due next week correct?
A1: live answered
A2: Released Wednesday, due the following Wednesday
Q: will we have class or sections on wednesday?
A1: Yes there are still sections this week + our normal lecture schedule
Q: Why didn’t the memory cap out at 2gb?
A1: The myths are 64-bit systems, not 32
Q: Is there a way to make the demo once and ge the same output?
A1: Yes (but the point was to demonstrate what happens when you allocated many copies and did not delete them)
Q: So it took more memory on myth because each individual string takes up more memory?
A1: No, there is other memory use by a process behind the scenes that is OS-dependent
Q: do we have to call the destructor in the main?
A1: The destructor is automatically called when the variable goes out of scope
Q: If the destructor tells the for loop to give the memory back, why does the memory still increase at all, even by a little bit?
A1: live answered
Q: I understand why stopping is faster when delete is used properly, but why does the program itself slow down when delete is not used?
A1: live answered
A2: The program slows down because you keeping asking the OS to go find free, contiguous memory, which gets harder and harder if you’re already hogging all the memory in the system
Q: if this was java, then this memory reallocation would have happened automatically correct? Since this is C++ and does not have dynamic memory allocation, we have to do it manually right?
A1: Correct
Q: How does the program know when a class is out of scope?
A1: live answered
A2: The closing curly brace closes a scope
A3: The compiler knows when things go out of scope based ont he way you’ve written the code – anytime scoping rules are in effect (based on a conditional or functin block ending) they are enforced by the compiler
Q: what happens if you run out of memory within the loop?
A1: live answered
A2: The program will terminate/crash
Q: What would have happened if we didn't use dynamic memory? - or do we always have to use dynamic memory for private variables
A1: live answered
Q: So, when using delete, would the same memory locations be used used every instance?
A1: Perhaps
A2: No guarantees that it would be, the OS is free to give us any memory that meets our size requirements, no guarantee it will always be the same chunk
Q: If we had a class that didn't have a dynamically allocated array, would we still get a memory leak?
A1: No memory leaks are only applicable for dynamically allocated memory
Q: What is the worst case time for finding enough contigous memory, assuming it exists somewhere
A1: I suppose the worst case could require a linear search through all of memory
A2: depends on the implementation of the operating system, talked about in CS140
Q: so long as you define it in the class, the program will call the destructor automatically when the class goes out of scope?
A1: Yes
Q: Why doesn't the compiler automatically return the memory once the class goes out of scope?
A1: “with great power comes great responsibility” is generally the motto of C++. It gives you the power to allocate memory whenever you want but then gives you the responsibility to clean it up when you’re done with it. If it tried to automatically clean things up, it might get int he way of what you want to do with the memory
Q: how does the destructore get called?
A1: automatically called by the compiler when something goes out of scope
Q: Didn’t we find the contiguous memory spaces at the beginning via new?
A1: Correct
Q: if the program crashes will it still be able to give back the used memory?
A1: The operating system will likely do some memory cleanup of its own if your program crashes and is unable to give it bakc manually
Q: What if you e.g. added the Demo instances you made to a Vector
A1: It is a little subtle, but storing the object in the Vectorm makes a copy of the object, this copy is distinct from the one on the stack
Q: Why was the memory used still over 50MB?
A1: I don’t remember exactly how much memory was in use but there is other ovehead in the program using memory that we won’t really talk about
Q: If the operating system can't find that amount of contiguous memory, will it wait until it becomes available, or just crash immediately?
A1: If its truly unable to give you that much memory, it would give you something like a “bad malloc” error and then fail
Q: Does the stack have less memory space than the heap?
A1: Yes, typically quite a lot less space is designated for the stack than the heap
A2: Yes, the stack is usually of fixed size that is smaller than what is available on the heap. Thus, general programming practice is to store large data structrues on the heap
Q: what does overloading mean?
A1: live answered
Q: So if we found all of the contiguous memory spaces in the beginning, why does the program slow down (when we don’t delete)? I thought Chris said it slows down because it is searching for the memory, but we find it all in the beginning. How does this work?
A1: Ah, it searches for the memory “on demand” so each subsequent new call is doing its own search, and as the memory gets more full, it takes longer and longer to find available spots
A2: We don’t find it all in the beginning – we ask the OS to find mor ememory on every individual call to new. As you keep doing mroe and more new calls without freeing any memory, it becomes harder to fulfill the requirements of each subsequent new call
Q: Would it potentially be useful to define push to return the object or the value rather than void?
A1: live answered
A2: We could, but we’re going for a pretty simple implementation here
Q: Can peek() be declared as a const function?
A1: Yes
Q: what is ostream
A1: output stream, cout is the standard output stream
Q: Should we declare arrays with the asterisk notation or with brackets?
A1: Asterisk
A2: There’s two components here – we declare the variable that points to an array as a pointer (using the asterisk). When we actually go to declare the array, we will use the new int[N] syntax with brackets to actually create the array, and the reutrn type of that will be a pointer we store in elements
Q: what’s the purpose of declaring it as int* elements and not just int elements?
A1: It is a pointer variable
A2: It needs to store a pointer to an array in dynamically allocated memory
Q: is it ok if we don’t understand the friend / std / ostream stuff yet or should we be able to write that at this point
A1: live answered
A2: live answered
Q: Can you have a const in private variables if you don’t want users to be able to see what the const is?
A1: Yes, you could
Q: What is the initial capacity of the standard and Stanford stacks?
A1: The interface does make any guarantees, this is an internal implementation detail
Q: elements are pointer?
A1: The elements member variable is a pointer to an array of int elements
A2: Yes elements is an int pointer
Q: What are the 2 parameters of friends for?
A1: The first is the output stream to which we are outputting info regarding the object we want to print and the second param is the object whose state we want to print
Q: Are we going to have to implement classes with the friend stuff
A1: You won’t have to implement a friend function on A5
Q: what's the difference between using "const" and "#define" when dealing with things like INIT_CAPACITY, etc?
A1: #define is the old-style C way, a bit hacky. Using const is preferred
Q: for elements, could we use vector instead of int*, or should we not use adts when creating classes
A1: The goal here is to build our own ADT from scratch, so doesn’t really make sense to build on top of existing ADT
Q: Is it possible to specify the value of the constant initial capacity by including another constructor with a user-defined value?
A1: Yes, that would be possible
Q: Why don’t we say “using namespace StackInt” in the cpp file?
A1: That won’t have the effect that you intend
Q: why dont we use namespace std in the header file
A1: You don’t have to, it’s a stylistic preferrence
Q: what does the new keyword do
A1: live answered
A2: Asks the operating system for dynamically allocated memory on the heap and returns a pointer to that memory
Q: where did the variables go?
A1: live answered
Q: even though the array has eight elements, it still only has one address? which is stored in elements
A1: Correct, the address points to the front of the arr
A2: The array has space for 8 elements, and we store a pointer to the beginning of the array, yes.
Q: where are elements, count, and capacity defined?
A1: live answered
A2: We just defined those in the class declaration in the header file (.h)
Q: Would elements just be filled with 0s initially?
A1: live answered
A2: Good question! It’s actually filled with “garbage” values in the sense that we have no control over what values are actually initially stored in the array (could be zeros, could be randm large ints, etc.)
Q: so using dynamic memory means the stack can grow or shrink, which means we don’t need a class for every possible size?
A1: Correct
Q: just to double check:: the delete keyword returns the memory to the heap right?
A1: Correct
Q: Will we ever use the destructor to do anything other than deleting the class instance?
A1: For most uses in this class, the destructor will be used to free dynamic memory associated with the clas sinstance
Q: Do we have to actively call the destructor, or does the program do that automatically when the variable goes out of scope?
A1: The latter.
Q: I don’t really understand what count means
A1: count is an instance variable that we are using to keep track of the number of elements currently in the stack
Q: Could the garbage values be left over values from when you returned memory?
A1: Yes
A2: Yes, potentially. In general, garbage value sshould be treated as totally unpredictable
A3: Maybe, from a long time ago. I wouldn’t count on this though
Q: if elements is a pointer and not an actual array, how come we can index into it like an array?
A1: live answered
A2: C++ supports indexing semantics on pointers that point to the beginning of an array
Q: does expand just cause the memory to expand by one?
A1: We’ll see in a second!
Q: is expand defined somewhere else already
A1: No, it is coming up
A2: We’ll write it togteher in a bit (it is a private helper functions)
Q: Does this get rid of capacity?
A1: No, capacity is unchanged
A2: No, capacity stays fixed
Q: why dont we just do return elements[count -= 1]
A1: live answered
Q: Do you have to delete the memory used by that 3?
A1: No, we speicfically don’t want to at the moment. We can use that space to stroe more lements in the future (if more elements are added to the stack)
A2: No because we might want to access that memory later for a different variable
Q: Why don’t we delete elements[count] for pop
A1: We don’t want to delete that memory – we might want to use it again to store more elements in the future!
Q: do we want to deallocate the memory at the last index when we pop
A1: live answered
A2: live answered
Q: Why not count - - for peek?
A1: live answered
A2: Peek should not change the state of the stack (nothing is getting removed)
Q: qhen you decrement count in a function, will that change be permanent and take effect even if count is used in other function besides the one it was decremented in?
A1: Yes, changing the value of count is a persistent change
A2: Yes, we are operatign on instance varaibles, which are shared across all functions for a specific class instance. So those change sar epersistent across our whole stack
Q: Is the actual Stanford stack implemented the exact same way, only with a template?
A1: The Stanford stack is actually implemented on top of the STL containers (we kind of cheat, don’t want to reinvent the wheel!)
Q: what’s the benefit of allocating our array on the heap rather than the stack? If we’re getting rid of our StackInt once it goes out of scope then what’s the benefit of using the new keyword and allocating?
A1: One of the specific benefits of using dynamic memory in this case is it allows us to to dynamically resize the capacity of the sotrage for our container (going to be discussed rn). If we tried to use arrays on the stack it would be hard/impossibel to resize our internal capacity.
Q: Isn't it inefficient to copy anything and potentially hard for the OS to find larger and larger continguous memory arrays?
A1: Yes, there is an expense involving in growing an array
A2: Yes copying everything over and asking for new memory is an expensive operation which is why we try to do it relatively infrequently (why we double the size every time). Plus if we want to store a lot of information, there is no other alternative!
Q: does peek() as it is currently written (return elements[count-1]) return a copy of the value stored in the stack? in particular if the stack were to store a non-primitive type?
A1: yes
A2: Yes, it returns a copy, good catch.
Q: instead of moving the whole array, couldn't you somehow store a pointer to the next allocated memory slots? Is there a way to implement this?
A1: live answered
A2: It would be a lot more complicated to try to store ifnromation about every distinct chunk of memory you own and which elements are stored where
Q: is there a way to make elements a reference to newElements, or do we not care about having two pointers pointing to the same thing
A1: We will eventually update elements to point to the new array, but we need to free whats stored at the array currently pointed to by elements first
A2: We temporarily need both (since we are going to copy from one to the other)
Q: What does the [] mean again int he delete statement?
A1: It basically means “free the array pointed to by this pointer”
Q: i though we never call the delete function
A1: We never call the deconstructor. We do call delete
A2: No, we definitely need to call the delete function. Chris may have mentioned earlier we never manually call a class destructor but that is a very different concept
Q: Is the delet deleted the value or address?
A1: Remember, delete doesn’t really delete anything. It frees the array pointed to by the pointer.
A2: It vrees the memory at the address letting the computer konw that that memory is available
Q: So everytime we expand, we get one more pointer, but its not a big problem because each pointer is just a single address worth of memory?
A1: The class only stores one pointer, we reassign that pointer to a differnet address when we expand, but there is no additional pointer being stored for each expand
Q: What would happen if we deleted newElements at the end?
A1: Then we would not longer have any valid memory assigned to us, and any later access would likely crash
A2: We essentially would have now new expanded array
Q: if we delete the elements then set newelements equal to it why isnt that problematic
A1: We first free the memory pointed to by elements (give it back to the OS) then we make the pointer point to a different location in memory. There’s nothing illegal we’ve done here!
Q: if there was no asterisk in the newElements, we would have had two arrays and there would have been no memory reallocation?
A1: Without an asterisk, the code would not compile
Q: Would we need to explicitly call the expand function in our program or is it implicitly called like delete?
A1: You must explicit choose to expand
A2: No, we are in charage of manually calling expand when necessary.
Q: Could we combine steps 1 and 5 by writing cpacity *= 2 in place of capacity * 2?
A1: Yeah, that would work.
Q: is elements not limited to 8?
A1: live answered
Q: when we made the word editor, it thought you couldn't do
Q: oops disregard that
Q: if we want to shrink, we still need to find a new address with smaller capacity and copy all the integers right?
A1: Yes, exactly
A2: Yes (but we typically do not do that)
Q: So the push operation for Stack isn’t really O(1) in the cases when we have to expand?
A1: Correct, but in most cases it’s O(1)
A2: Yes, it would be O(n) in cases where we have to expand but that cost is dsitributed over all calls to stack (since most are O(1)) so in general we say push is still a O(1) operation
Q: how do you support uniform initialization in your class, like StackInt myStack = {1,2,3,4}
A1: live answered
Q: Are we always able to access the pointer after deleting the array it points to?
A1: Yes, unless you move the pointer away from that address
A2: We are always able to reassign the pointer to point somewhere else, but we can’t try to dereference it after we’ve freed the memory it points at
Q: so if we have an extra empty space because of the pop function, if the code needed one more space of memory would the code still call expand or just fill that one empty space in the array?
A1: live answered
Q: Do the Stanford data structures use a factor of 2 to increase capacity? Which initial capacities / capacity multipliers are most efficient?
A1: Doubling is a common strategy
Q: What about isEmpty, size, and the private bit?
A1: Sorry, what about them?
Q: What would the effect of *elements = *newElements be?
A1: That would copy the first element from newElements and overwrite the first element of elements
A2: You would set the first element of elements to be the first element of newElements
Q: what the [] after delete doing ?
A1: They specify that we are freeing an arrays worth of memory
Q: if it become garbage, we can still return it?
A1: live answered
Q: Why can't we just increment the array by 1 every time we need to add an element rather than have an explicit function to expand
A1: This is less efficient. Every time we expand this is an expensive time cost
A2: Expanding the capacity of the array is a very expensive process (request new memory, copy everythign over, etc) so we try to do it as rarely as possible by doubling by 2 when necessary
Q: Oh, sorry, @ my earlier question, I was just wondering why we didn’t write those 3 functions (isEmpty, size, etc) —did we just choose not to write them this lecture?
A1: live answered
A2: we did write them! they’re pretty straight forward (one line)
Q: What is the difference between array and pointer when u created the int* array? If it is a pointer, why don't u have to dereference it when u access it?
A1: array bracket syntax is doing an implicit dereference
Q: if we change a variable name in the class, do we have to change it in the header?
A1: All instance variables are defined in the header file so yes namiin must be consistent there
Q: What is going on behind the scenes of using namespace std and why can’t we use using namespace StackInt? How does namespace know which lines to use the namespace for?
A1: live answered
A2: StackInt isn’t really a namespace