CS2134 HOMEWORK 6

CS2134 HOMEWORK 6

Be sure to include your name at the beginning of the file! Assignment 6 includes only a typed portion which
should consist of a single file (hw06written) in a .pdf format. Be sure to include your name at the beginning of
each file! You must hand in the file via NYU Classes.
Written Part:
1. Draw the conceptual representation for our implementation of a link list (include the header) containing
a single item A.
2. For each of the following, determine if the code compiles.
vector<int A = {1,2,3,4,5};
vector<int::iterator vItr1;
vector<int::iterator vItr2;
list<int C = {1, 2,3,4,5};
list<int::iterator lItr1;
list<int::iterator lItr2;
(a)
vItr1 = A.begin( );
vItr2 = A.end( );
cout << vItr1 + (vItr1 + vItr2)/2;
(b) lItr1 = C.begin( );
lItr2 = find(C.begin(), C.end(), 3);
if ( lItr1 < lItr2 )
cout << " 2 is not the first item ";
3. For each of the following, determine if the iterator is valid.
vector<int A = {1,2,3,4,5};
vector<int B;
vector<int::iterator vItr;
list<int C = {1, 2,3,4,5};
list<int D;
list<int::iterator lItr;
1
(a) B = A;
vItr = B.begin();
B.erase(B.begin()+1);
(b) B = A;
vItr = B.begin()+2;
B.erase(B.begin()+1);
(c) D = C;
lItr = C.begin();
C.erase(++C.begin());
(d) D = C;
lItr = ++D.begin();
++lItr
D.erase(++D.begin());
4. Which of the following code snippets are valid? If the code snippet is invalid, state why.
(a) list<int l;
list<int::iterator lIter;
l.push_back(200);
lIter = l.begin();
for (int i = 1; i < 100; ++i)
l.push_front(i);
for (int i = 1; i < 100; ++i)
l.push_back(-i);
cout << *lIter << endl;
(b) list<int l;
list<int::iterator lIter1;
list<int::iterator lIter2;
list<int::iterator mid;
for (int i = 0; i < 100; ++i)
l.push_back(i);
lIter1 = l.begin();
lIter2 = l.end();
mid = lIter1 + (lIter2 - lIter1)/2;
cout << *mid << endl;
(c) vector<int v;
vector<int::iterator vIter1;
vector<int::iterator vIter2;
vector<int::iterator mid;
for (int i = 0; i < 100; ++i)
v.push_back(i);
vIter1 = v.begin();
vIter2 = v.end();
mid = vIter1 + (vIter2 - vIter1)/2;
cout << *mid << endl;
2
5. For the List class, what if the following code for the method remove was used. Would it work correctly?
Explain.
void remove( const Object & x )
{
Node * prev = header-next;
while ( prev != nullptr )
{
if ( prev-next-data == x )
erase_after( iterator(prev) );
else
prev = prev-next;
}
}
3