#ifndef LIST_H #define LIST_H #include <algorithm> using namespace std; template

Question

#ifndef LIST_H
#define LIST_H

#include <algorithm>
using namespace std;

template <typename Object>
class List
{
private:   
// The basic doubly linked list node.
// Nested inside of List, can be public
// because the Node is itself private
struct Node
{
//Add code to define Node.
};

public:
class const_iterator
{
//Add code to define const_iterator class
};

class iterator : public const_iterator
{
//Add code to define iterator class
};

public:
List( )
{ //Add code for the constructor to initialize a empty list.
}

~List( )
{
//Add code to clean up the List.
}

List( const List & rhs )
{
//Add code for the constructor to initialize a list with values.
}

List( List && rhs )
: theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }
{
//Add code.
}

List & operator= ( const List & rhs )
{
//Add code
}

List & operator= ( List && rhs )
{   
//Add code
}
  
// Return iterator representing beginning of list.
// Mutator version is first, then accessor version.
iterator begin( )
{ return iterator( head->next ); }

const_iterator begin( ) const
{ return const_iterator( head->next ); }

// Return iterator representing endmarker of list.
// Mutator version is first, then accessor version.
iterator end( )
{ return iterator( tail ); }

const_iterator end( ) const
{ return const_iterator( tail ); }

// Return number of elements currently in the list.
int size( ) const
{ return theSize; }

// Return true if the list is empty, false otherwise.
bool empty( ) const
{ return size( ) == 0; }

void clear( )
{
while( !empty( ) )
pop_front( );
}

// front, back, push_front, push_back, pop_front, and pop_back
// are the basic double-ended queue operations.
Object & front( )
{ return *begin( ); }

const Object & front( ) const
{ return *begin( ); }

Object & back( )
{ return *--end( ); }

const Object & back( ) const
{ return *--end( ); }

void push_front( const Object & x )
{ insert( begin( ), x ); }

void push_back( const Object & x )
{ insert( end( ), x ); }

void push_front( Object && x )
{ insert( begin( ), std::move( x ) ); }

void push_back( Object && x )
{ insert( end( ), std::move( x ) ); }

void pop_front( )
{ erase( begin( ) ); }

void pop_back( )
{ erase( --end( ) ); }

// Insert x before itr.
iterator insert( iterator itr, const Object & x )
{
//add code.
}

// Insert x before itr.
iterator insert( iterator itr, Object && x )
{
//Add code.
}
  
// Erase item at itr.
iterator erase( iterator itr )
{
//Add code.
}

iterator erase( iterator from, iterator to )
{
for( iterator itr = from; itr != to; )
itr = erase( itr );

return to;
}

private:
int theSize;
Node *head;
Node *tail;

void init( )
{
//Add code here to define the function to initialize list.
}
};

#endif

Try to complete the code in List.h to make main.cpp work. It's simply trying to generate a list, and show the list.

Here is the instruction:

1. Insert the following code to define Node in List class:

Object data;

Node *prev;

Node *next;

Node( const Object & d = Object{ }, Node * p = nullptr, Node * n = nullptr )

: data{ d }, prev{ p }, next{ n } { }

Node( Object && d, Node * p = nullptr, Node * n = nullptr )

: data{ std::move( d ) }, prev{ p }, next{ n } { }

2. Define the Nested const_iterator class for List class:

public:

// Public constructor for const_iterator.

const_iterator( ) : current{ nullptr }

{ }

// Return the object stored at the current position.

// For const_iterator, this is an accessor with a

// const reference return type.

const Object & operator* ( ) const

{ return retrieve( ); }

const_iterator & operator++ ( )

{

current = current->next;

return *this;

}

const_iterator operator++ ( int )

{

const_iterator old = *this;

++( *this );

return old;

}

const_iterator & operator-- ( )

{

current = current->prev;

return *this;

}

const_iterator operator-- ( int )

{

const_iterator old = *this;

--( *this );

return old;

}

bool operator== ( const const_iterator & rhs ) const

{ return current == rhs.current; }

bool operator!= ( const const_iterator & rhs ) const

{ return !( *this == rhs ); }

protected:

Node *current;

// Protected helper in const_iterator that returns the object

// stored at the current position. Can be called by all

// three versions of operator* without any type conversions.

Object & retrieve( ) const

{ return current->data; }

// Protected constructor for const_iterator.

// Expects a pointer that represents the current position.

const_iterator( Node *p ) : current{ p }

{ }

friend class List<Object>;

3. Define the Nested iterator class for List class

public:

// Public constructor for iterator.

// Calls the base-class constructor.

// Must be provided because the private constructor

// is written; otherwise zero-parameter constructor

// would be disabled.

iterator( )

{ }

Object & operator* ( )

{ return const_iterator::retrieve( ); }

// Return the object stored at the current position.

// For iterator, there is an accessor with a

// const reference return type and a mutator with

// a reference return type. The accessor is shown first.

const Object & operator* ( ) const

{ return const_iterator::operator*( ); }

iterator & operator++ ( )

{

this->current = this->current->next;

return *this;

}

