C++ question For dynamic bag, implement the operators -= and – for the class. Th

Question

C++ question

For dynamic bag, implement the operators -= and – for the class.

These operators compute the difference between two bags. In summary b1-b2 results in a bag that has the elements of b1 with the elements of b2 removed.

o For example, if b1 has eight 4’s in it and b2 has five 4’s in it then b1-b2 has three 4’s in it.

If b2 has more of an element than b1, it is not an error. The difference simply ends up with none of that element.

o For example, if b1 has five 4’s in it and b2 has eight 4’s in it then b1-b2 has no 4’s in it.

Implement -= as a member function and - as a non-member function (similar to += and +).

Here are the two headers from bag2.h:
o void operator -=(const bag &subtrahend);
o bag operator-(const bag & b1, const bag & b2);

o The program bag_diff3.cpp provide a basic check of the two new operators.

bag2.h file

#ifndef MAIN_SAVITCH_BAG2_H
#define MAIN_SAVITCH_BAG2_H
#include // Provides size_t
#include

namespace main_savitch_4
{
class bag
{
public:
// TYPEDEFS and MEMBER CONSTANTS
typedef int value_type;
typedef std::size_t size_type;
static const size_type 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);
       void operator -=(const bag& subtrahend);
// 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 dynamic 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);
   bag operator -(const bag& b1, const bag& b2);
}

#endif

bag2.cpp file

#include // Provides copy function
#include // Provides assert function
#include "bag2.h"
using namespace std;

namespace main_savitch_4
{
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 we are using.

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

   // First, set index to the location of target in the data array,
   // which could be as small as 0 or as large as used-1.
   // If target is not in the array, then index will be set equal to used.
   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;

   // When execution reaches here, target is in the bag at data[index].
   // So, reduce used by 1 and copy the last item onto data[index].
   --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:
   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;
   }

   // Copy the data from the source array:
   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;
}

}

bag_diff3.cpp file

#include "bag2.h"
#include

using namespace std;
using namespace main_savitch_4;

int main() {
int size = 5;
// how many of each value to put in each bag
// one 0 will be put in b1
// two 1's will be put in b1
// five 0's will be in b2 ...
int num1[] = {1, 2, 3, 4, 5};
int num2[] = {5, 4, 3, 2, 1};
bag b1;
bag b2;
// insert data into bags
for(int i = 0; i < size; i++ ) {
for(int j = 0; j < num1[i]; j++) {
b1.insert(i);
}
for(int j = 0; j < num2[i]; j++ ) {
b2.insert(i);
}
}
for(int i = 0; i < size; i++ ) {
if(num1[i] != b1.count(i)) {
cout << "value " << i << " has bad count in b1: "
<< b1.count(i) << " rather than " << num1[i] << endl;
}
if(num2[i] != b2.count(i)) {
cout << "value " << i << " has bad count in b2: "
<< b2.count(i) << " rather than " << num2[i] << endl;
}
}
bag b3 = b1 - b2;
for(int i = 0; i < size; i++ ) {
int d = num1[i] - num2[i];
d = (d >= 0) ? d : 0;
if(b3.count(i) != d) {
cout << "value " << i << " has bad count in b3: "
<< b3.count(i) << " rather than " << d << endl;
}
}

b1 -= b1;
for(int i = 0; i < size; i++ ) {
if(0 != b1.count(i)) {
cout << "value " << i << " has bad count in b1: "
<< b1.count(i) << " rather than " << 0 << endl;
}
}

cout << "no news is good news!" << endl;
}

Explanation / Answer

void bag::operator -=(const bag& diffend)
// Library facilities used: algorithm
{
for (int i = 0; i < diffend.used; i++) {
erase_one(diffend.data[i]);
}
}

bag operator -(const bag& b1, const bag& b2)
{
return (b1 -= b2);
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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