| A bag can contain more than one copy of an item. For example, the chapter desc

Question

| A bag can contain more than one copy of an item. For example, the chapter describes a bag that contains the number 4 and two cop ies of the number 8. This bag behavior is different from a set, which can contain only a single copy of any given item. Write a new container class called set, which is similar to a bag, except that a set can contain only one copy of any given item. You'll need to change the interface a bit. For example, in- stead of the bag's count function, you'll want a con- stant member function such as this: bool set::contains (const value_type& target) const; // Postcondition: The return value is true if // target is in the set,; otherwise the return // value is false. Make an explicit statement of the invariant of the set class. Do a time analysis for each operation. At this

Explanation / Answer

I have added the code for the same.working c++ code:

#ifndef MAIN_SAVITCH_BAG2_H
#define MAIN_SAVITCH_BAG2_H
#include <cstdlib> // Provides size_t

namespace main_savitch_4
{
    class bag
    {
    public:
      // TYPEDEFS and MEMBER CONSTANTS
   // * For VC++ 6.0 use size_t instead of std::size_t.
   // * Define CAPACITY using an enum instead of a static member

typedef int value_type;
        typedef size_t size_type;
        enum { DEFAULT_CAPACITY = 30 };
        // CONSTRUCTORS and DESTRUCTOR
        bag(size_type initial_capacity = DEFAULT_CAPACITY);
        bag(const bag& source);
        ~bag( );
        // MODIFICATION MEMBER FUNCTIONS
        void reserve(size_type new_capacity);
        bool erase_one(const value_type& target);
      size_type erase(const value_type& target);
        void insert(const value_type& entry);
        void operator +=(const bag& addend);
        void operator =(const bag& source);
        // CONSTANT MEMBER FUNCTIONS
        size_type size( ) const { return used; }
        size_type count(const value_type& target) const;
    private:
        value_type *data;     // Pointer to partially filled array
        size_type used;       // How much of array is being used
        size_type capacity;   // Current capacity of the bag
    };

    // NONMEMBER FUNCTIONS for the bag class
    bag operator +(const bag& b1, const bag& b2);
}

#endif
// CLASS implemented: bag (see bag2.h for documentation)
// INVARIANT for the bag class:
//   1. The number of items in the bag is in the member variable used;
//   2. The actual items are stored in a partially filled
//      dynamic array pointed to by member variable "data";
//   3. The size of the dynamic array is in member variable "capacity".

#include <algorithm>     // Provides copy function
#include <cassert>       // Provides assert function
#include "bag2.h"
using namespace std;

namespace main_savitch_4
{
    // (Omitted for VC++ 6.0) const bag::size_type bag::DEFAULT_CAPACITY;

    bag::bag(size_type initial_capacity)
    {
        data = new value_type[initial_capacity];
        capacity = initial_capacity;
        used = 0;
    }

    bag::bag(const bag& source)
    // Library facilities used: algorithm
    {
        data = new value_type[source.capacity];
        capacity = source.capacity;
        used = source.used;
        copy(source.data, source.data + used, data);
    }

    bag::~bag( )
    {
   delete [ ] data;
    }

    void bag::reserve(size_type new_capacity)
    // Library facilities used: algorithm
    {
        value_type *larger_array;

        if (new_capacity == capacity)
            return; // The allocated memory is already the right size.

        if (new_capacity < used)
            new_capacity = used; // Can’t allocate less than needed.

        larger_array = new value_type[new_capacity];
        copy(data, data + used, larger_array);
        delete [ ] data;
        data = larger_array;
        capacity = new_capacity;
    }
  
    bag::size_type bag::erase(const value_type& target)
    {
   size_type index = 0;
   size_type many_removed = 0;

   while (index < used)
   {
        if (data[index] == target)
        {
       --used;
       data[index] = data[used];
       ++many_removed;
        }
        else
       ++index;
   }

   return many_removed;
    }

    bool bag::erase_one(const value_type& target)
    {
   size_type index; // The location of target in the data array  
   index = 0;
   while ((index < used) && (data[index] != target))
        ++index;

   if (index == used) // target isn't in the bag, so no work to do
        return false;

   --used;
   data[index] = data[used];
   return true;
    }

    void bag::insert(const value_type& entry)
    {
        if (used == capacity)
            reserve(used+1);
        data[used] = entry;
        ++used;
    }
  
    void bag::operator +=(const bag& addend)
    // Library facilities used: algorithm
    {
        if (used + addend.used > capacity)
            reserve(used + addend.used);
      
        copy(addend.data, addend.data + addend.used, data + used);
   used += addend.used;
    }

    void bag::operator =(const bag& source)
    // Library facilities used: algorithm
    {
   value_type *new_data;

   // Check for possible self-assignment:
// this is a pointer to the object which activated this function
    // when this = address of parameter they are the same object
// so stop
   if (this == &source)
            return;

   // If needed, allocate an array with a different size:
   if (capacity != source.capacity)
   {
        new_data = new value_type[source.capacity];
        delete [ ] data;
        data = new_data;
        capacity = source.capacity;
   }

   used = source.used;
   copy(source.data, source.data + used, data);
    }

    bag::size_type bag::count(const value_type& target) const
    {
   size_type answer;
   size_type i;

   answer = 0;
   for (i = 0; i < used; ++i)
        if (target == data[i])
       ++answer;
   return answer;
    }

    bag operator +(const bag& b1, const bag& b2)
    {
   bag answer(b1.size( ) + b2.size( ));

   answer += b1;
   answer += b2;
   return answer;
    }

}
//bagclassapp.cpp

#include <iostream>     // Provides cout and cin
#include <cstdlib>      // Provides EXIT_SUCCESS
#include "bag2.h"       // With Item defined as an int
using namespace std;
using namespace main_savitch_4;

void get_ages(bag& ages);
void check_ages(bag& ages);

int main( )
{
    bag ages;

    get_ages(ages);
    check_ages(ages);
    cout << "May your family live long and prosper." << endl;
    return EXIT_SUCCESS;
}

void get_ages(bag& ages)
{
    int user_input; // An age from the user's family

    cout << "Type the ages in your family. ";
    cout << "Type a negative number when you are done:" << endl;
    cin >> user_input;
    while (user_input >= 0)
    {
        ages.insert(user_input);
        cin >> user_input;
    }
}

void check_ages(bag& ages)
{
    int user_input; // An age from the user's family

    cout << "Type those ages again. Press return after each age:"
        << endl;
    while (ages.size( ) > 0)
    {
        cin >> user_input;
        if (ages.erase_one(user_input))
            cout << "Yes, I've got that age and have removed it."
              << endl;
        else
            cout << "No, that age does not occur!" << endl;
    }
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.