36
Implementation Details
❐We also need to keep track of how
many numbers are in the bag.
An array of integers
844
We don’t care what’s in
this part of the array.
An integer to keep
track of the bag’s size
3
[ 0 ] [1] [ 2 ] [ 3 ] [ 4 ] [ 5 ] . . .
37
An Exercise
Use these ideas to write a
list of private member
variables could implement
the Bag class. You should
have two member
38
An Exercise
class Bag
{
public:
…
private:
int data[20];
size_t count;
};
One solution:
39
An Exercise
A more flexible solution:
class Bag
{
public:
static const size_t CAPACITY = 20;
…
private:
int data[CAPACITY];
size_t count;
};
40
An Example of Calling Insert
void Bag::insert(int new_entry)
Before calling insert, we
might have this bag b:
2
[ 0 ] [ 1 ] [2] . . .
84
b.data
b.count
41
An Example of Calling Insert
void Bag::insert(int new_entry)
b.data
b.count
We make a function call
b.insert(17)
What values will be in
b.data and b.count
after the member
function finishes ?
2
[ 0 ] [ 1 ] [2] . . .
84
void Bag::insert(int new_entry)
42
An Example of Calling Insert
void Bag::insert(int new_entry)
After calling b.insert(17),
we will have this bag b:
3
[ 0 ] [1] [ 2 ] . . .
84
17
void Bag::insert(int new_entry)
b.data
b.count 2
[ 0 ] [ 1 ] [2] . . .
84
43
Pseudocode for Bag::insert
➊assert(size( ) < CAPACITY);
➋Place new_entry in the appropriate location
of the data array.
➌Add one to the member variable count.
What is the “appropriate
location” of the data array ?
44
Pseudocode for Bag::insert
➊assert(size( ) < CAPACITY);
➋Place new_entry in the appropriate location
of the data array.
➌Add one to the member variable count.
data[count] = new_entry;
count++;
45
write ++count instead.
Pseudocode for Bag::insert
➊assert(size( ) < CAPACITY);
➋Place new_entry in the appropriate location
of the data array.
➌Add one to the member variable count.
data[ count++] = new_entry;
46
The Other Bag Operations
❐Read Section 3.1 for the implementations of
the other bag member functions.
❐Remember: If you are just using the Bag
class, then you don’t need to know how the
operations are implemented.
❐Later we will reimplement the bag using
more efficient algorithms.
❐We’ll also have a few other operations to
manipulate bags.
47
Here’s one last question for you to think about. Of course, the answer
is that there is very little difference between a bag of integers and a bag
of any other type.
Other Kinds of Bags
❐In this example, we have implemented a bag
containing integers.
❐But we could have had a bag of float
numbers, a bag of characters, a bag of
strings . . .
Suppose you wanted one of these other
bags. How much would you need to change
in the implementation ?
Section 3.1 gives a simple solution using
the C++ typedef statement.
48
❐A container class is a class that can hold a
collection of items.
❐Container classes can be implemented with a C++
class.
❐The class is implemented with a header file
(containing documentation and the class
definition) and an implementation file (containing
the implementations of the member functions).
❐Other details are given in Section 3.1, which you
should read.
Summary
49
Presentation copyright 1997, Addison Wesley Longman
For use with
Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch.