6
\$\begingroup\$

For my third assignment in CS2, I was given the following:

A set is a special bag that does not allow duplicates. Specify each operation for a set of objects by stating its purpose, by describing its parameters, and by writing preconditions, postconditions, and a pseudocode version of its header. Then write a C++ interface for the set. Include javadoc-style comments in your code.

The difference of two bags is a new bag containing the entries that would be left in one bag after removing those entries that also occur in the second set. Design and specify a method difference() for the ADT bag that returns as a new bag the difference of the bag receiving the call to the method and the bag that is the method's one argument. Include sufficient comments to fully specify the method.

Not too much to say, looking for a more efficient way to implement this perhaps. Feel free to rip it apart!


SetInterface.h:

#ifndef SET_INTERFACE
#define SET_INTERFACE

#include <vector>

/** @class BagInterface BagInterface.h "BagInterface.h"
 *
 *  Definition of BagInterface class template. */
template <typename ItemType>
class SetInterface 
{
public:

  /** Virtual destructor. */
  virtual ~SetInterface() {}

  /** Gets the current number of entries in this set.
   *  @return The integer number of entries currently in the set. 
   */
  virtual int size() const = 0;

  /** Gets the maximum number of items allowed in a set
   *  @return The integer number of maximum items allowed in a set
   */
  virtual int getCapacity() const = 0;

  /** Sets the maximum number of items allowed in a set
   *  @post The capacity memeber of the Set instance will be set to 
   *        whatever number was passed in
   *  @param num The maximum number of items that can be stored in a set
   */
  virtual void setCapacity(int) = 0;

  /** Sees whether this set is empty.
   *
   *  @return True if the set is empty, or false if not. 
   */
  virtual bool isEmpty() const = 0;

  /** Adds a new entry to this set.
   *
   *  @post If successful, newEntry is stored in the set and the
   *        count of items in the set has increased by 1.
   *
   *  @param newEntry The object to be added as a new entry.
   *
   *  @return True if addition was successful, or false if not. 
   */
  virtual bool add(const ItemType&) = 0;

  /** Removes one occurrence of a given entry from this set, if
   *  possible.
   *
   *  @post If successful, anEntry has been removed from the set and
   *        the count of items in the set has decreased by 1.
   *
   *  @param anEntry The value of the entry to be removed.
   *
   *  @return True if removal was successful, or false if not. 
   */
  virtual bool remove(const ItemType&) = 0;

  /** Removes all entries from this set.
   *
   *  @post This set contains no items (thus the count is 0). 
   */
  virtual void clear() = 0;

  /** Counts the number of times a given entry appears in set.
   *
   *  @param anEntry The value of the entry to be counted.
   *
   *  @return The number of times anEntry appears in this set. 
   */
  virtual int count(const ItemType&) const = 0;

  /** Tests whether this set contains a given entry.
   *
   *  @param anEntry The value of the entry to locate.
   *
   *  @return True if this set contains anEntry, or false
   *          otherwise. 
   */
  virtual bool contains(const ItemType&) const = 0;

  /** Converts this set into a vector.
   *
   *  @return A vector containing all the entries in this set. 
   */
  virtual std::vector<ItemType> toVector() const = 0;
};

#endif

Set.cpp:

template <typename ItemType>
Set<ItemType>::Set() : itemCount(0), capacity(DEFAULT_CAPACITY) {}

template <typename ItemType>
int Set<ItemType>::size() const 
{
  return itemCount;
}

template <typename ItemType>
int Set<ItemType>::getCapacity() const 
{
  return capacity;
}

template <typename ItemType>
void Set<ItemType>::setCapacity(int num)
{
  capacity = num;
}

template <typename ItemType>
ItemType* Set<ItemType>::getItems()
{
  return items;
}

template <typename ItemType>
bool Set<ItemType>::isEmpty() const {

  return itemCount == 0;
}

template <typename ItemType>
bool Set<ItemType>::add(const ItemType& newEntry) 
{
  int location = -1;
  if (itemCount < capacity) 
  {
      for(int i = 0; i < capacity; ++i)
      {
      if(items[i] == newEntry) return false;
      if(location == -1 && items[i] == ItemType{}) location = i; 
      }
      items[location] = newEntry;
      ++itemCount;
      return true;
  }
  return false;
}

template <typename ItemType>
bool Set<ItemType>::remove(const ItemType& anEntry) {

  int locatedIndex = getIndexOf(anEntry);
  bool canRemoveItem = !isEmpty() && locatedIndex > -1;

  if (canRemoveItem) {
    --itemCount;
    items[locatedIndex] = items[itemCount];
  }

  return canRemoveItem;
}

template <typename ItemType>
void Set<ItemType>::clear() {

  itemCount = 0;
}

template <typename ItemType>
bool Set<ItemType>::contains(const ItemType& anEntry) const {

  bool found = false;
  int curIndex = 0;

  while (!found && curIndex < itemCount) {
    if (anEntry == items[curIndex]) {
      found = true;
    }
    ++curIndex;
  }

  return found;
}