iterator operator++ ( int )

{

iterator old = *this;

++( *this );

return old;

}

iterator & operator-- ( )

{

this->current = this->current->prev;

return *this;

}

iterator operator-- ( int )

{

iterator old = *this;

--( *this );

return old;

}

protected:

// Protected constructor for iterator.

// Expects the current position.

iterator( Node *p ) : const_iterator{ p }

{ }

friend class List<Object>;

4. Define init() function:

theSize = 0;

head = new Node;

tail = new Node;

head->next = tail;

tail->prev = head;

5. Add code to constructor List() to generate an empty list:

init();

6. Add code to constructor List( const List & rhs ) to initialize a list with values.

init( );

for( auto & x : rhs )

push_back( x );

7. Add code to constructor List( List & rhs ) to initialize an empty list.

rhs.theSize = 0;

rhs.head = nullptr;

rhs.tail = nullptr;

8. Add code to destructor ~List():

clear( );

delete head;

delete tail;

9. Add code for operator =

List & operator= ( const List & rhs )

List copy = rhs;

std::swap( *this, copy );

return *this;

List & operator= ( List && rhs )

std::swap( theSize, rhs.theSize );

std::swap( head, rhs.head );

std::swap( tail, rhs.tail );

return *this;

10. Use the following code to complete insert functions:

iterator insert( iterator itr, const Object & x )

Node *p = itr.current;

++theSize;

return iterator( p->prev = p->prev->next = new Node{ x, p->prev, p } );

iterator insert( iterator itr, Object && x )

Node *p = itr.current;

++theSize;

return iterator( p->prev = p->prev->next = new Node{ std::move( x ), p->prev, p } );

11. Add code to erase a node:

iterator erase( iterator itr )

Node *p = itr.current;

iterator retVal( p->next );

p->prev->next = p->next;

p->next->prev = p->prev;

delete p;

--theSize;

return retVal;

iterator erase( iterator from, iterator to )

for( iterator itr = from; itr != to; )

itr = erase( itr );

Explanation / Answer

#ifndef list_h #define list_h #include #include using namespace std; template class List { private: struct Node { /* See Figure 3.13 */ Object data; Node *prev; Node *next; Node( const Object & d = Object( ), Node *p = NULL, Node *n = NULL ) : data( d ), prev( p ), next( n ) { } }; public: class const_iterator { public: const_iterator( ) : current( NULL ) { } const Object & operator* ( ) const { return this->retrieve( ); } const_iterator & operator++ ( ) { current = current->next; return *this; } const_iterator operator++ ( int ) { const_iterator old = *this; ++( *this ); return old; } bool operator== ( const const_iterator & rhs ) const { return current == rhs.current; } bool operator!= ( const const_iterator & rhs ) const { return !( *this == rhs ); } protected: Node *current; Object & retrieve( ) const { return current->data; } const_iterator( Node *p ) : current( p ) { } friend class List; }; class iterator : public const_iterator { public: iterator( ) { } Object & operator* ( ) { return this->retrieve( ); } const Object & operator* ( ) const { return const_iterator::operator*( ); } iterator & operator++ ( ) { this->current = this->current->next; return *this; } iterator operator++ ( int ) { iterator old = *this; ++( *this ); return old; } protected: iterator( Node *p ) : const_iterator( p ) { } friend class List; }; public: List() { init( ); } ~List( ) { clear( ); delete head; delete tail; } List( const List & rhs ) { init( ); *this = rhs; } const List & operator= ( const List & rhs ) { if( this == &rhs ) return *this; clear( ); for( const_iterator itr = rhs.begin( ); itr != rhs.end( ); ++itr ) push_back( *itr ); return *this; } void init( ) { theSize = 0; head = new Node; tail = new Node; head->next = tail; tail->prev = head; } iterator begin() { return iterator( head->next); } const_iterator begin() const { return const_iterator( head->next); } iterator end() { return iterator(tail); } const_iterator end() const { return const_iterator(tail); } int size() const { return theSize; } bool empty() const { return size() == 0; } void clear() { while (!empty()) pop_front(); } Object & front( ) { return *begin( ); } const Object & front( ) const { return *begin( ); } Object & back( ) { return *--end( ); } const Object & back( ) const { return *--end( ); } void push_front( const Object & x ) { insert( begin( ), x ); } void push_back( const Object & x ) { insert( end( ), x ); } void pop_front( ) { erase( begin( ) ); } void pop_back( ) { erase( --end( ) ); } iterator insert( iterator itr, const Object & x ) { Node *p = itr.current; theSize++; return iterator( p->prev = p->prev->next = new Node( x, p->prev, p ) ); } iterator erase( iterator itr ) { Node *p = itr.current; iterator retVal( p->next ); p->prev->next = p->next; p->next->prev = p->prev; delete p; theSize--; return retVal; } iterator erase( iterator from, iterator to ) { for( iterator itr = from; itr != to; ) itr = erase( itr ); return to; } private: int theSize; Node *head; Node *tail; /* This should either be private or public but not both. void init( ) { } */ }; #endif

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.