CSCI 362 — Lab 6

UnorderedSet and UnorderedMultiSet: Unordered Associative Containers implemented with HashTable

Due: June 28, 2019 @ 11:59PM

Handout

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

Overview

I've given you a mostly complete implementations of UnorderedSet and UnorderedMultiset. These are pretty similar to std::unordered_set and std::unordered_multiset; however, we do not handle certain types of insertions or accessors.

The assignment is split into three files:

• HashTable.hpp -- contains the HashTable class (along with its iterator class)
• UnorderedSet.hpp -- contains the UnorderedSet class
• UnorderedMultiSet.hpp -- contains the UnorderedMultiSet class

Like prior labs, it can be easy to get overwhelmed. But, if you work on one file at a time and complete the implementations of the functions in the specified order, you will make progress quickly!

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

New Functors for Hashing and Key Equality

Hash tables are supposed to be pretty generic. We should be able to store any form of data. This also means we should be able to provide a few customization points:

1. a user may want to use their own hash function
2. a user may want to use their own equality comparison function

The C++ standard library provides two reasonable defaults for us to use:

namespace std
{
  template <typename T>
  struct hash;

  template <typename T = void>
  struct equal_to;
}

UnorderedSet and UnorderedMultiSet use these by default; however, our HashTable is very generic:

template <typename Value, typename Hash, typename KeyEqual>
class HashTable
{
  ...

  Hash const&
  hash_function () const noexcept
  {
    return m_hash;
  }

  KeyEqual const&
  key_eq () const noexcept
  {
    return m_key_equal;
  }

private:
  ...
  Hash const m_hash;
  KeyEqual const m_key_equal;
  ...
};

• Hash and KeyEqual are function objects which are callable
• When you want to compute the hash for a value, you can say the following:

  size_t my_hash = hash_function() (my_awesome_value);

• When you want to check two values for equality, you can say the following:

  bool equal = key_eq() (value1, value2);

• This is similar to the last lab (priority queue)

Required functions

NOTE: solve in the listed order

Required Functions

Note: do not run the autograder until you've attempted the first 10 points

HashTable.hpp

template <typename Value, typename Hash, typename KeyEqual>
struct HashTableIterator {
  // [4] iterator equality
  friend bool operator== (HashTableIterator const&, HashTableIterator const&);
  // [4] iterator increment
  HashTableIterator& operator++();
};

template <typename Value, typename Hash, typename KeyEqual>
class HashTable {
  // [1] begin iterator
  iterator begin() const noexcept;

  // [1] end iterator
  iterator end() const noexcept;

  // [9] insertion of unique value (no duplicates allowed)
  //     NOTE: until rehash is implemented, only 6/9 will be earned
  std::pair<iterator, bool> insert_unique (Value const&);

  // [9] insertion of any value (duplicates allowed)
  iterator insert (Value const&);

  // [4] clear the hash table (so it's empty)
  void clear();

  // [5] search for a value in the hash table
  iterator find (Value const&);

  // [8] erase a single element
  iterator erase (iterator);

  // [9] rehash by changing the number of buckets
  void rehash (size_t);
};

UnorderedSet.hpp

template <typename Key, typename Hash, typename KeyEqual>
class UnorderedSet {

  // [4] range-insertion into UnorderedSet
  template <typename InputIt, Requires (concepts::ForwardIterator, InputIt)>
  void insert (InputIt, InputIt);

  // [4] range-erase from UnorderedSet
  iterator erase (const_iterator, const_iterator);
};

UnorderedMultiSet.hpp

template <typename Key, typename Hash, typename KeyEqual>
class UnorderedSet {

  // same as UnorderedSet -- not graded
  template <typename InputIt, Requires (concepts::ForwardIterator, InputIt)>
  void insert (InputIt, InputIt);

  // same as UnorderedSet -- not graded
  iterator erase (const_iterator, const_iterator);

  // [4] key-based erase -- returns the number of elements erased
  size_t erase(key_type const&);

  // [4] key-based find -- returns the number of elements that exist with specified key
  size_t find(key_type const&);

};

Running the autograder

Invoking make should create the autograder.

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

./autograder --failed

Will list all failed tests at the end of the autograder output

./autograder --passed

Will list all passed tests at the end of the autograder output

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

Since this consists of multiple files, a tarball will be required for submission.

invoking make handin should create handin.tar

Please submit handin.tar to autolab

Grading

This lab is graded out of 75 points.

• [70pts] Unit tests
• [5pts] Clean and clear formatting/style points
• NOTE: if your program does not compile/run, the highest score you will earn will be a 5/75