CSCI 362 — Lab 3

List: a std::list class

Due: June 10, 2019 @ 6:00PM

Handout

Grab the handout tarfile from here: http://cs.millersville.edu/~wkillian/2019/summer/files/csci362/lab3-list.tar

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 really care or 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".

  1. I recommend solving the pieces in the order I have them listed
  2. I am giving you a comprehensive unit test autograder as part of the handout
  3. 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>
class List
{
  struct Node {
    ...

    // removes [first,last] and updates links
    static void unhook (Node* first, Node* last) noexcept;

    // hooks [first,last] before this
    void hook (Node* first, Node* last) noexcept;
  };

  // transfers [first,last) from their list to pos' list (inserting before pos)
  static void transfer (const_iterator pos, const_iterator first, const_iterator last) noexcept;

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

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

  // default constructor
  List();

  // range constructor
  template <typename ForwardIter>
  List (ForwardIter, ForwardIter);

  // size-value constructor
  List (size_type, T const&);

  // destructor
  ~List();

  // copy assignment
  List& operator= (List const&);

  // intializer_list assign()
  void assign (std::initializer_list<T>);

  // begin and end iterators
  iterator        begin()  noexcept;
  const_iterator  begin()  noexcept const;
  iterator        end()    noexcept;
  const_iterator  end()    noexcept const;

  // front and back accessors
  reference       front();
  const_reference front()  const;
  reference       back();
  const_reference back()   const;

  // insertion routines -- const reference
  iterator insert (const_iterator, T const&);
  void     push_back (T const&);
  void     push_front (T const&);

  // insertion routines -- r-value reference
  iterator insert (const_iterator, T&&);
  void     push_back (T&&);
  void     push_front (T&&);

  // erase single value
  iterator erase (const_iterator);
  // erase range
  iterator erase (const_iterator, const_iterator);

  // removes all elements from the list
  void     clear();

  // resize with default value
  void     resize (size_type);
  // resize with const reference
  void     resize (size_type, T const&);

};

Implementation Details

I recommend working on the functions in the following order. I've also included how many points each part is worth

[4] static Node::unhook (Node* first, Node* last)
    [2] When first == last (single element)
    [2] When first != last
[4] Node::hook (Node* first, Node* last)
    [2] When first != last
    [2] When first == last (single element)
[5] static List::transfer(ConstIterator pos, ConstIterator first, ConstIterator last)
    [1] when first == last (no-op)
    [2] when distance(first, last) == 1 (single element)
    [2] when distance(first, last) >> 1 (many elements)
[1] Iterator& Iterator::operator++()
[1] Iterator Iterator::operator++(int)
[1] Iterator& Iterator::operator--()
[1] Iterator Iterator::operator--(int)
[1] friend bool Iterator::operator==(Iterator const&, Iterator const&)
[1] ConstIterator& ConstIterator::operator++()
[1] ConstIterator ConstIterator::operator++(int)
[1] ConstIterator& ConstIterator::operator--()
[1] ConstIterator ConstIterator::operator--(int)
[1] friend bool ConstIterator::operator==(ConstIterator const&, ConstIterator const&)
[1] iterator       List::begin()
[1] const_iterator List::begin() const
[1] iterator       List::end()
[1] const_iterator List::end() const
[1] List::List()
[3] List::List(InputIter, InputIter)
    [1] when distance(first, last) == 0
    [2] when distance(first, last)  > 0
[1] reference       List::front()
[1] const_reference List::front() const
[1] reference       List::back()
[1] const_reference List::back() const
[3] iterator List::insert (const_iterator, T const&)
[2] void List::push_back (T const&)
[2] void List::push_front (T const&)
[3] iterator List::insert (const_iterator, T&&)
[2] void List::push_back (T&&)
[2] void List::push_front (T&&)
[3] List::List(size_type, T const&)
[3] List::~List()
[6] List& List::operator=(List const&)
[2] void List::assign(std::initializer_list<T>)
[6] iterator List::erase (const_iterator)
[8] iterator List::erase (const_iterator, const_iterator)
[5] void List::clear()
[4] void List::resize (size_type)
[4] void List::resize (size_type, T const&)

Running the autograder

Invoking make should create the autograder. If it says autograder up to date then you can type rm autograder and re-run make

There can be a lot of output shown from the autograder. Some of it could be overwhelming at times. I recommend adding a couple of arguments to the autograder to help ease the pain.

./autograder -a

Will run the autograder and stop as soon as the first FAILURE is found

./autograder -t

Will list all of the tags for each of the tests. If you want to run a specific subset of tags you can do so by stating the following:

./autograder [access],[iterator]

Will run all tests that have the access and iterator tags

Style

Use good programming style:

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.