C++代写:CSE232 Multi-Set

实现Multi-Set的Data Structure,和普通的Set不同的是,Multi-Set允许多次存储相同的值。

The Problem

We are going to work on making our own template container class using dynamically allocated memory. We are going to build a MSet class, a multi-set that allows multiple copies of the same element by keeping track of elements as a value:count pair

Some Background

A typical set, such as a C++ set, allows only one copy of an element to be stored. However, in a multiset, you can store multiple copies of an element. The typical approach is to store an element in the set that has two fields: a value and a count. Every time the same element is inserted into the multiset, the count associated with the value goes up by 1.

We are going to implement our own class, called MSet and implement that class using dynamic memory.

We will try to keep it simple in terms of operations.

We really need two classes to address this problem

  • a SetElement struct, which is the payload that carries the value and count for each entry
  • an MSet class

In particular, you cannot use an STL container inside of your class. Memory has to be dynamically allocated and deleted.

Skeleton on hackerrank

I thought it a bit much to struggle through templates and dynamic memory at once without some help. So I have provided some of the information you need in the hackerrank problem. This file will not compile as is! Everywhere you see a comment with the phrase FIX IT (in caps) is a place where you have to modify the file to make it work. Each function/method is declared.

SetElement

SetElement is a good example of needing a struct, not a class. A SetElement exists to carry information on its value and count, that’s about it.

  • public data member element of template type V
  • public data member cnt of type int
  • SetElement(V v); o constructor. Sets element to val, sets cnt to 1
  • overloaded function ostream &operator<<(ostream&, const SetElement& p),
    • print a SetElement.
    • doesn’t have to be a friend since the members are public, so just a regular function. It is just a templated function, doesn’t even show up in the struct definition.

MSet

A multiset class. It has dynamic memory that grows on demand. You manage the memory.

  • private data SetElement<V>* ary_ the contents of the MSet. This points to your array when you make it (and you have to make it).
  • private data size_t capacity_, the size the underlying array (dynamically allocated) can hold before it needs to grow.
  • private data size_t size_, the actual number of elements in the underlying array.
  • feel free to add anything else you think is important.

MSet Methods

The standard stuff from the rule-of-three. You should understand these already so not much other detail needed.

  • copy constructor
  • operator=
  • destructor
  • 3 constructors o MSet(size_t s=2). Default size of the array (the capacity of the initial memory ary_ points to) is 2
  • MSet(T val). Take a template T val and:
    • again, make ary_ point to an initial array of size 2
    • assign val to ary_[0].element and ary[0].cnt to 1
  • MSet(vector<T>& v). Take every element from the v and either insert that value or create an ary_ memory of size equal to v.size() and assign the elements
  • size_t size(). member function. Number of elements in the MSet.
  • size_t capacity(). member function. Present capacity of the MSet.
  • void grow(). This is a private member, not available outside of class methods. Its job is to:
    • double the capacity_ of the instance
    • make a pointer to new memory of twice the present size.
    • copy the contents previously in ary_ into the newly created array
    • swap the old pointer and new pointer
    • delete the old memory
  • SetElement<T>* find(T val). member function.
    • if val is found in the MSet, returns a pointer to the element
    • if val is not found, returns nullptr.
  • void insert(V value). member function.
    • If the value already exists in the array of SetElement elements:
      • change the cnt of element to be one larger o If the value does not yet exist in the array of SetElement
    • if the array has reached capacity
      • call the grow method thus double the underlying size
    • add a SetElement to the array with element = value and cnt = 1 size_t count(V value). member function. Returns count of how many times value occurs in the set. Could be 0.
  • bool erase(V value). member function.
    • If the value exists in the MSet array
      • if the cnt > 1, decrease the cnt by 1
      • If the cnt == 1, remove the array entry, shifting all elements above it in the array down one.
      • return true
    • If the value does not exist, return false;
  • ostream& operator<<(ostream &out, const MSet &m). This is a friend function (not a member).
    • It prints the underlying the size_ and capacity_ of the MSet, as well as the contents of the array of SetElement elements.
    • It should be fully defined in the header as indicated. Friends are a problem, do it in the header.
    • The format is very specific, so be careful. Look at the hackerrank page for details.
      • if the list is empty, prints “Empty”
      • if there is a list, each entry is printed with “, “ between but no comma at the end!

Deliverables

  • Turn in proj10.cpp
  • Don’t change the main! We will notice and you will get 0 for the project!
  • Save a copy to your H drive.

Notes

The hackerrank main is ridiculously detailed because testing your code without breaking it into pieces would be difficult. There are 7 test cases, each part of a switch statement. The first element of each test is its associated case in the switch statement. It should make it easier to work with.

Test

Implement your class and get it to run with the provided main.cpp.