CS2134 Homework Assignment 3

CS2134 Homework Assignment 3

Assignment 3 include a programming portion and a written portion. The programming portion
must compile and consist of a single file ( hw03.cpp), and the written portion should consist of a
single file (hw03written) in a .pdf format. Be sure to include your name at the beginning of each
file! You must hand in both files via NYU Classes.
Programming Part:
1. Write a function template called print if that:
• takes three parameters: two iterators start, end, and a functor pred
start and end have the capabilities of a forward iterator, and refer to a range
[start,end) in a container
pred is a functor that takes an element in the range [start,end) as an arguement
and returns a bool
• prints1 all items in the range [start,end) which evaluates to true
• runs in O(n) time where n is the number of items in the range [start,end)
The signature of your function template is:
template< class Itr, class UnaryPred
void print_if( Itr start, Itr end, UnaryPred pred )
A small amount of extra credit will be given for figuring out how to add your own test case
to the unit test for this assignment.
∗A bonus of %5 percent will be given if you turn in this homework assignment by Tues. Sept 27 at 11:00 p.m.
1Print each item on its own line
1
Written Part
1. For the vector class, and for the following code2
snippet:
vector<int c { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
vector<int::iterator itr1 = c.begin()+2;
vector<int::iterator itr2 = c.begin()+4;
vector<int::iterator itr3 = c.begin()+8;
cout << *(c.begin( ) + ( c.end( ) - c.begin( ) )/2 ) << endl;
c.erase(itr2);
cout << *itr1 << endl;
cout << *itr2 << endl;
cout << *itr3 << endl;
cout << *(c.begin( ) + ( c.end( ) - c.begin( ) )/2 ) << endl;
What is printed? Explain your answer.3
2. Using big-Oh notation, give the worst case run time for the method print if, which you
implemented programming problem 1.
3. Given the following code snippet:
vector<int a {1,2,3,4, ..., n}; // vector, a, has n items
vector<int::iterator itrStart;
vector<int::iterator itrMid;
vector<int::iterator itrEnd;
Assign values to the iterators, itrStart, itrMid, itrEnd, so that:
(a) [itrStart, itrMid) refers to the range 1,2, 3, ..., n/2
(b) [itrMid, itrEnd) refers to the range n/2+1,n/2+2, ..., n
4. For each code snippet below state either why the code won’t compile/run, or state what is
printed by the code snippet.
(a) vector<int a {1, 2, 3, 4, 5};
vector<int::iterator itra = a.begin();
cout << *(itra + 3);
(b) list<int b {1, 2, 3, 4, 5};
list<int::iterator itrb = b.begin();
cout << *(itrb + 3);
2Remember c.end() - c.begin() returns the number of items in the range [ c.begin(), c.end() )
3Hint: think of how you implemented the erase method in the Vector class.
2
(c) list<int c {1, 2, 3, 4, 5};
list<int::iterator itrc = c.end();
itrc--;
cout << *(itrc);
(d) vector<int d {1, 2, 3, 4, 5};
vector<char::iterator itrd = d.begin();
cout << *(itrd + 3);
3