template <typename ItemType>
int Set<ItemType>::count(const ItemType& anEntry) const {

  int frequency = 0;
  int curIndex = 0;

  while (curIndex < itemCount) {
    if (items[curIndex] == anEntry) {
      ++frequency;
    }
    ++curIndex;
  }

  return frequency;
}

template <typename ItemType>
Set<ItemType> Set<ItemType>::difference(Set<ItemType> &set) const
{
  Set<ItemType> newSet;
  ItemType *items1 = set.getItems();
  for(int i = 0; i < size(); ++i)
  {
      for(int j = 0; j < set.size(); ++j)
      {
      if (items[i] == items1[j]) break;
      if (j == set.size() - 1) newSet.add(items[i]);
      }
  }
  return newSet;
}

template <typename ItemType>
std::vector<ItemType> Set<ItemType>::toVector() const {

  std::vector<ItemType> setContents;

  for (int i = 0; i < itemCount; ++i) {
    setContents.push_back(items[i]);
  }

  return setContents;
}

template <typename ItemType>
int Set<ItemType>::getIndexOf(const ItemType& target) const {

  bool found = false;
  int result = -1;
  int searchIndex = 0;

  while (!found && searchIndex < itemCount) {
    if (items[searchIndex] == target) {
      found = true;
      result = searchIndex;
    }
    else {
      ++searchIndex;
    }
  }

  return result;
}

Set.h:

#ifndef SET_ADT
#define SET_ADT

#include "SetInterface.h"

/** @class Set Set.h "Set.h"
 *
 *  Specification of an array-based ADT set. */
template <typename ItemType>
class Set : public SetInterface<ItemType>
{
 private:
  /** Maximum capacity of this bag. */
  static const int DEFAULT_CAPACITY = 6;

  /** Number of items in this bag. */
  int itemCount;

  /** Maximum capacity of this bag. */
  int capacity;

  /** Data storage. */
  ItemType items[DEFAULT_CAPACITY];

  /** Gets the index of target in the array 'items' in this bag.
   *
   * @param target The ItemType value to retrieve the index of.
   *
   * @return The index of the element in the array 'items' that
   *         contains 'target' or -1 if the array does not contain
   *         'target'. */
  int getIndexOf(const ItemType& target) const;

public:
  /** Default constructor. */
  Set();

  int size() const;

  int getCapacity() const;

  void setCapacity(int);

  ItemType* getItems();

  bool isEmpty() const;

  bool add(const ItemType&);

  bool remove(const ItemType&);

  void clear();

  int count(const ItemType&) const;

  bool contains(const ItemType&) const;

  Set<ItemType> difference(Set<ItemType>&) const;

  std::vector<ItemType> toVector() const;
};

#include "Set.cpp"

#endif

main.cpp:

/** @file main.cpp
 *
 *  @course CS1521
 *  @section 1
 *
 *  Testing the Set class.
 */

#include <cassert>
#include <iostream>
#include <string>
#include <cstdlib>
#include "Set.h"

void displaySet(Set<std::string>& set) 
{    
    std::cout << "The set contains " << set.size() << " items:" << std::endl;

    std::vector<std::string> setItems = set.toVector();  
    int numberOfEntries = (int)setItems.size();

    for (int i = 0; i < numberOfEntries; ++i) 
    {
      std::cout << setItems[i] << " ";
    }  
    std::cout << std::endl;
}

void setTester(Set<std::string>& set)
{
    assert(1 == set.isEmpty());
    displaySet(set);

    std::string items[] = {"one", "two", "three", "four", "five", "one"};

    std::cout << "Adding 6 items to the set" << std::endl;
    for (int i = 0; i < set.getCapacity(); ++i) 
    {
        set.add(items[i]);
    }
    displaySet(set);

    std::cout << "Now running tests on the set!" << std::endl;
    assert(0 == set.isEmpty());
    assert(5 == set.size());
    assert(6 == set.getCapacity());
    assert(0 == set.add("one"));
    assert(1 == set.add("more"));
    assert(0 == set.add("extra"));
    displaySet(set);

    std::cout << "Testing differences of sets, with set 2 containing \"one\"" << std::endl;
    Set<std::string> set2;
    set2.add("one");
    Set<std::string> diff = set.difference(set2);
    displaySet(diff);

    assert(6 == set.size());
    assert(6 == set.getCapacity());
    assert(1 == set.contains("three"));
    assert(0 == set.contains("ten"));
    assert(1 == set.count("one"));
    assert(1 == set.remove("one"));
    assert(0 == set.count("one"));
    assert(0 == set.remove("one"));
    assert(0 == set.count("one"));

    std::cout << "After clearing the set: " << std::endl;

    set.clear();
    displaySet(set);
    assert(1 == set.isEmpty());
    assert(0 == set.contains("two"));
}

int main() 
{    
    Set<std::string> set;

    std::cout << "Testing Set:" << std::endl;
    setTester(set);    
    std::cout << "All done!" << std::endl;
}
\$\endgroup\$
5
\$\begingroup\$

