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

ID: 3663751 • Letter: A

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 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, in- stead 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 linear 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.

First, combine the two into one set by using + (union) operator, and print out the union set. The + operator must remove all duplicates and store one copy of any item. You also need to implement a subtraction operator (A-B means removing all elements of B from A) and print out the result. So the main function takes two sets of integers and print the result of + and - operation.

A sample input.dat may look like this. Note that we assume the input file includes only two sets of integer numbers, each number is separated by white spaces and sets are separated by a newline character. Note that you will probably have to use getline() <iostream> to get each line from the file and place it into a string, then stringstream <sstream> to parse the string into individual integers.

3 4 5 7 5 16 7 12 11 12 3 9 9 8 1 12

15 4 3 6 1 12 3 12 7 8 19 9 11 12 8 5 -4 -100

Assume that all inputs are integers and anything else should be rejected with an error message.

Include a run-time asymptotic analysis (Best, Average, Worst Case in terms of Big O) of main member functions in the readme file. You can write your readme file in html or pdf format.

here is the bag1.h

// FILE: bag1.h

// From Chapter 3 of Data Structures and Other Objects (Second Edition)

// ________________________________________________________________________//

// This file has been modified to work with Microsoft Visual C++ 6.0,// as described in www.cs.colorado.edu/~main/vc6.html

// ________________________________________________________________________//

// CLASS PROVIDED: bag (part of the namespace main_savitch_3)

// TYPEDEF and MEMBER CONSTANTS for the bag class:

// typedef ____ value_type

// bag::value_type is the data type of the items in the bag. It may be anyof

// the C++ built-in types (int, char, etc.), or a class with a default

// constructor, an assignment operator, and operators to

// test for equality (x == y) and non-equality (x != y).

// typedef ____ size_type

// bag::size_type is the data type of any variable that keeps track of howmany items

// are in a bag.

// static const size_type CAPACITY = _____

// bag::CAPACITY is the maximum number of items that a bag can hold.

// CONSTRUCTOR for the bag class:

// bag( )

// Postcondition: The bag has been initialized as an empty bag.

// MODIFICATION MEMBER FUNCTIONS for the bag class:

// size_type erase(const value_type& target);

// Postcondition: All copies of target have been removed from the bag.

// The return value is the number of copies removed (which could be zero).

// void erase_one(const value_type& target)

// Postcondition: If target was in the bag, then one copy has been removed;

// otherwise the bag is unchanged. A true return value indicates that one

// copy was removed; false indicates that nothing was removed.

// void insert(const value_type& entry)

// Precondition: size( ) < CAPACITY.

// Postcondition: A new copy of entry has been added to the bag.

// void operator +=(const bag& addend)

// Precondition: size( ) + addend.size( ) <= CAPACITY

.// Postcondition: Each item in addend has been added to this bag.

// CONSTANT MEMBER FUNCTIONS for the bag class:

// size_type size( ) const

// Postcondition: The return value is the total number of items in the bag.

// size_type count(const value_type& target) const

// Postcondition: The return value is number of times target is in the bag.

// NONMEMBER FUNCTIONS for the bag class:

// bag operator +(const bag& b1, const bag& b2)

// Precondition: b1.size( ) + b2.size( ) <= bag::CAPACITY.

// Postcondition: The bag returned is the union of b1 and b2.

// VALUE SEMANTICS for the bag class:

// Assignments and the copy constructor may be used with bag objects.

#ifndef MAIN_SAVITCH_BAG1_H#define MAIN_SAVITCH_BAG1_H#include <cstdlib> // Provides size_t
namespace main_savitch_3{ class bag { public: // TYPEDEFS and MEMBER CONSTANTS

// * For VC++ 6.0 we are using size_t instead of std::size_t. And we// * have defined CAPACITY using an enum instead of a static member// * constant. See www.cs.colorado.edu/~main/vc6.html for details.

typedef int value_type; typedef size_t size_type;enum { CAPACITY = 30 }; // CONSTRUCTOR bag( ) { used = 0; } // MODIFICATION MEMBER FUNCTIONS size_type erase(const value_type& target); bool erase_one(const value_type& target); void insert(const value_type& entry); void operator +=(const bag& addend); // CONSTANT MEMBER FUNCTIONS size_type size( ) const { return used; } size_type count(const value_type& target) const; private: value_type data[CAPACITY]; // The array to store items size_type used; // How much of array is used };
// NONMEMBER FUNCTIONS for the bag class bag operator +(const bag& b1, const bag& b2);}
#endif

here is bag1.cpp

Explanation / Answer

This will work :

try this :
The Bag Class Abstraction.
This bag will be our example of a container class. This is a class where each object can contain a collection of items (such as numbers). One of the important facets of a container class is that each object begins in a known configuration. In the case of a bag, we will count on each bag being initially empty. This is called the initial state of a bag.

We will use a fixed collection of operations to manipulate bags.
Insert a number in the bag.
One of the simplest operations that we permit is the action of inserting a new number into a bag.
Query a bag contents
We will have two Query methods. Is a number in the bag? How many copies of a number is in the bag?
Remove a number
The next operation is to remove a single number from the bag.
Remove all members from the bag.
Clear the bag.
Another operation allows us to find out how many numbers are in the bag, what is the size of the bag?

Bag Class implemetation.
The header file
//
#ifndef _BAG_
#define _BAG_

typedef int bag_type;

class Bag {

private:
int count; // members in bag
bag_type data[20]; // data store up to 20 members

public:
           Bag();             // Constructor
   bool    insert(bag_type); // Put a member in the bag
   bool    remove(bag_type); // remove a member from the bag
   int     size();            // number of members in bag
   void    clear();           // remove all members from bag
   bool    inbag(bag_type);   // is a member in the bag?
   int     howmany(bag_type); // how many member in bag.
};
#endif
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 . . .

Also summary of this bag containter class :

Container Classes

Bags

Initial State of a Bag

Inserting Numbers into a Bag

Examining a Bag

Removing a Number from a Bag

How Many Numbers

Summary of the Bag Operations

The Bag Class

The Bags Default Constructor

The Insert Function

The Size Function

The Occurrences Function

The Remove Function

Using the Bag in a Program

// Record the ages of three children:
ages.insert(4);
ages.insert(8);
ages.insert(4);

The Header File and Implementation File

Documentation for the Bag Class

The Bags Class Definition

The Implementation File

A Quiz
Suppose that a Mysterious Benefactor provides you with the Bag class, but you are only permitted to read the documentation in the header file. You cannot read the class definition or implementation file. Can you write a program that uses the Bag data type ?

Answer
Suppose that a Mysterious Benefactor provides you with the Bag class, but you are only permitted to read the documentation in the header file. You cannot read the class definition or implementation file. Can you write a program that uses the Bag data type ?

You know the name of the new data type, which is enough for you to declare Bag variables. You also know the headings and specifications of each of the operations.

Implementation Details

An Exercise

Use these ideas to write a list of private member variables could implement the Bag class. You should have two member variables. Make the bag capable of holding up to 20 integers.

An Example of Calling Insert

Pseudocode for Bag::insert

The Other Bag Operations

Other Kinds of Bags

Try this as well :

Navigate

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

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

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

Question

Explanation / Answer

Related Questions

Navigate