CSE 332: Fall 2020 Pandemic Exam Replacement Assigned: 11/19/2020 Due: 11/25/2020 11:59 PM CT Percent of final grade: 14% In place of an in-person exam, this assignment is designed to be a cumulative review of concepts covered so far this semester. Topics covered will be: 1. Pointers and pointer arithmetic 2. Dynamic memory management 3. Copy control 4. Design of the STL Note: This is an individual assignment and academic integrity checks will be made. TAs will be instructed not to answer questions over the exam or help with exam code in office hours (you may ask about slides, concepts we have covered, past assignments, etc.). Any logistical questions on the exam can be asked on Piazza or via email to Prof. Shidal. Overview of the assignment: In this assignment, you will implement your own deque data structure as well as an iterator for your deque implementation. Deque stands for double-ended queue and supports a similar set of methods as the vector class. However, the vector class only supports insertions to the back of the vector using the push_back method, whereas a deque supports insertions to the front or back of the deque. To keep the assignment to a reasonable length, you will only be implementing a subset of the functions std::deque supports. You will implement a slimmed down iterator as well. (~300-400 lines of code for the deque implementation, ~100-300 lines of code for the iterator) The grading breakdown is as follows: Getting started: Important: This assignment will be graded using unit tests. Some tests are provided and you should make sure your implementation passes those tests. To ensure your code works well with the unit tests, it is important that you name classes and public member functions exactly as Code: Percentage of grade Part I: my_deque implementation 70% Part II: my_deque_iterator implementation 30% described in this document (anything highlighted in blue needs to be named exactly as it is typed in this document, for example: “my_deque”). As in studios 16-21, all files needed for this lab have already been created for you (my_deque.h, my_deque.cpp, my_deque_iterator.h, my_deque_iterator.cpp, and files containing the tests), so you should not move the files around, rename files, or create new files. 1. To create your repository, visit the link here and accept the assignment. 2. Open a Windows remote desktop and open Visual Studio. Clone your repository to your h: drive as described in Studio 2. All you need to do is clone your repo, a Visual Studio Solution is already set up for you. 3. Within Visual Studio, open the “Team Explorer” tab. From the “manage connections” screen, make sure your repository is listed under “Local Git Repositories”. If it is not, click “Add”, navigate to your cloned copy of the repository, and open it. You should see the repository appear under “Local Git Repositories”. Double-click it to make it your active repository. At the bottom of the ”Home” screen of the “Team Explorer” tab, you should see all .sln(visual studio solutions) stored in the repository (there should only be 1). Open “deque_assignment.sln” by double-clicking on it and then switch to the “Solution Explorer” tab. You should see the “deque_assignment” project as well as “deque_test”. All of your code should be written within the “deque_assignment” project. “deque_test” contains a set of tests provided so that you may test your codes’ functionality. 4. Expand the “deque_assignment” project. You should see the following header and source files. I’ve provided an overview of what code you will write in each file as well. a. my_deque.h - declaration of the my_deque class b. my_deque.cpp - function definitions for my_deque class c. my_deque_iterator.h - declaration of my_deque_iterator class d. my_deque_iterator.cpp - definitions for my_deque_iterator class e. deque_assignment.cpp - contains main(), you can use this to test your code as you work You should write all of your code in these files. You should not rename or move these files. 5. Testing: Originally, many (or all) of the tests will contain errors as you have not declared/defined the required classes yet. I would suggest commenting out the tests with errors. As you implement required functionality, you can uncomment and run tests that only use functionality you have implemented so far. To run the unit tests to test your code perform the following steps: 1. Make sure you have built your program. 2. Select “Test >> Windows >> Test Explorer” from the top bar of your VS window. This will open the Test Explorer Window. 3. Click the green arrow to run ALL tests. Failed tests will show up red and passed tests will show up green. 4. Go back and fix any code that did not pass the given tests! Look at the test for more details on what might have gone wrong. You can also debug the test by right-clicking a test in the “test explorer” window and selecting “debug”. Make sure to set breakpoints in the test or in your code. Note: Rebuild after you make any changes to your solution before you rerun the tests! Overview of deque implementation: The deque data structure has a few highlights: ● Elements can be inserted to the front or back of the deque in amortized constant time ● Elements can be removed from the front or back of the deque in amortized constant time ● A deque provides random access to its elements A typical deque implementation would use generic programming (templates in C++) which we did not cover in this course. Templates would allow us to create a deque class that can hold many different element types. Your deque will be implemented to store integers only. Also, although the C++ standard does not require that elements in a deque are stored in contiguous memory, the implementation you write for this assignment will. Your deque will maintain a pointer to a dynamically allocated array, the size of that array, and some information about which locations in the array are currently filled (lIndex and rIndex). To support insertions to the front or back of the deque, elements will be stored in the middle of the array, with some empty locations on either end. The example above illustrates this, and gives you a glimpse into the member variables that you may need to maintain in your deque implementation. If an int (say 1) was pushed to the front of the deque, it would be updated as illustrated below: And if an int (say 4) was pushed to the back of the deque, it would be updated as so: Popping an element from the back would then update the deque back to the state shown here: Resizing: So, the basic functionality of this deque implementation is somewhat straightforward, but you have some additional cases to handle. As more elements are added to the deque. the array will eventually fill up. Or, if many elements are popped from the deque, the array will take up more space than is needed. Your deque implementation will have to manage growing and shrinking the underlying array as elements are added or removed. Your implementation should follow these rules: 1. If there is no room for an element being inserted, the array will either be doubled in size or the elements in the array will be re-centered to make room. If the number of elements in the deque will become greater than (size / 2) after the element is inserted, it should be doubled. Otherwise, it should be re-centered. 2. If the number of elements in the deque becomes less than (size / 8), the array size should be cut in half. The array should never shrink below its initial size. As examples, say we have a deque in the current state: Now we push the integer 9 to the back of the deque. It will contain 6 elements, which is greater than size/2 and there is no space at the end of the array for the 9, so the array must be resized before pushing 9 into it. After the push executes, the deque would be in the following state: Notice, a new array of twice the size was allocated, elements were copied and centered in the new array, and finally 9 was pushed to the back of the array. (think about what has to happen to the old array to avoid memory leaks). From here, if all elements were removed except for one, the number of elements in the deque would be less than its size / 8, so we would need to resize the array by cutting it in half. The remaining elements would then be centered in the new array. The deque would look like the following if all elements were removed except for the 4 (via pop_back()): Centering: The next case we have to worry about is all of the elements stored in the deque becoming shifted to one end of the array. Imagine a sequence of insertions to the back of the deque, as well as some pops from the front of the deque. We could end in a state that looks something like: In this case, the array does not need to be resized (it will not contain greater than size/2 elements after an insertion), but instead it needs to be recentered. After recentering, the deque would look like: The elements stored in a deque should be re-centered when there is no space remaining for an element to be inserted and the number of elements in the deque after the insertion will be less than or equal to (size / 2). Additional details: ● The underlying array should not shrink to a size below its initial size, which will be supplied when the deque is constructed. The initial size will always be an even number. ● lIndex and rIndex should never refer to a location in the array that contains an element, instead they refer to the location the next element will be inserted into. ● When a push or a pop requires resizing or recentering and the deque will contain an odd number of elements after the push or pop, there should always be 1 more element in the front half of the array than the back half. Part I: Implement my_deque Implementation details: Open my_deque.h and my_deque.cpp. In these files, you will declare and define a class called “my_deque”. Your my_deque class should contain the following functions in its public interface: a. my_deque(int initial_size); b. my_deque(const my_deque & d); c. ~my_deque(); d. int get_used(); e. int get_size(); f. int get_lIndex(); g. int get_rIndex(); h. void push_back(int v); i. void push_front(int v); j. int pop_back(); k. int pop_front(); l. int * get_mem(); m. int& operator[](const int i); Go ahead and declare the my_deque class and add these functions to the class’s public interface. Add member variables as needed to track the required information discussed in the above section. I will refer to this data as “array”, “size”, “rIndex”, and “lIndex” in this document, although you may name the variables whatever you would like as well as add additional member variables if needed. Then, define the member functions to do nothing for now (or return some dummy value if a return value is expected). Many of the unit tests should compile once you have done this (but will fail if you run them), go ahead and uncomment the tests that you can (the tests that compile). As you implement the member functions, you should start to see some of these tests pass. Now, implement the member functions of the my_deque class as described below: a. my_deque(int initial_size) Dynamically allocate an array of integers with size initial_size. Set the appropriate member variable to point to this array. Set the size member variable accordingly. Set lIndex and rIndex to refer to the two middle indices in the array. They should not refer to the same location. b. my_deque(const my_deque & d) First, design an experiment to determine if std::deque provided by the C++ STL provides a deep copy constructor or a shallow copy constructor. Code this experiment in the main function (in deque_assignment.cpp). In your ReadMe.txt file for this assignment, clearly mark a section called “Deep vs. Shallow copy”. Paste your experiment code and describe how the experiment will be able to determine which type of copy std::Deque makes. Answer the question: Does std::deque provide a deep copy constructor or a shallow copy constructor? (this is worth 5% of the assignment grade) Define the copy constructor for your my_deque class to make a deep copy. c. ~my_deque() Define your destructor in an appropriate way given that the copy constructor makes a deep copy. Be sure to avoid double deletions, dangling pointers, or memory leaks. d. int get_used() Return the number of elements currently in the deque. This is not the size of the array. e. int get_size() Return the size of the array managed by the deque. f. int get_lIndex() Return lIndex. g. int get_rIndex() Return rIndex. h. void push_back(int v) Expand or recenter the array if needed to make room for the element being pushed. Add v to the end of the array maintained by the deque. Update member variables as needed. Make sure to avoid memory leaks. i. void push_front(int v) Expand or recenter the array if needed to make room for the element being pushed. Add v to the beginning of the array maintained by the deque. Update member variables as needed. Make sure to avoid memory leaks. j. int pop_back() Remove 1 element from the back of the deque and return a copy of it. If there is no element to be removed, an exception of type std::exception should be thrown. If the array requires resizing, resize the array. Make sure to avoid memory leaks. k. int pop_front() Remove 1 element from the front of the deque and return a copy of it. If there is no element to be removed, an exception of type std::exception should be thrown. If the array requires resizing, resize the array. Make sure to avoid memory leaks. l. int * get_mem(); Return the address of the array managed by the deque. m. int& operator[](const int i) Return the ith element in the deque. If i is not a valid index (there is no element stored at that location), an exception of type std::exception should be thrown. You can test some of these functions as you go, however at this point you should be able to uncomment all tests for my_deque and ensure they are passing. Part II: Implement my_deque_iterator Completing part I correctly will result in a maximum grade of 70%. The tests for part II rely on part I being implemented correctly, so you would be better served continuing to work on part I rather than skipping to part II. Overview of my_deque_iterator: In this part of the assignment, you will implement an iterator for your deque class. The iterator will be slimmed down compared to a random access iterator supplied by the STL. Your iterator class, which will be named my_deque_iterator should be declared/defined in my_deque_iterator.h/my_deque_iterator.cpp. Your iterator will store the address of the integer it is currently referring to, as well as maintain access to the my_deque object it is iterating over. As an example, here is an image that would represent an iterator and deque object. The iterator maintains a pointer to the deque object, which gives it access to the deque it is iterating over. It also maintains a pointer to the element in the deque it is currently pointed to. The above example shows an iterator in a valid state, as it can be dereferenced to get an element in the deque. An iterator may be in one of 2 other states: 1. Invalid: The iterator does not point to an element in the deque. Anytime an iterator becomes invalid, its “curr” pointer should be set to nullptr or 0. 2. Past the end: The iterator is past the end if its “curr” pointer points to the location in the deque just past the last valid element in the deque. Your iterator should always be in one of these 3 states. In other words, if the iterator is not valid and not past the end, it should be in the invalid state and “curr” should be a nullptr. Implementation details: Open my_deque_iterator.h and declare the my_deque_iterator class. It should have private member variables to store the address of the integer it is currently referring to (“curr” in the above illustrations, but you can name it whatever you would like), as well as the address of the my_deque object the iterator is currently iterating over (“deque” in the above illustrations, but you can name it whatever you like). Declare the following member functions in the class’s public interface and define them as described: a. my_deque_iterator (int *, my_deque*) Initialize “curr” and “deque” with the parameters accordingly. Determine which state the iterator is in and update if needed. b. my_deque _iterator operator+ (int n) Create and return a new my_deque_iterator that is advanced by n integers. If n is negative, an invalid my_deque_iterator should be returned. c. my_deque_iterator & operator+= (int n) Update the my_deque_iterator this function is called on to be advanced by n integers in the deque. Once again, if n is negative the iterator should be placed in an invalid state. After updating, return the my_deque_iterator this function is called on by reference. d. int & operator* () Return a reference to the integer the my_deque_iterator is currently aliasing. If the iterator is not valid (it is invalid or past the end) an exception of type std::exception should be thrown. e. bool operator< (const my_deque_iterator compare_against) const If either of the my_deque_iterators this function acts on is in an invalid state or if they are not iterating over the same deque, throw an exception of type std::exception. Otherwise, return true if “this” is aliasing an integer that comes before the integer aliased by “compare_against” in the deque and false otherwise. A past the end iterator is larger than any valid iterator iterating over the same deque. f. bool operator== (const my_deque_iterator) const Returns true if the 2 my_deque_iterators this function acts on iterate over the same deque object and are aliasing the same integer element of the deque. Return false otherwise. g. int * get_mem(); Return the memory address of the integer this iterator is currently aliasing. Adding begin() and end() to my_deque: Now that you have implemented an iterator for your deque implementation, declare and define two additional member functions of your my_deque class in my_deque.h and my_deque.cpp. Those functions should be: a. my_deque_iterator begin() Create and return a my_deque_iterator that is initialized to iterate over “this” my_deque object and is initialized to alias the first element in “this” deque. If there are no elements in the deque, a past the end iterator should be returned. b. my_deque_iterator end() Create and return a my_deque_iterator that is initialized to iterate over “this” my_deque object and is in a past the end state. At this point, all tests can be uncommented and run. Run the test and modify your implementations as needed to ensure your deque and iterator implementations are working correctly.
欢迎咨询51作业君
