Chapter 3 Problem 5 A bag can contain more than one copy of an item. For example

Question

Chapter 3 Problem 5

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 copies 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, instead of the bag’s count function, you’ll want a constant 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 point, an efficient implementation is not needed. For example, just adding a new item to a set will take lin- ear time because you’ll need to check that the new item isn’t already present. Later we’ll explore more efficient implementations (including the implementation of set in the C++ Standard Library). You may also want to add additional operations to your set class, such as an operator for subtraction.

It looks like other people have posted similar questions, none really work.

Explanation / Answer

The Bag implementation Code
#include "bag.h"

#include <iostream>

Bag::Bag()    // Constructor
{
   // set the initial state of the bag
   count=0;
}

void Bag::clear() // Clear the bag
{
   count=0;
}

bool Bag::insert(bag_type value) //Place a value in Bag
{
   bool reply;
   if(count <20 ) {
      data[count]=value;
      reply=true;
      count++;
   } else {
      reply=false;
   }
   return reply;
}

bool Bag::inbag(bag_type value) // Is a value in the bag?
{
   bool reply=false;
   int index;
   for(index=0;index<count&& !reply;index++)
      if(data[index] == value) reply=true;
   return reply;
}

int Bag::howmany(bag_type value) //How many of element;
{
   int thismany=0;
   int index;
   for(index=0;index<count;index++)
      if(data[index]==value) thismany++;
   return thismany;
}

bool Bag::remove(bag_type value) // Remove a value
{
   bool reply=false;
   int index;
   if(howmany(value) == 0) return reply;
   reply=true;
   index=0;
   while(data[index] != value) index++;
   for(;index<count;index++)
      data[index]=data[index+1];
   count--;
}

int Bag::size()    // How many elements in bag?
{
   return count;
}
Driver to test the Bag
#include <iostream>
#include <cstdlib>
#include "bag.h"

using namespace std;

int main(int argc, char *argv[])
{
Bag b;
bag_type value;

cout << "Bag" << endl;
b.insert(4);
do {
     value=rand()%6 +1;
} while(b.insert(value));
cout << b.size()<< " elements in the bag" << endl;
cout << b.howmany(4) << " fours " << endl;
b.remove(4);
cout << b.size()<< " elements in the bag" << endl;
cout << b.howmany(4) << " fours " << endl;
cout << b.howmany(5) << " fives " << endl;
while(b.inbag(5)) b.remove(5);
cout << b.howmany(5) << " fives " << endl;

system("Pause");
return 0;
}

Test Run
Bag
20 elements in the bag
3 fours
19 elements in the bag
2 fours
4 fives
0 fives
Press any key to continue . . .

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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