Overall design:

SetInterface is unnecessary. Defining an interface just for the sake of hiding private data & methods might be popular in Java and such languages that rely heavily on dynamic dispatch, but not so much in C++.

Your interface makes the code a lot more complicated, from a maintenance standpoint, and spread-out through at least three files. It will also add a virtual table to your class, which has a performance impact and increases the size of the compiled binary. My advice it to just throw away SetInterface and keep a simple and straightforward Set<T> template class.

Other details:

  • Your main header comment is outdated:

    /** @class BagInterface BagInterface.h "BagInterface.h"  
     *  
     * Definition of BagInterface class template. */
    

    You are not calling you class/header-file BagInterface.

  • I'd suggest to keep parameter names in function/method prototypes, as this adds to the documentation of the code.

  • Template parameter name for types is by convention just T, though ItemType is also quite descriptive.

  • toVector() can be optimized to avoid vector reallocations by simply declaring the vector with itemCount size:

    std::vector<ItemType> setContents(itemCount); // <-- Allocate storage just once
    for (int i = 0; i < itemCount; ++i) 
    {
        setContents.push_back(items[i]);
    }
    

    However, you can also construct the vector from a range, so that loop can actually be consolidated into a single line:

    std::vector<ItemType> setContents(items, items + itemCount);
    
  • Take a look at the Rule of Three. This rule is basically about how your class is going to behave regarding copy via operator = and copy constructors. You might wish to provide custom ones or even completely disallow copy and/or assignment.

\$\endgroup\$
4
\$\begingroup\$
  • count method looks out of place. If it returns anything but 0 or 1 then the main invariant of the set is broken. Could be handy for debugging, but definitely not to be exposed to an end user.

  • setCapacity implementation seems naive. As implemented, capacity could become smaller than the size. Kind of unexpected.

  • Performance wise, insertions and removals are linear by the set size; difference is quadratic. I recommend tree-based implementation (AVL or RB would be wonderful).

  • Additional constructors (from vector, from range, from initializer list) are usually very handy.

\$\endgroup\$
2
\$\begingroup\$

Bugs

  • I noticed a few bugs in your current implementation. The first is in your difference() method. You need to check if j <= set.size() in order for it to work properly. Also, you had some jenky spacing issues going on with some of your code, but we'll just say that wasn't your fault and was your text-editors fault.

    template <typename ItemType>
    Set<ItemType> Set<ItemType>::difference(Set<ItemType> &set) const
    {
      Set<ItemType> newSet;
      ItemType *items1 = set.getItems();
      for(int i = 0; i < size(); ++i)
      {
          for(int j = 0; j <= set.size(); ++j)
          {
              if (items[i] == items1[j]) break;
              if (j == set.size()) newSet.add(items[i]);
          }
      }
      return newSet;
    }
    
  • Your 'clear()' method doesn't actually clear anything. It's kinda useless really... here's how you should be clearing the items:

    template <typename ItemType>
    void Set<ItemType>::clear() 
    {
        for(int i = 0; i < capacity; ++i)
        {
            items[i] = ItemType{};
        }
        itemCount = 0;
    }
    

Style

  • You're consistency could do with a bit of work: in some places you have the opening brace on the same line as the function definition, on other places you put it on its own separate line. You need to choose some style and stick on it!

  • You have a lot of unnecessary spacing between your function prototypes in Set.h, IMO. You could do without those spaces.

  • Me being a more visual person, I don't like how you are testing out your Set class. I think it would be better for you to display the contents of the original Set, the contents of the Set you will be using to show off your difference() method, and the Set that gets returned from the difference() method. Here is such a method:

    void displaySetDifference(Set<ItemType> set1, Set<ItemType> set2, Set<ItemType> diff) 
    {    
        std::vector<ItemType> set1Items = set1.toVector();  
        std::vector<ItemType> set2Items = set2.toVector();
        std::vector<ItemType> diffItems = diff.toVector();
        std::cout << "Set 1: [ ";
        for (int i = 0; i < set1Items.size(); ++i) 
        {
            std::cout << set1Items[i] << " ";
        }
        std::cout << " ]" << std::endl << "Set 2: [ ";
        for (int i = 0; i < set2Items.size(); ++i)
        {
          std::cout << set2Items[i] << " ";
        }
        std::cout << " ]" << std::endl << "Difference: [ ";
        for (int i = 0; i < diff.size(); ++i)
        {
          std::cout << diffItems[i] << " ";
        }
        std::cout << " ]" << std::endl;
    }
    

    Now does this function maybe violate some DRY principals? Yeah, probably. But you are going to either have to have the duplication within this function, or within the function that you call this from if you were to DRY it up a bit. But I though this was the better approach, so I just went with it. Now look at your pretty output that you can have!

    Set differences with set 2 containing "one":
    Set 1: [ one two three four five  ]
    Set 2: [ one  ]
    Difference: [ two three four five  ]
    

    Much easier to see how your code is working now!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.