Time due: 11:00 PM Tuesday, March 4
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.
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.
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.
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.
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.
#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.
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;
}
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.
This problem will appear later
This problem will appear later
This problem will appear later
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.
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!