Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

CS 32: Introduction to Computer Science II

Homework 4

Time due: 11:00 PM Tuesday, March 4

1. We anticipate that many people working on Project 3 will spend a lot of time debugging something that arises from a common novice misunderstanding. To save you that time later, we'll give you a chance to make that mistake in a simpler context, so you can work out that issue and how it manifests itself. (It may turn out that you don't have that misunderstanding, so you won't have any issues doing this problem. Still, keep this problem in mind, because you may still make the mistake in Project 3.)

   Be especially sure to run your code for this problem under g32 to help ensure that there are no pointer/iterator violations or memory leaks which that common misunderstandings may lead to.

   Material about vectors, lists, and iterators are in lecture09-updated.pptx in Carey Nachenberg's slides and David Smallberg's STL lecture and STL slides.

   1. Implement the removeOdd function; you must use list's erase member function; you must not use list's remove or remove_if member functions. Each int in the list must be examined for oddness no more than once.#include <list> #include <vector> #include <algorithm> #include <iostream> #include <cassert> using namespace std; // Remove the odd integers from li. // It is acceptable if the order of the remaining even integers is not // the same as in the original list. void removeOdd(list<int>& li) { } void test() { int a[9] = { 5, 2, 8, 9, 6, 7, 3, 4, 1 }; list<int> x(a, a+9); // construct x from the array assert(x.size() == 9 && x.front() == 5 && x.back() == 1); removeOdd(x); assert(x.size() == 4); vector<int> v(x.begin(), x.end()); // construct v from x sort(v.begin(), v.end()); int expect[4] = { 2, 4, 6, 8 }; for (int k = 0; k < 4; k++) assert(v[k] == expect[k]); } int main() { test(); cout << "Passed" << endl; }

      For this problem, you will turn a file named oddlist.cpp with the body of the removeOdd function, from its "void" to its "}", no more and no less. Your function must compile and work correctly when substituted into the program above, leaking no memory.

   2. Implement the removeOdd function; you must use vector's erase member function. Each int in the vector must be examined for oddness no more than once.#include <vector> #include <algorithm> #include <iostream> #include <cassert> using namespace std; // Remove the odd integers from v. // It is acceptable if the order of the remaining even integers is not // the same as in the original vector. void removeOdd(vector<int>& v) { } void test() { int a[9] = { 5, 2, 8, 9, 6, 7, 3, 4, 1 }; vector<int> x(a, a+9); // construct x from the array assert(x.size() == 9 && x.front() == 5 && x.back() == 1); removeOdd(x); assert(x.size() == 4); sort(x.begin(), x.end()); int expect[4] = { 2, 4, 6, 8 }; for (int k = 0; k < 4; k++) assert(x[k] == expect[k]); } int main() { test(); cout << "Passed" << endl; }

      For this problem, you will turn a file named oddvector.cpp with the body of the removeOdd function, from its "void" to its "}", no more and no less. Your function must compile and work correctly when substituted into the program above, leaking no memory.

   3. Implement the removeBad function; you must use list's erase member function; you must not use list's remove or remove_if member functions. Each Movie in the list must have its rating examined no more than once.#include <list> #include <vector> #include <algorithm> #include <iostream> #include <cassert> using namespace std; vector<int> destroyedOnes; class Movie { public: Movie(int r) : m_rating(r) {} ~Movie() { destroyedOnes.push_back(m_rating); } int rating() const { return m_rating; } private: int m_rating; }; // Remove the movies in li with a rating below 50 and destroy them. // It is acceptable if the order of the remaining movies is not // the same as in the original list. void removeBad(list<Movie*>& li) { } void test() { int a[9] = { 25, 85, 80, 30, 70, 20, 15, 90, 10 }; list<Movie*> x; for (int k = 0; k < 9; k++) x.push_back(new Movie(a[k])); assert(x.size() == 9 && x.front()->rating() == 25 && x.back()->rating() == 10); removeBad(x); assert(x.size() == 4 && destroyedOnes.size() == 5); vector<int> v; for (list<Movie*>::iterator p = x.begin(); p != x.end(); p++) { Movie* mp = *p; v.push_back(mp->rating()); } // Aside: Since C++11, the above loop could be // for (auto p = x.begin(); p != x.end(); p++) // { // Movie* mp = *p; // v.push_back(mp->rating()); // } // or // for (auto p = x.begin(); p != x.end(); p++) // { // auto mp = *p; // v.push_back(mp->rating()); // } // or // for (Movie* mp : x) // v.push_back(mp->rating()); // or // for (auto mp : x) // v.push_back(mp->rating()); sort(v.begin(), v.end()); int expect[4] = { 70, 80, 85, 90 }; for (int k = 0; k < 4; k++) assert(v[k] == expect[k]); sort(destroyedOnes.begin(), destroyedOnes.end()); int expectGone[5] = { 10, 15, 20, 25, 30 }; for (int k = 0; k < 5; k++) assert(destroyedOnes[k] == expectGone[k]); for (list<Movie*>::iterator p = x.begin(); p != x.end(); p++) delete *p; } int main() { test(); cout << "Passed" << endl; }

      For this problem, you will turn a file named badlist.cpp with the body of the removeBad function, from its "void" to its "}", no more and no less. Your function must compile and work correctly when substituted into the program above, leaking no memory.

   4. Implement the removeBad function; you must use vector's erase member function. Each Movie in the vector must have its rating examined no more than once.#include <vector> #include <algorithm> #include <iostream> #include <cassert> using namespace std; vector<int> destroyedOnes; class Movie { public: Movie(int r) : m_rating(r) {} ~Movie() { destroyedOnes.push_back(m_rating); } int rating() const { return m_rating; } private: int m_rating; }; // Remove the movies in v with a rating below 50 and destroy them. // It is acceptable if the order of the remaining movies is not // the same as in the original vector. void removeBad(vector<Movie*>& v) { } void test() { int a[9] = { 25, 85, 80, 30, 70, 20, 15, 90, 10 }; vector<Movie*> x; for (int k = 0; k < 9; k++) x.push_back(new Movie(a[k])); assert(x.size() == 9 && x.front()->rating() == 25 && x.back()->rating() == 10); removeBad(x); assert(x.size() == 4 && destroyedOnes.size() == 5); vector<int> v; for (int k = 0; k < 4; k++) v.push_back(x[k]->rating()); sort(v.begin(), v.end()); int expect[4] = { 70, 80, 85, 90 }; for (int k = 0; k < 4; k++) assert(v[k] == expect[k]); sort(destroyedOnes.begin(), destroyedOnes.end()); int expectGone[5] = { 10, 15, 20, 25, 30 }; for (int k = 0; k < 5; k++) assert(destroyedOnes[k] == expectGone[k]); for (vector<Movie*>::iterator p = x.begin(); p != x.end(); p++) delete *p; } int main() { test(); cout << "Passed" << endl; }

      For this problem, you will turn a file named badvector.cpp with the body of the removeBad function, from its "void" to its "}", no more and no less. Your function must compile and work correctly when substituted into the program above, leaking no memory.

   5. Make sure you understand why the code below passes the first two tests but fails the third. Draw pictures if necessary. Don't forget the lesson you learn from this problem when working on Project 3.#include <iostream> #include <vector> #include <list> using namespace std; const int MAGIC = 11223344; void test() { bool allValid = true; vector<int> v1(5, MAGIC); int k = 0; for ( ; k != v1.size(); k++) { if (v1[k] != MAGIC) { cout << "v1[" << k << "] is " << v1[k] << ", not " << MAGIC <<"!" << endl; allValid = false; } if (k == 2) { for (int i = 0; i < 5; i++) v1.push_back(MAGIC); } } if (allValid && k == 10) cout << "Passed test 1" << endl; else cout << "Failed test 1" << endl; allValid = true; list<int> l1(5, MAGIC); k = 0; for (list<int>::iterator p = l1.begin(); p != l1.end(); p++, k++) { if (*p != MAGIC) { cout << "Item# " << k << " is " << *p << ", not " << MAGIC <<"!" << endl; allValid = false; } if (k == 2) { for (int i = 0; i < 5; i++) l1.push_back(MAGIC); } } if (allValid && k == 10) cout << "Passed test 2" << endl; else cout << "Failed test 2" << endl; allValid = true; vector<int> v2(5, MAGIC); k = 0; for (vector<int>::iterator p = v2.begin(); p != v2.end(); p++, k++) { if (k >= 20) // prevent infinite loop break; if (*p != MAGIC) { cout << "Item# " << k << " is " << *p << ", not " << MAGIC <<"!" << endl; allValid = false; } if (k == 2) { for (int i = 0; i < 5; i++) v2.push_back(MAGIC); } } if (allValid && k == 10) cout << "Passed test 3" << endl; else cout << "Failed test 3" << endl; } int main() { test(); }

      Explain in a sentence or two what happens during the execution of test case 3 that eventually leads to test case 3 failing.

