CS2134 Homework 6 Solved

Written Part:

1.   Draw the conceptual representation for our implementation of a link list (include the header) containinga 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;

(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;

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;

}

}