Bag ADT using Dynamic Array – 1

We shall look at implementing the Bag ADT using a dynamic array as the underlying data structure. This improves upon our previous implementation using static array.

By using a dynamic array, we do not suffer under the constraint of having a fixed capacity which may not be exceeded. We can dynamically allocated more memory from the heap as and when needed.

——

We first give the class definition of the Bag class. We postpone the function implementations to future posts.

——

//implementing BAG ADT using dynamic array.

#ifndef BAG2_H

#define BAG2_H

class Bag

{

public:

typedef int Item; //our Bag contains items of type Item.

static const int DEFAULT_CAP = 30;

Bag ( size_t initial_cap = DEFAULT_CAP); //parameterized constructor, which can also
// act as default constructor.

Bag (const Bag& other_bag); //copy constructor — needed since we use dynamic //memory in class.

//MODIFICATION MEMBER FUNCTIONS

void operator = (const Bag& other_bag); //overloaded assignment operator — needed //since we use dynamic memory in class.

void insert (const Item& entry);

bool remove (const Item& target);

void operator += (const Bag& addend);

friend Bag operator + (const Bag& b1, const Bag& b2); //implements Bag union.

 

//CONSTANT MEMBER FUNCTIONS

size_t size ( ) const { return used; }

size_t occurrences ( const Item& target) const;//returns how many times target appears //in the bag.

void print_bag ( ) const;

 

private:

Item *data; //our dynamic array.

size_t used; //how much of the “data” array is currently being used.

size_t capacity; //what is the current capacity of the “data” array.

};

//Non-member function.

Bag operator + (const Bag& b1, const Bag& b2);

#endif

———-

Invariant of the Bag ADT:

– Items are stored in the dynamic array, data.

– If no Items are currently stored, used = 0.

– If some number of Items are currently stored, they are stored in the indices 0 through used-1.

– We do not care what is stored in the “data” array from index “used” through “capacity-1”.

– The current size of the data array is given by “capacity”.

Now that we have the class definition with us, we can go on to see the implementations of these functions in the coming posts.

——–



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: