| A bag can contain more than one copy of an item. For example, the chapter desc
ID: 3665291 • Letter: #
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 thisExplanation / Answer
Answer
// FILE: set2.h
// CLASS PROVIDED: set(a container class for a collection of items)
// TYPEDEFS and MEMBER CONSTANTS for the set class:
// void operator +=(const set& addend)
// Postcondition: Each item in addend has been added to this set.
//
#ifndef MAIN_SAVITCH_SET2 _H
#define MAIN_SAVITCH_SET2 _H
#include <cstdlib> // Provides size_t
namespace main_savitch_4
{
class set
{
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
set(size_type initial_capacity = DEFAULT_CAPACITY);
set(const bag& source);
~set ( );
// MODIFICATION MEMBER FUNCTIONS
void insert(const value_type& entry);
// 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 set
};
// NONMEMBER FUNCTIONS for the set class
set operator +(const set& s1, const set& s2);
}
#endif
// FILE: set2.cxx
// CLASS implemented: set(see set2.h for documentation)
// INVARIANT for the set class:
// 1. The number of items in the set is in the member variable used;
// 2. The actual items of the set are stored in a partially filled array.
// The array is a dynamic array, pointed to by the member variable data;
// 3. The size of the dynamic array is in the member variable capacity.
#include <algorithm> // Provides copy function
#include <cassert> // Provides assert function
#include "set2.h"
using namespace std;
namespace main_savitch_4
{
const set::size_type set::DEFAULT_CAPACITY;
set::set(size_type initial_capacity)
{
data = new value_type[initial_capacity];
capacity = initial_capacity;
used = 0;
}
set::set(const set& source)
// Library facilities used: algorithm
{
data = new value_type[source.capacity];
capacity = source.capacity;
used = source.used;
copy(source.data, source.data + used, data);
}
set::~set( )
{
delete [ ] data;
}
void set::insert(const value_type& entry)
{
if (used == capacity)
reserve(used+1);
data[used] = entry;
++used;
}
set operator +(const set& b1, const set& b2)
{
set answer(s1.size( ) + s2.size( ));
answer += s1;
answer += s2;
return answer;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.