Often we will have a class with a data member of a container type. Of course, containers come in two overall flavors: strings and vectors. Let's look at each in turn.
When we have a data member of a class which is a string, we have to think about using that member as a whole thing -- we'll rarely need to alter individual characters of that string. For instance, a chemical element has a name:
class Element
{
string name;
// ...
};
Among other data... It is unlikely that the programmer using this class will need to change characters in the name for any reason. More likely, they'll need to have or change the whole name at once. So, our accessor/mutator pair for this member will look like this:
class Element
{
string name;
// ...
public:
Element(void);
Element(const string & n, /* ... */);
string get_name(void) const;
void set_name(const string & n);
// ...
};
Here we are using a string return type to give them a copy of the Element's name member:
string Element::get_name(void) const
{
return name;
}
For mutation, we accept their new name for us (by constant reference) and copy it in:
void Element::set_name(const string & n)
{
name = n;
return;
}
We don't need to give them any further facilities since even if they did want to alter a single character of the name somehow, they could simply access it, alter that char, then mutate it.
Constructing is similar. The default constructor will either leave the name empty:
Element::Element(void) : name(), // init other members here
{
}
Calling name's default constructor directly like this is unusual -- in fact it wouldn't work on a normal variable declaration/initialization -- but works for this situation just dandy. If it really bothers you, you can be more explicit by doing:
Element::Element(void) : name(""), // init other members here
{
}
But that won't work too well when we get to vector members below...
Or, it might put in some non-sense value so the programmer will remember to initialize things properly next time (or so the programmer can more easily track logic errors...):
Element::Element(void) : name("Your_Programmer_Is_An_Idiot!"),
// init other members here
{
}
I don't even call the mutator since there is no error/validity checking to do for a string member. the maximum declared size. I could use the mutator, though, if I didn't mind the compiler warnings:
Element::Element(void) : // init other members here
{
set_name("Your_Programmer_Is_An_Idiot!");
}
And constructing from an initial value will work similarly, but have a value given by the caller:
Element::Element(const string & n, /* ... */) : name(n), // ...
{
}
You can also do the mutator thing if you don't mind the warnings...
When a class has a vector member, most programmers using the class will need access to individual elements. This Grader class, for instance, has a vector that collects the user's scores on assignments in a particular category (test, quiz, project, etc.) and can then calculate the average:
class Grader
{
vector<double> scores;
// ...
public:
typedef typename vector<double>::size_type GrdPos;
Grader(void);
double get_score(GrdPos which) const;
bool set_score(GrdPos which, double to);
bool add_score(double new_score);
double average(void) const;
GrdPos get_count(void) const { return scores.size(); }
void reset(void) { scores.clear(); return; }
// ...
};
This looks quite a bit more complicated! A vector is rarely used in its entirety and so we need to access individual elements of the vector for access and mutation. This class has decided to do that via integral-type positions (distances from the beginning of the vector). Note the typedef to make referring to size_type for a vector of doubles simpler by naming it GrdPos (for grade position).
Constructing this class should take care to ensure the vector is empty:
Grader::Grader(void) : scores(), // other members here
{
}
Note that to do this, we don't need to fill in the vector with any elements or anything -- just default construct it (which we know will be an empty vector). This alone tells us that there is nothing in the vector!
The accessor and mutator add a new argument to tell us which score the caller wants to access/mutate. We must validate this index before allowing them to retrieve/change that position:
double Grader::get_score(GrdPos which) const
{
return which >= 0 && which < scores.size()
? scores[which] : -1.0;
}
bool Grader::set_score(GrdPos which, double to)
{
bool changed = false;
if (which >= 0 && which < scores.size())
{
changed = true;
scores[which] = to;
}
else if (which == scores.size())
{
changed = add_score(to);
}
return changed;
}
Here we are returning a (presumed) invalid score of negative one when they provide an illegal position. We also only allow them to alter positions which currently exist. But, to be nice, if they are trying to modify what would be the next position, we try to let them add that score to the collection. So, how do we get new scores in the collection in the first place? Like this:
bool Grader::add_score(double new_score)
{
bool added = false;
if (scores.size() != scores.max_size())
{
added = true;
scores.push_back(new_score);
}
return added;
}
If we haven't yet filled the vector, we add the new score to the end of the collection. Note how the max_size() function is called to determine the maximum size this vector can be (maximum number of elements it can store). This is unlikely to ever fail, but it's better to be safe than sorry...
Finally, let's take the average of the elements (just because):
double Grader::average(void) const
{
double sum = 0.0;
for (GrdPos s = 0; s != scores.size(); s++)
{
sum += scores[s];
}
return scores.size() == 0 ? sum : sum/scores.size();
}
Also note that the programmer using this class is allowed to retrieve the current count of scores stored and to reset the collection to empty.
Let's say a programmer needed to store information about chemical elements and then wanted to print only the names of the elements. Let's say, for sake of argument that there are only 3 elements to be stored. This fragment might do what we want:
string name;
Element one, two, three;
cout << "Enter your three elements: ";
one.input();
two.input();
three.input();
cout << "Your element names were:\n";
name = one.get_name();
cout << '\t' << name << '\n';
name = two.get_name();
cout << '\t' << name << '\n';
name = three.get_name();
cout << '\t' << name << '\n';
Or, they could also skip the local string object and simply print the get_name() result directly:
Element one, two, three;
cout << "Enter your three elements: ";
one.input();
two.input();
three.input();
cout << "Your element names were:\n";
cout << '\t' << one.get_name() << '\n';
cout << '\t' << two.get_name() << '\n';
cout << '\t' << three.get_name() << '\n';
A certain teacher has 3 types of assignments for her course: tests, homework, and papers. The following fragment might help her get her student's averages for the course (assumes each category is equally weighted internally -- each test is worth the same -- and then applies weights to each category):
Grader helper;
double test_weight, hw_weight, paper_weight;
double test_avg, hw_avg, paper_avg;
short num_stus;
cout << "Enter weights for tests, homework, and papers: ";
cin >> test_weight >> hw_weight >> paper_weight;
cout << "How many students do you have? ";
cin >> num_stus;
for (short s = 0; s != num_stus; s++)
{
cout << "Enter student's test scores (alpha to end): ";
cin >> test_avg;
while (!cin.fail())
{
helper.add_score(test_avg);
cin >> test_avg;
}
test_avg = helper.average();
helper.reset();
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cout << "Enter student's homework scores (alpha to end): ";
cin >> hw_avg;
while (!cin.fail())
{
helper.add_score(hw_avg);
cin >> hw_avg;
}
hw_avg = helper.average();
helper.reset();
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
cout << "Enter student's scores on papers (alpha to end): ";
cin >> paper_avg;
while (!cin.fail())
{
helper.add_score(paper_avg);
cin >> paper_avg;
}
paper_avg = helper.average();
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
helper.reset();
helper.add_score(test_avg*test_weight);
helper.add_score(hw_avg*hw_weight);
helper.add_score(paper_avg*paper_weight);
test_avg = helper.total();
helper.reset();
helper.add_score(test_weight);
helper.add_score(hw_weight);
helper.add_score(paper_weight);
test_avg /= helper.total();
cout << "\nThis student gets " << test_avg << ".\n";
}
Note I 'added' another facility to the Grader class: a total method. With this facility, we can do weighted grades, too...albeit a little clunkily. Maybe we should just do a weighted version of the Grader class:
class WeightedGrader
{
vector<double> scores;
vector<double> weights;
short num_scores;
// ...
public:
double get_score(GrdPos which) const;
double get_weight(GrdPos which) const;
bool set_score(GrdPos which, double score, double weight);
bool add_score(double new_score, double new_weight);
// ...
};
Essentially, we treat the weights and scores vectors as parallel and set/add scores with their weights in parallel. Nothing else need change on the outside. The internal code doesn't change much, either. Just work with both scores and weights in parallel. The trickiest change is in add_score:
bool WeightedGrader::add_score(double new_score, double new_weight)
{
bool added = false;
if (scores.size() != scores.max_size())
{
added = true;
weights.push_back(new_weight);
scores.push_back(new_score);
}
return added;
}
Note that we only need to check if one of the two vectors has reached its limit of storage. Since the vectors are being treated in parallel, when one fills, so will the other. Or, when one isn't full, neither will the other be.
Thinking it over, we realize that the WeightedGrader class is just like the Grader class if we default the weight arguments to 1.0! Then we'll only have to maintain one set of code...cool!
You can see both of these examples (and others) in the example directories.
Since defining a class creates a brand-new (non-void) data type, we can use it as the base-type for a vector (any dimension). Why would you want to do such a thing? Well, there are many reasons. Let's look at a few and see what kind of syntax hel...er, nightma...er, fun...yeah...fun awaits!
Let's collect a list of points the user enters and then find the pair of points that is farthest apart. First to declare our vector for storing the list:
vector<Point> data;
Looks almost like any other vector declaration. The only 'difference' is that the vector's base type is a class type (Point class we looked at before). Now let's collect the user's data:
Point t;
cout << "Enter points (q to end): ";
do
{
t.Input();
data.push_back(t);
skip_spaces();
} while (data.size() != data.max_size() && cin.peek() != 'q');
cin.ignore(numeric_limits<streamsize>::max(), '\n');
This is similar to our earlier loops for input of vector elements. The problem here is the Point Input format: (x,y). Simply entering 'q' won't end things by itself. It would extract as the '(' of the next point and then cin would simply wait for the x, etc. If we are more 'pushy' (well...not really pushy but ...oh, never mind), we can have them enter two 'q' chars to quit:
Point t;
cout << "Enter points (qq to end): ";
t.Input();
while (data.size()+1 != data.max_size() && !cin.fail())
{
data.push_back(t);
t.Input();
}
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
Now, with the second 'q' causing a fail on the x input, it looks just like the previous (numerical) entry loops. Um...but do we really need the temporary variable for input? Not exactly. We can hide this variable inside a function:
inline Point input_pt(void)
{
Point t;
t.Input();
return t;
}
// ...etc...
cout << "Enter points (qq to end): ";
do
{
data.push_back(input_pt());
} while (data.size() != data.max_size() && !cin.fail());
data.pop_back();
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
Note that the loop is now 'do-able' (sorry...couldn't resist). Also note that we must throw one item off the end which is the Point that was 'qq'd during input. It won't have valid data in it and so won't need storing. (This will always be safe since at least one Point was added to the vector.)
Next let's make loops that can create all pairs of what we have:
typedef typename vector<Point>::size_type PtPos;
for (PtPos from = 0; from+1 < data.size(); from++)
{
for (PtPos to = from+1; to < data.size(); to++)
{
if (from != to)
{
// pair data[from] with data[to]
}
}
}
The data point we are 'going' from (our distance 'origin') can be any of the first data.size()-1 Points -- all but the last Point in the list. The data point we get the distance to can be any of the remaining Points -- after the one we are 'going' from. We start the 'to' loop at from+1 because the distance calculation is symmetric -- the distance from A to B is the same as the distance from B to A. So we avoid pairs like 0, 1 and 1, 0 by having the inner loop start after the outer loop's position (if the outer loop is at 1, the inner one will start at 2 and we avoid calculating the 1, 0 distance -- since it would be the same as the 0, 1 distance we already did!)
We also realize that the distance from a point to itself is always 0 and we don't care about that (it can't possibly be our maximum!). So, basically we have something like this:
Point To |
-\ |
\---\ | A B C D E
Point From\--\ |
-----------\|-----------------------------------------------
|
A | X check check check check
|
|
B | X X check check check
|
|
C | X X X check check
|
|
D | X X X X check
|
|
E | X X X X X
|
So, for this case of 5 points (A-E), we can get away with checking just 10 pairs instead of the possible 25 pairs since many are redundant (due to symmetry) or useless (the self-pairs). In general, we reduce from n-squared pairs to check (for n points) to:
2
n - n n*(n - 1)
---------- = -------------
2 2
In fact, looking at the chart, the if inside the loops doesn't even need to be there. We just need the loops!
But, we digress. Let's look at one more thing for the loops before we actually do the maximum distance bit. Note that the loop conditions are not using != as we normally do but <. The reason for this is that in the extreme case that there are no Points in the list, the != would cause a (near) infinite loop. Note:
from | data.size()-1 | != result | loop will
-------+-----------------+-------------+---------------
0 | max_size() | true | continue
1 | max_size() | true | continue
2 | max_size() | true | continue
3 | max_size() | true | continue
4 | max_size() | true | continue
And since from is increasing while the vector stays the same length, we won't reach max_size() until we hit the top of the integer range for vector<Point>::size_type! (size_type is always an unsigned type...) If we are dealing with a short, that is 65,535 iterations. If we are dealing with a long, that'd be 232-1 iterations! Luckily for us, the program should crash long before that happened because the elements we were trying to iterate thru would not exist and the system would NOT be happy about that!
We've also shifted the expression 'from < data.size()-1' to be 'from+1 < data.size()' -- which is mathematically equivalent but avoids the unsigned wrap-around to the maximum:
from+1 | data.size() | != result | loop will | < result | loop
--------+---------------+-------------+------------+------------+---------
1 | 0 | true | continue | false | dies
2 | 0 | true | continue | N/A | N/A
3 | 0 | true | continue | N/A | N/A
4 | 0 | true | continue | N/A | N/A
5 | 0 | true | continue | N/A | N/A
Note also that the inner loop also suffers:
to | data.size() | != result | loop will
-------+-----------------+-------------+---------------
1 | 0 | true | continue
2 | 0 | true | continue
3 | 0 | true | continue
4 | 0 | true | continue
5 | 0 | true | continue
That table being for the case when from is 0, but they just look worse and worse as from increases. Each of these loops will suffer the same (near) infinite number of iterations and the same propensity to crash your program.
But, with < instead, we note that 1 < 0 is immediately false and the outer loop stops without trying to form pairs of no Points. Even when there is only one Point, we won't enter the outer loop, because 0 < 0 is immediately false.
Finally, for the extreme case when we have just two Points in the list, the outer loop will enter (0 < 1) and the inner loop will enter since 1 < 2 is true. So we form that one pair (0 with 1). On the next pass, the outer loop will end as we come back through since it will be checking 1 < 1, which is false.
Having formed the pairs we want to check, we now want to find the maximum distance between pairs:
typedef typename vector<Point>::size_type PtPos;
double max = 0.0; // a valid start since all non-self distances
// will be strictly greater than 0.0
PtPos max1, max2; // indices of farthest apart pair
max1 = max2 = 0;
for (PtPos from = 0; from+1 < data.size(); from++)
{
for (PtPos to = from+1; to < data.size(); to++)
{
// pair data[from] with data[to]
if ((data[from].distance(data[to]) > max)
{
max1 = from;
max2 = to;
max = data[from].distance(data[to]);
}
}
}
Of course, the if here is our max finding if -- not the if that kept us from being the same point.
Sanity Check: If we have no points or 1 point, the max will end up being 0.0, but that's pretty much correct for those situations anyway!
Note the use of the dot operator (.) when we call the distance method. The data[from] picks a single Point object from the vector and then the dot calls the distance method with that object as the calling object. (And we do similarly for the 'to' Point, but we actually pass that object to the distance method as its single argument.)
The only other thing I would recommend is to have a cache (temporary) variable to hold the result of the distance method. Although distance is small and is probably inline'd, its actual calculation is a bit expensive -- two pow's and a sqrt. So we can speed up this loop greatly by caching the results:
typedef typename vector<Point>::size_type PtPos;
double max = 0.0, // a valid start since all non-self distances
// will be strictly greater than 0.0
dist; // used to cache the distance calculation result
PtPos max1, max2; // indices of farthest apart pair
max1 = max2 = 0;
for (PtPos from = 0; from+1 < data.size(); from++)
{
for (PtPos to = from+1; to < data.size(); to++)
{
// pair data[from] with data[to]
dist = data[from].distance(data[to]);
if (dist > max)
{
max1 = from;
max2 = to;
max = dist;
}
}
}
It also made the code spacier and easier to read. Cool!
Now that we've gotten our list, let's next find the pair of points whose midpoint is closest to the origin -- (0.0,0.0) that is.
Point origin; // default ctor's to 0,0
double min = -1.0, // obviously invalid minimum
dist; // caching distance result
PtPos min1, min2; // indices of closest midpoint pair
if (data.size() > 1)
{
min1 = 0;
min2 = 1;
min = data[min1].midpoint(data[min2]).distance(origin);
for (PtPos from = 0; from != data.size()-1; from++)
{
for (short to = from+1; to != data.size(); to++)
{
dist = data[min1].midpoint(data[min2]).distance(origin);
if (dist < min)
{
min1 = from;
min2 = to;
min = dist;
}
}
}
cout << "\nI think you'll find that ";
data[min1].Output();
cout << " and ";
data[min2].Output();
cout << " are the pair whose midpoint is\n"
"closest to the origin!\n";
}
else
{
cout << "\n\aNot enough data for calculation!\n";
}
Not bad. First an if to protect us from having silly and senseless results. But then, inside, what's that [].().() non-sense! Oh, my! Well, let's break it down again:
data[min1].midpoint(data[min2]).distance(origin)
---------- ----------
object object
The min1 and min2 are used to subscript the vector to select two objects from the list, I'll call them A and B for simplification (like a math change of variable or substitution):
A.midpoint(B).distance(origin)
-------------
object
Now I call the midpoint method with A as the calling object and B as the actual argument. The midpoint method sends back a brand new Point object! Let's call that one C:
C.distance(origin)
And finally we have an expression we recognize: object calling method. Subscript takes precedence over dot and then dot's happen left to right (like * and +: x * y + z * w + t; this multiplies x and y giving A and z times w giving B: A + B + t; this adds A and B giving C: C + t; this is add C to t!).
Anyway, the whole she-bang can be found here.
Some sadistic %$@#!%$ ...er... client wants us to track the start and end times for their classes (meetings, dates, whatever) and then report any overlapping events to them. For this we need one vector for the names of the events: Hist101, Work, Tom, Ellen, Study, Chem221, etc. We'll also need two other vectors: one each for the start time and the end time for the event. All three of these will need to line up in parallel:
+---------------+ +---------+ +---------+
| Hist101 | | 10:20 | | 11:50 |
+---------------+ +---------+ +---------+
| Work | | 11:30 | | 17:00 |
+---------------+ +---------+ +---------+
| Tom | <-- i --> | 18:30 | <-- i --> | 20:00 |
+---------------+ +---------+ +---------+
| Ellen | | 19:45 | | 21:15 |
+---------------+ +---------+ +---------+
| Study | | 21:30 | | 21:45 |
+---------------+ +---------+ +---------+
| Chem221 | | 08:30 | | 09:55 |
+---------------+ +---------+ +---------+
We immediately see a few overlaps for ourselves, but several problems pop up. First, the times aren't in order and it would be ever-so much easier if things were listed in order. Second, time is a composite quantity (with need of data validation): hours and minutes. We should use a class for this. (Oh, look what I found!!!) And third, how exactly do we tell if times are overlapping? Hmm...
Let's think about those while we do some grunt work. We'll start with the declarations:
vector<string> events;
vector<Time> starts_at, ends_at;
Now we fill in the stuff our client wants:
string event;
Time t;
cout << "Enter meeting name (no spaces), start time, and end time:\n";
cin >> event;
while (strcasecmp(event, "done") != 0 &&
events.size()+1 != events.max_size())
{
events.push_back(event);
t.input();
starts_at.push_back(t);
t.input();
ends_at.push_back(t);
cin >> event;
}
cin.ignore(numeric_limits<streamsize>::max(), '\n');
Here we have let them enter the special event name 'done' to signal that they are 'done' entering events. We again use a temporary Time object to input each next Time for both starting and ending times and then put it onto the correct list. The 'done' event shouldn't have times following it so we let just the event name prime the loop (and toss any extra crap they've entered...).
Now we are up to the question of order. I'm pretty sure the names themselves won't help us determine overlap so we should order by time. But start or end time? Assuming no event ends before it begins, it shouldn't matter -- but we'll choose start time just in case some event wraps across midnight. The crucial thing to remember is to swap data in all parallel vectors when two start times are out of order!
To sort by time, we'll need to be able to compare times. We can do this in several ways. The most natural would be to teach the Time class how to compare Times to each other. We'd need to write at least two methods (usually less and equal -- greater being neither of those; i.e. x > y == !(x < y) && !(x == y)). This isn't really too hard:
class Time
{
public:
bool equal(const Time & t) const
{ return hour == t.hour && minute == t.minute &&
second == t.second; }
bool less(const Time & t) const
{ return hour < t.hour ||
(hour == t.hour && minute < t.minute) ||
(hour == t.hour && minute == t.minute &&
second < t.second); }
// ...
};
But that one seems like a lot of typing. Maybe a quicker way? Well, we could do:
Time a, b;
if (a.get_as_sec() < b.get_as_sec())
{
// a < b
}
// similarly for == and even >
Although the second is much easier for us, it is actually much less efficient for our user and so is the worse choice. I'll assume we added the above methods to the class as we continue...
Now what sort should we use? Bubble? Selection? Insertion? How about selection? It's faster than bubble from the reduction in swapping and we have a LOT of data to swap! So:
void selection(vector<string> & a,
vector<Time> & b,
vector<Time> & c)
{
vector<Time>::size_type min_idx;
for (vector<Time>::size_type pass = 0; pass+1 < b.size(); pass++)
{
min_idx = find_min(b, b.size(), pass);
if (min_idx != pass)
{
swap(a[pass], a[min_idx]);
swap(b[pass], b[min_idx]);
swap(c[pass], c[min_idx]);
}
}
return;
}
(Note the 'pass+1 < b.size()' thing again...) And some helper functions:
vector<Time>::size_type
find_min(const vector<Time> & a,
vector<Time>::size_type end,
vector<Time>::size_type start = 0);
inline void swap(string & a, string & b)
{
string c = a;
a = b;
b = c;
return;
}
inline void swap(Time & a, Time & b)
{
Time c = a;
a = b;
b = c;
return;
}
Oh, we better define that find_min, eh?
vector<Time>::size_type
find_min(const vector<Time> & a,
vector<Time>::size_type end,
vector<Time>::size_type start)
{
vector<Time>::size_type min_at = start;
for (vector<Time>::size_type c = start+1; c < max; c++)
{
if (a[c].less(a[min_at]))
{
min_at = c;
}
}
return min_at;
}
Note the overloaded swap and the . to call the less method we (inline) defined above. What was next... Oh, yeah, the Time class. Um...got it...*smile* Next!
How do we code that two events overlap? Well, what does it mean in reality? It means that one starts while the other is still going on. I.E. the start time of one is less than the end time of the other. So:
bool overlaps(const Time & end, const Time & start)
{
return start.less(end);
}
And:
for (vector<Time>::size_type c = 0; c+1 < starts_at.size(); c++)
{
if (overlaps(ends_at[c], starts_at[c+1]))
{
cout << "\n\a" << events[c] << " and "
<< events[c+1] << " overlap!!!\n";
}
}
(And again with the 'c+1 < starts_at.size()' stuff!) Note that we only look at consecutive pairs since we've sorted the events. And since we want only pairs, we stop one short of the end of the data! (The last data has no following event to pair with!) Here is the code with a simplification to avoid coding strcasecomp for you...
Yes, it is still possible that one event could completely subsume/encompass another, but that would still be reported as an overlap. The only problem is if one event encompasses several other events which do not themselves overlap we'll report only one overlap! Darn! Fixing this is left to the interested reader...
I'll describe it later, but here's the code for using a vector of Element objects instead of just handling 3.
More to come...