CSCI 362: List – a std::list class

Handout

Grab the handout tarfile from Autolab

Overview

I have given you a somewhat incomplete implementation of List. List is almost exactly like std::list but with a few minor differences we won’t worry about. You are tasked with implementing several member functions.

This is not a small file! I’m giving you 500+ lines of code and you’ll be adding to it. It’s easy to become overwhelmed — so I’m providing you a “path toward success”.

Things to remember:

• A ListNode contains a T value, ListNode* prev, and ListNode* next
• A ListIterator contains a single ListNode* (m_nodePtr)
• A ListConstIterator contains a single ListNode* (m_nodePtr)
• A List contains a single ListNode (m_header) and a size_t (m_size)
• I recommend solving the pieces in the order I have them listed below Required Functions
• If you are ever unsure of the behavior of List, you can always write code and compare it to what happens when you use std::list

Required Functions

template <typename T>
struct ListNode {
  ...
  
  // removes [first,last] and updates links
  static void unhook_range (ListNode* first, ListNode* last) noexcept;
  
  // hooks [first,last] before this
  void hook_range (ListNode* first, ListNode* last) noexcept;
};

struct ListIterator {
  ...
  // postincrement
  ListIterator operator++(int) noexcept;
  // predecrement
  ListIterator& operator--() noexcept;
  // comparison
  friend bool operator!=(Iterator const&, ListIterator const&) noexcept;
};

struct ListConstIterator {
  ...
  // preincrement
  ListConstIterator& operator++() noexcept;
  // postdecrement
  ListConstIterator operator--(int) noexcept;
  // comparison
  friend bool operator==(ListConstIterator const&, ListConstIterator const&) noexcept;
};

template <typename T>
class List
{
  // transfers [first,last) from their list to pos' list (inserting before pos)
  static void transfer (iterator pos, iterator first, iterator last) noexcept;

  
  // default constructor
  List();
  
  // size-value constructor
  List (size_type, T const&);
  
  // range constructor
  template <typename ForwardIter>
  List (ForwardIter, ForwardIter);
  
  // destructor
  ~List();

  // copy assignment
  List& operator= (List const&);
  
  // begin and end iterators
  iterator        begin()  noexcept;
  const_iterator  begin()  noexcept const;
  iterator        end()    noexcept;
  const_iterator  end()    noexcept const;
  
  // insertion routines
  iterator insert (iterator, T const&);
  void     push_back (T const&);
  void     push_front (T const&);
  
  // front and back accessors
  reference       front();
  const_reference front()  const;
  reference       back();
  const_reference back()   const;
  
  // erase routines
  iterator erase (iterator);
  iterator erase (iterator, iterator);
  void     clear();
  void     pop_back();
  void     pop_front();
  
  // resize routines
  void     resize (size_type, T const&);

  // reverse the list in linear time; no new allocations
  void     reverse();
};

Implementation Details

I recommend working on the functions in the following order. I’ve also included how many points each part is worth. Autolab will test your functions in this order.

// node insertion/removal

[5] static Node::unhook_range (Node* first, Node* last)
    [3] When first == last (single element)
    [2] When first != last

[5] Node::hook_range (Node* first, Node* last)
    [3] When first != last
    [2] When first == last (single element)


// iterator methods

[2] ListIterator    ListIterator::operator++(int)
[2] ListIterator&   ListIterator::operator--()
[2] friend bool     ListIterator::operator!=(ListIterator const&, ListIterator const&)

[2] ListConstIterator& ListConstIterator::operator++()
[2] ListConstIterator  ListConstIterator::operator--(int)
[2] friend bool        ListConstIterator::operator==(ListConstIterator const&, ListConstIterator const&)


// list transfer

[4] static List::transfer(ListIterator pos, ListIterator first, ListIterator last)
    [1] when first == last (no-op)
    [1] when distance(first, last) == 1 (single element)
    [2] when distance(first, last) >> 1 (many elements)


// iterator accessors

[1] iterator       List::begin()
[1] const_iterator List::begin() const
[1] iterator       List::end()
[1] const_iterator List::end() const


// default constructor

[5] List::List()


// operations which (can) add elements

[4] iterator List::insert (iterator, const T&)
[2] void     List::push_back (const T&)
[2] void     List::push_front (const T&)

[5] List::List(size_type, const T& = T())
    [1] when size == 0
    [4] when size > 0

[5] List::List(InputIter, InputIter)
    [1] when distance(first, last) == 0
    [4] when distance(first, last)  > 0


// data accessors

[1] reference       List::front()
[1] const_reference List::front() const
[1] reference       List::back()
[1] const_reference List::back() const


// operations which (can) remove elements

[4] iterator List::erase (iterator)
[2] void pop_back()
[2] void pop_front()

[5] iterator List::erase (iterator, iterator)
    [1] when distance == 0
    [4] when distance > 0
[5] void List::clear()
[5] List::~List()


// operations which can add or remove elements

[5] List::operator= (const List&)

[5] void List::resize (size_type, const T& = T())
    [2] when newSize > size
    [2] when newSize < size
    [1] when newSize == size


// extra credit

[+5] void reverse()

Style

Use good programming style:

• Write comments where appropriate
• Remember to include a comment block at the top of your program that includes:
  • Your name
  • The course
  • The last date of modification
  • The assignment name
  • A brief description of what your program does
• FORMAT YOUR CODE CONSISTENTLY

Submission

Please submit List.hpp to autolab

Grading

This lab is graded out of 100 points. You could earn up to 105 points on this assignment.

• [90pts] Unit tests for List
• [10pts] Clean and clear formatting/style points
• [+5pts] Extra Credit for reverse()
• NOTE: if your program does not compile/run, the highest score you will earn will be a 10/100