Homework 7

Computer Architecture I ShanghaiTech University


In this assignment, you can finally code in C++ again. Topics covered are:

If you have any difficulties in C++ programming, please refer to Lab 9.


Download the following files: doubll.hpp and Makefile.


Your task is to implement a doubly linked list in C++ using templates. If in doubt its behaviour should be similar to the std::list. But of course the std::list is more complicated - we implement a simplified version. doubll.hpp defines all the classes needed and some of their data structures and methods. Other methods are left for you to declare. For templates, the program that is using them has to always include the implementation as well, because we cannot generate and link to a .o file because the code depends on the template parameter. To keep the code clean it is one convention to still only declare the classes and functions in a .hpp file while its implementation goes into a *-impl.hpp file which is included at the end of the .hpp file.

Implementation Details

Finish the implementation of the class and methods in doubll-impl.hpp. And you should obey the following rules:

List nodes

Similar to HW2, a list node has both pointers to its predecessor and successor. Most of the methods are implemented or generated by the compiler by default. You only need to implement two methods:
Constructor: __List_node_base ()
Default constructor. Use _Tp's default constructor to initialize the data. Set both pointers to nullptr.
Constructor: explicit __List_node_base ( const _Tp & v )
Initialize the node with a value. Set both pointers to nullptr. The reason to use explicit here is to prevent the compiler from doing the implicit conversion.


Finish the implementation of __detail::__List_iterator<_Tp>. Consider what data structure should be used in the iterator. You have to implement the following methods:
Constructor: __List_iterator ()
Default constructor.
Constructor: __List_iterator ( const __List_iterator & other )
Copy constructor.
Constructor: __List_iterator ( __List_node_base<_Tp> * node )
Initialize the iterator with a pointer to a node.
Destructor: ~__List_iterator ()
You should also overload the following operators: These operators should behave similarly to std::list<_Tp>::iterator.

Const Iterator

It is similar to the iterator except for the dereferenced value should be const type (they cannot be modified). All methods for iterator should also be implemented for const iterator. You should also implement one additional method:
Constructor: __List_const_iterator ( const __List_iterator & other )
Convert an iterator into a const iterator. Please notice that the reverse conversion (const iterator -> iterator) is not required and you should consider why.

Doubly Linked List

Finally, implement the doubly linked list. Implement the following methods:
Constructor: list ()
Default constructor.
Constructor: list ( size_type size, const _Tp& value )
Initialize the list with size copies of elements with value.
Destructor: ~list ()
Method: size_type size () const
Returns the size of the current list.
Method: iterator begin ()
Returns an iterator to the first element. If the list is empty, the returned iterator will be equal to end().
Method: iterator end ()
Returns an iterator to the element following the last element.
Method: const_iterator cbegin () const
Returns a const iterator to the first element. If the list is empty, the returned iterator will be equal to cend().
Method: const_iterator cend () const
Returns a const iterator to the element following the last element.
Method: iterator insert ( iterator pos, const _Tp& value )
Method: iterator insert ( const_iterator pos, const _Tp& value )
Inserts value before pos. Returns iterator pointing to the inserted value.
Method: iterator erase ( iterator pos )
Method: iterator erase ( const_iterator pos )
Removes the element at pos. Returns iterator following the last removed element. If the iterator pos refers to the last element, the end() iterator is returned.
Method: void reverse ()
Reverses the order of the elements in the list. No references or iterators become invalidated.
Please note that the copy and move constructors are removed in order to avoid memory issues like double free.



Submit doubll-impl.hpp to Autolab.