EECS 281 Midterm || All Accurate 100%.
What is memory ownership for a container? correct answers When a container owns a value,
only that container can modify the value. A drawback of this is it takes a long time to copy
containers like this. When a container has pointers, either the container or other objects
pointing to the same thing can modify, which can be unsafe. This can be used for shared data.
When a container owns a reference to a value, it doesn't own the value. You cannot delete by
reference. The value must be initialized but cannot be assigned to.
student answer:
Memory ownership of a container refers to how controlled the interface is to the data held
within the container. There are different degrees of ownership ranging from no control (as in
the case of references) to a lot of control (which is the default from within the container). A
container class can control how much access objects outside the class can have over the
elements of the container (hence the class has a public interface for other objects).
- A container composed of values can completely restrict or give complete access to the
elements (the former being impractical and the latter being close to what vector does) but in
either situation the container class mutates the data.
- A container composed of pointers however is a different story. Because they contain
pointers, the container only protects the location data (the pointer data) but it cannot protect
or control the interface to the data stores at the addresses. Thus, the container does not have
total control over the relevant data. Hypothetically, an object outside the container can make
edits to the data.
What are some disadvantages of arrays? correct answers when many insertions are needed,
we need to move everything over EVERY time we insert a number.
One disadvantage of an array is that there are no bound checks so you increase the change of
illegally accessing memory (causing a seg fault) or you need O(1) complexity overhead like a
size variable to maintain bound checks.
Why do you need a const and non-const version of some operators?
What should non=const op[ ] return ? correct answers Read and write. In some cases, the
compiler knows it can speed some things up if it knows it never has to make any changes.
Non const operator returns the object, which can be modified.
You would need both const and non-const version of operations because you would want to
be as safe as possible. One good rule for C++ programming from the book "Effective C++"
highlights that you should make every variable you don't manipulate a const variable to
protect any data you can. Having methods return const makes your operation more resilient to
potential bugs (like accidently mutating data in a container when you didn't want to).
how many destructor calls (min, max) can be invoked by
operator delete
operator delete[ ] correct answers A destructor should have only one call to delete for each
new allocation to the heap and one call to delete[] for each new[] allocation to the heap.
Why would you use a pointer-based copying algorithm? correct answers Pointer-based
algorithm works with both random access and sequential access (ex: will work with both a
linked list and a vector).Random access would not work with a linked list, just a vector.
, You would use a pointer-based copying algorithm when the objects are very large and it
would be costly to copy or when you don't necessarily know the end of a container so you
can use a nullptr as the null terminator. This is the idea behind vector.end() iterator which is
an iterator that points one past the end of a vector.
Are C++ strings null-terminated? correct answers no
Give two examples of off-by-one bugs correct answers accessing one off the end of the array
when comparing i <= SIZE. Assigning one off the end of the array with arr[i] = arr[i + 1]
when i = size - 1.
How do I set up a two-dim array class? correct answers setup an array of int pointers:
const int ** arr = new int * [R];
The array is a collection of pointers, which is currently not looking at anything
Perform an amortized complexity analysis of an automatically resizable container with a
doubling policy correct answers When a call to add an element places the element one passed
the end, the container will resize to twice it's size. In amortized complexity analysis, we find
the cost per operation over a sequence of operations. In the worst case of the container
reaching it's limit, the complexity of the nth addition would be O(n). However, the next n-1
calls to add an element will have a O(1) complexity. So we have n + n(1) = 2n => O(n)
complexity. O(n) / n = O(1) amortized complexity.
Discuss pros and cons of pointers and references when implementing container classes.
correct answers Pointers vs references in container classes.
Pointers are useful for having containers of large objects. They are also useful for sharing
data with other objects (as long as you have mutually exclusive locks on data as they are
being edited just so you don't have two objects accidently edit the object at the same time).
References are useful for function returns but aren't very useful as elements of the container.
Convert indexing between a 1D array and a 2D array correct answers 1D to 2D: column =
index % num_columns
row = index / num_columns
2D to 1D: index = row * num_columns + column
Copying complexities: worst, best and average case correct answers O(n)
write an algorithm for dynamic reallocation of array class (aka, inserting something when the
array is full) correct answers
time complexity of inserting into an array correct answers Best case: O(1). We just need to
insert at the end
Worst case: O(n). We need to loop through the whole thing and insert at the beginning
What is memory ownership for a container? correct answers When a container owns a value,
only that container can modify the value. A drawback of this is it takes a long time to copy
containers like this. When a container has pointers, either the container or other objects
pointing to the same thing can modify, which can be unsafe. This can be used for shared data.
When a container owns a reference to a value, it doesn't own the value. You cannot delete by
reference. The value must be initialized but cannot be assigned to.
student answer:
Memory ownership of a container refers to how controlled the interface is to the data held
within the container. There are different degrees of ownership ranging from no control (as in
the case of references) to a lot of control (which is the default from within the container). A
container class can control how much access objects outside the class can have over the
elements of the container (hence the class has a public interface for other objects).
- A container composed of values can completely restrict or give complete access to the
elements (the former being impractical and the latter being close to what vector does) but in
either situation the container class mutates the data.
- A container composed of pointers however is a different story. Because they contain
pointers, the container only protects the location data (the pointer data) but it cannot protect
or control the interface to the data stores at the addresses. Thus, the container does not have
total control over the relevant data. Hypothetically, an object outside the container can make
edits to the data.
What are some disadvantages of arrays? correct answers when many insertions are needed,
we need to move everything over EVERY time we insert a number.
One disadvantage of an array is that there are no bound checks so you increase the change of
illegally accessing memory (causing a seg fault) or you need O(1) complexity overhead like a
size variable to maintain bound checks.
Why do you need a const and non-const version of some operators?
What should non=const op[ ] return ? correct answers Read and write. In some cases, the
compiler knows it can speed some things up if it knows it never has to make any changes.
Non const operator returns the object, which can be modified.
You would need both const and non-const version of operations because you would want to
be as safe as possible. One good rule for C++ programming from the book "Effective C++"
highlights that you should make every variable you don't manipulate a const variable to
protect any data you can. Having methods return const makes your operation more resilient to
potential bugs (like accidently mutating data in a container when you didn't want to).
how many destructor calls (min, max) can be invoked by
operator delete
operator delete[ ] correct answers A destructor should have only one call to delete for each
new allocation to the heap and one call to delete[] for each new[] allocation to the heap.
Why would you use a pointer-based copying algorithm? correct answers Pointer-based
algorithm works with both random access and sequential access (ex: will work with both a
linked list and a vector).Random access would not work with a linked list, just a vector.
, You would use a pointer-based copying algorithm when the objects are very large and it
would be costly to copy or when you don't necessarily know the end of a container so you
can use a nullptr as the null terminator. This is the idea behind vector.end() iterator which is
an iterator that points one past the end of a vector.
Are C++ strings null-terminated? correct answers no
Give two examples of off-by-one bugs correct answers accessing one off the end of the array
when comparing i <= SIZE. Assigning one off the end of the array with arr[i] = arr[i + 1]
when i = size - 1.
How do I set up a two-dim array class? correct answers setup an array of int pointers:
const int ** arr = new int * [R];
The array is a collection of pointers, which is currently not looking at anything
Perform an amortized complexity analysis of an automatically resizable container with a
doubling policy correct answers When a call to add an element places the element one passed
the end, the container will resize to twice it's size. In amortized complexity analysis, we find
the cost per operation over a sequence of operations. In the worst case of the container
reaching it's limit, the complexity of the nth addition would be O(n). However, the next n-1
calls to add an element will have a O(1) complexity. So we have n + n(1) = 2n => O(n)
complexity. O(n) / n = O(1) amortized complexity.
Discuss pros and cons of pointers and references when implementing container classes.
correct answers Pointers vs references in container classes.
Pointers are useful for having containers of large objects. They are also useful for sharing
data with other objects (as long as you have mutually exclusive locks on data as they are
being edited just so you don't have two objects accidently edit the object at the same time).
References are useful for function returns but aren't very useful as elements of the container.
Convert indexing between a 1D array and a 2D array correct answers 1D to 2D: column =
index % num_columns
row = index / num_columns
2D to 1D: index = row * num_columns + column
Copying complexities: worst, best and average case correct answers O(n)
write an algorithm for dynamic reallocation of array class (aka, inserting something when the
array is full) correct answers
time complexity of inserting into an array correct answers Best case: O(1). We just need to
insert at the end
Worst case: O(n). We need to loop through the whole thing and insert at the beginning