2. The files Sequence.h and Sequence.cpp contain the definition and implementation of Sequence implemented using a doubly-linked list. A client who wants to use a Sequence has to change the type alias declaration in Sequence.h, and within one source file, cannot have two Sequences containing different types.

   Eliminate the using statement defining the type alias, and change Sequence to be a class template, so that a client can say

   #include "Sequence.h" #include <string> using std::string; ... Sequence<int> si; Sequence<string> ss; si.insert(30); ss.insert("30 For 30"); ...

   Also, change subsequence and zipper to be function templates.

   (Hint: Transforming the solution based on a type alias is a mechanical task that takes five minutes if you know what needs to be done. What makes this problem non-trivial for you is that you haven't done it before; the syntax for declaring templates is new to you, so you may not get it right the first time.)

   (Hint: Template typename parameters don't have to be named with single letters like T; they can be names of your choosing. You might find that by choosing the name ItemType, you'll have many fewer changes to make.)

   (Hint: The Node class nested in the Sequence class can talk about the template parameter of the Sequence class; it should not itself be a template class.)

   The declarations and implementations of your Sequence class template and the subsequence and zipper template functions must be in just one file, Sequence.h, which is all that you will turn in for this problem. Although the implementation of a non-template non-inline function should not be placed in a header file (because of linker problems if that header file were included in multiple source files), the implementation of a template function, whether or not it's declared inline, can be in a header file without causing linker problems, and in fact the header file is the normal place to put it in most C++ environments.

   There's a pre-C++20 language technicality that relates to a type declared inside a class template, like N below:

   template <typename T> class S { ... struct N { ... }; N* f(); ... };

   The technicality affects how we specify the return type of a function (such as S<T>::f) when that return type uses a type defined inside a template class (such as S<T>::N). If we attempt to implement f this way:

   template <typename T> S<T>::N* S<T>::f() // Error! Won't compile in C++17 or earlier. { ... }

   the pre-C++20 technicality requires the compiler to not recognize S<T>::N as a type name; it must be announced as a type name this way:

   template <typename T> typename S<T>::N* S<T>::f() // OK in all C++ versions { ... }

   Giving g32 the -std=c++20 option will cause it to use C++20. We will test your code with C++17, unless it doesn't compile, in which case we'll test it with C++20 instead.

   For you to not get a score of zero for this problem, this test program that we will try with your Sequence.h must build and execute successfully under both g32 and either Visual C++ or clang++, with no Sequence.cpp file on the command line (for g32) or as part of the project (for Visual C++ or Xcode):

   #include "Sequence.h" #include <iostream> #include <string> #include <cassert> using namespace std; void test() { Sequence<int> si; assert(si.empty()); assert(si.size() == 0); assert(si.insert(0, 20) == 0); assert(si.insert(10) == 0); assert(si.find(20) == 1); assert(si.remove(10) == 1); int i; assert(si.get(0, i)); assert(si.set(0, 30)); assert(si.erase(0)); Sequence<int> si2(si); si2.swap(si); si2 = si; assert(subsequence(si,si) == -1); zipper(si,si2,si); Sequence<string> ss; assert(ss.empty()); assert(ss.size() == 0); assert(ss.insert(0, "Hello") == 0); assert(ss.insert("Goodbye") == 0); assert(ss.find("Hello") == 1); assert(ss.remove("Goodbye") == 1); string s; assert(ss.get(0, s)); assert(ss.set(0, "Aloha")); assert(ss.erase(0)); Sequence<string> ss2(ss); ss2.swap(ss); ss2 = ss; assert(subsequence(ss,ss2) == -1); zipper(ss,ss2,ss); } int main() { test(); cout << "Passed all tests" << endl; }

3. Consider this program:

   #include "Sequence.h" // class template from problem 2 class Coord { public: Coord(int r, int c) : m_row(r), m_col(c) {} Coord() : m_row(0), m_col(0) {} double r() const { return m_row; } double c() const { return m_col; } private: double m_row; double m_col; }; int main() { Sequence<int> si; si.insert(50); // OK Sequence<Coord> sc; sc.insert(0, Coord(50,20)); // OK sc.insert(Coord(40,10)); // error! }

   Explain in a sentence or two why the call to the one-argument form of Sequence<Coord>::insert causes at least one compilation error. (Notice that the call to the one-argument form of Sequence<int>::insert is fine, as is the call to the two-argument form of Sequence<Coord>::insert.) Don't just transcribe a compiler error message; your answer must indicate you understand the ultimate root cause of the problem and why that is connected to the call to Sequence<Coord>::insert.

4. This problem will appear later

5. This problem will appear later

6. This problem will appear later

Turn it in

By Monday, March 3, there will be a link on the class webpage that will enable you to turn in this homework. Turn in one zip file that contains your solutions to the homework problems. The zip file must contain eight files:

• oddlist.cpp, a C++ source file with your solution to problem 1a.
• oddvector.cpp, a C++ source file with your solution to problem 1b.
• badlist.cpp, a C++ source file with your solution to problem 1c.
• badvector.cpp, a C++ source file with your solution to problem 1d.
• Sequence.h, a C++ header file with your declaration and implementation of the class and function templates for problem 2.
• a file to be named later
• a file to be named later
• hw.docx or hw.txt, a Word document or a text file with your solutions to problems 1e, 3, and some other problems to be named later.

In each source file you turn in, do not comment out your implementation; you want our test scripts to see it!