Goals
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.
Setup
Download the following files: doubll.hpp and Makefile.
Overview
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:
- No standard libraries are allowed to use. Specifically, no #include statements are allowed to appear in doubll-impl.hpp.
- We assume type _Tp has default constructor and destructor, and it is both copy constructible and assignable.
- The number of comments should be at least 25% of the non-blank lines. The TA's will check by hand if those comments are valid and in English - failure to comply may lead to a score of 0 for this HW. You can use this Python script, which is the same as that on Autolab, to check your comments.
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.
Iterator
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 ()
- Destructor.
You should also overload the following operators:
- =: copy assignment operator.
- *: dereference operator.
- ->: arrow operator.
- ==, !=: comparison operator.
- ++, --: self increment and decrement operator.
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 ()
- Destructor.
- 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.
Hints
- You might encounter cases that require you to cast a const pointer into a normal pointer. The direct conversion is not allowed in C++, you should consider const_cast.
- You can refer to the GNU C++ Library's implementation. In GNU/Linux, the header file for std::list is placed at /usr/include/c++/<GCC version>/.
- Because the compiler will not generate any code if the templates are not used, so it won't complain about errors exist in methods you do not use. It is strongly suggested that you test all your methods before submission. One easy approach is to specialize your templates and compile it.
Submission
Submit doubll-impl.hpp to Autolab.