# Using Library Algorithms in C++

• Print
This chapter is from the book

## Comparing Grading Schemes

Imagine that we have a grading scheme that bases students' final grades in part on their median homework scores. Devious students can exploit this scheme by deliberately not turning in all their homework assignments. After all, the bottom half of their homework grades has no effect on their final grade. If they've done enough homework to ensure a good grade, why not stop doing homework altogether?

In our experience, most students do not exploit this particular loophole. However, we did have an occasion to teach one class that gleefully and openly did so. We wondered whether the students who skipped homework had, on average, different final grades than those who did all the homework. While we were thinking about how to answer that question, we decided that it might be interesting to see what the answer would be if we used one of two alternative grading schemes:

• Using the average instead of the median, and treating those assignments that the student failed to turn in as 0

• Using the median of only the assignments that the student actually submitted

For each of these grading schemes, we wanted to compare the median grade of the students who turned in all their homework with the median grade of the students who missed one or more assignments. We wound up with a program that had to solve two distinct subproblems:

1. Read all the student records, separating the students who did all the homework from the others

2. Apply each of the grading schemes to all the students in each group, and report the median grade of each group

### Working with Student Records

Our first subproblem is to read and classify the student records. Fortunately, we already have some code that we can use in solving this part of the problem: We can use the Student_info type and the associated read function (from previous book chapters) to read the student data records. What we don't have yet is a function that checks whether a student has done all the homework. Writing such a function is easy:

```bool did_all_hw(const Student_info& s)
{ return ((find(s.homework.begin(), s.homework.end(), 0))
== s.homework.end()); } ```

This function looks in s.homework to see whether any of the values stored there are 0. Because we give at least partial credit for any assignment that is turned in, a 0 grade means that the assignment was not submitted. We compare the return from find with homework.end(). As usual, find returns its second argument if it fails to find the value that it seeks.

With these two functions, writing code to read and separate the student records is simplicity itself. We'll read each student record, check whether the student did all the homework, and append the record to one of two vectors, which, for want of a better idea, we'll name did and didnt. While we're at it, we'll check that neither vector is empty so that we'll know that our analysis will actually tell us something useful:

```vector<Student_info> did, didnt; Student_info student;
// read all the records, separating them based on whether all
homework was done while (read(cin, student))
{ if (did_all_hw(student)) did.push_back(student);
else didnt.push_back(student); }
// check that both groups contain data if (did.empty())
{ cout << "No student did all the homework!" << endl; return 1; }
if (didnt.empty()) { cout << "Every student did all the homework!"
<< endl; return 1; } ```

The only new idea here is the emptymember function, which yields true if the container is empty and false otherwise. It is a better idea to use this function to check for an empty container than it is to compare the size with 0 because, for some kinds of containers, it might be more efficient to check whether the container has any elements than to figure out exactly how many elements there are.

### Analyzing the Grades

We now know how to read and classify student records into the did and didnt vectors. The next step is to analyze them, which means that we need to think a little about how to structure the analysis.

We know that we have three analyses to perform, and each analysis has two parts that analyze separately the students who did and who didn't do all the homework. Because we will do each analysis on two sets of data, we certainly want to make each analysis its own function. However, there are some operations, such as reporting in a common format, that we are going to want to do on pairs of analyses rather than on individual analyses. Evidently, we'll want to make writing the results of each pair of analyses into a function as well.

The tricky part is that we want to call the function that writes the analysis results three times, once for each kind of analysis. We want that function to call the appropriate analysis function twice, once each for the did and didnt objects. However, we want the function that generates the reports to call a different analysis function each time we call it. How do we arrange that?

The easiest solution is to define three analysis functions and pass each one as an argument to the reporting function. In this case, we want our output routine to take five arguments:

• The stream on which to write the output

• A string that represents the name of the analysis

• The function to use for the analysis

• Two arguments, each of which is one of the vectors that we want to analyze

For example, let's assume that the first analysis, which looks at the medians, is done by a function called median_analysis. Then we'd like to report the results for each group of students by executing:

`write_analysis(cout, "median", median_analysis, did, didnt); `

Before we define write_analysis, let's define median_analysis. We would like to give that function a vector of student records, and we would like it to compute the students' grades according to the normal grading scheme and to return the median of those grades. We can define that function as follows:

```// this function doesn't quite work double median_analysis
(const vector<Student_info>& students) { vector<double> grades;
transform(students.begin(), students.end(),

Although this function might appear difficult at first glance, it introduces only one new idea—namely, the transform function. This function takes three iterators and a function. The first two iterators specify a range of elements to transform; the third iterator is the destination into which to put the result of running the function.

When we call transform, we are responsible for ensuring that the destination has room for the values from the input sequence. In this case, there is no problem because we obtain the destination by calling back_inserter, thereby arranging that transform's results will be appended to grades, which will automatically grow as necessary to accommodate the results.

The fourth argument to transform is a function that transform applies to each element of the input sequence to obtain the corresponding element of the output sequence. Therefore, when we call transform in this example, the effect is to apply the grade function to each element of students and to append each grade to the vector named grades. When we have all these students' grades, we call median to compute their median.

There's only one problem: As the comment notes, this function doesn't quite work. One reason that it doesn't work is that there are several overloaded versions of the grade function. The compiler doesn't know which version to call because we haven't given grade any arguments. We need a way to tell the compiler to do so.

The other reason is that the grade function will throw an exception if any student did no homework at all, and the transform function does nothing about exceptions. If an exception occurs, the transform function will be stopped at the point of the exception, and control will return to median_analysis. Because median_analysis doesn't handle the exception, either, the exception will continue to propagate outward. The effect will be that this function will also exit prematurely, passing control to its caller, and so on, until control reaches an appropriate catch. If there is no such catch, as would be likely in this case, the program itself is terminated and the message that was thrown is printed (or not, depending on the implementation).

We can solve both problems by writing an auxiliary function that will try the grade function and handle the exception. Because we are calling the grade function explicitly rather than passing it as an argument, the compiler will be able to figure out which version we mean:

```double grade_aux(const Student_info& s) { try { return grade(s);
catch (domain_error) { return grade(s.midterm, s.final, 0);

}
} ```

This function will call the correct version of grade. If an exception occurs, we will catch it and call the version of grade that takes three doubles that represent the exam scores and overall homework grade. Thus, we'll assume that students who did no homework at all got a 0 grade on their homework, but their exams still count.

Now we can rewrite the analysis function to use grade_aux:

```// this version works fine double median_analysis
(const vector<Student_info>& students) { vector<double> grades;
transform(students.begin(), students.end(),

Having seen what an analysis routine looks like, we are now in a position to define write_analysis, which uses an analysis routine to compare two sets of students:

```void write_analysis(ostream& out, const string& name,
double analysis(const vector<Student_info>&),
const vector<Student_info>& did,
const vector<Student_info>& didnt)
{ out << name << ": median(did) = " << analysis(did) << ",
median(didnt) = " << analysis(didnt) << endl; } ```

Again, this function is surprisingly small, although it does introduce two new ideas. The first is how to define a parameter that represents a function. The parameter definition for analysis looks just like the function declaration that we wrote earlier in the book. (Actually, as we shall learn later, there is slightly more going on here than meets the eye. The additional detail doesn't affect the current discussion directly.) The other new idea is the return type, void. The built-in type void can be used only in a few restricted ways, one of which is to name a return type. When we say that a function "returns" a void, we're really saying that it has no return value. We can exit from such a function by executing a return statement with no value, such as

`return; `

or, as we do here, by falling off the end of the function. Ordinarily, we cannot just fall off the end of a function, but the language allows functions that return void to do so.

At this point, we can write the rest of our program:

```int main() {
// students who did and didn't do all their homework
vector<Student_info> did, didnt;
// read the student records and partition them
Student_info student; while (read(cin, student))
{ if (did_all_hw(student)) did.push_back(student);
else didnt.push_back(student); }
// verify that the analyses will show us something
if (did.empty()) { cout << "No student did all the homework!"
<< endl; return 1; } if (didnt.empty())
{ cout << "Every student did all the homework!" << endl; return 1; }
// do the analyses write_analysis
(cout, "median", median_analysis, did, didnt);
write_analysis(cout, "average", average_analysis, did, didnt);
write_analysis(cout, "median of homework turned in",
optimistic_median_analysis, did, didnt);
return 0; } ```

All that remains is to write average_analysis and optimistic_median_analysis.

### Grading Based on Average Homework Grade

We would like the average_analysis function to compute the students' grades by using the average homework grade rather than the median. Therefore, the logical first step is to write a function to compute the average of a vector, with the aim of using it instead of median for grade computation:

```double average(const vector<double>& v)
{ return accumulate(v.begin(), v.end(), 0.0) / v.size(); } ```

This function uses accumulate, which, unlike the other library algorithms we've used, is declared in <numeric>. As this header's name implies, it offers tools for numeric computation. The accumulate function adds the values in the range denoted by its first two arguments, starting the summation with the value given by its third argument.

The type of the sum is the type of the third argument, so it is crucially important for us to use 0.0, as we did here, instead of 0. Otherwise, the result would be an int, and any fractional part would be lost.

Having used accumulate to generate the sum of all the elements in the range, we divide that sum by v.size(), which is the number of elements in the range. The result of that division, of course, is the average, which we return to our caller.

Once we have the average function, we can use it to implement the average_grade function to reflect this alternative grading policy:

```double average_grade(const Student_info& s)
{ return grade(s.midterm, s.final, average(s.homework)); } ```

This function uses the average function to compute an overall homework grade, which it then gives to the grade function to use in computing the final grade.

With this infrastructure in place, the average_analysis function is simplicity itself:

```double average_analysis(const vector<Student_info>& students)
transform(students.begin(), students.end(),

The only difference between this function and median_analysis is its name and its use of average_grade instead of grade_aux.

### Median of the Completed Homework

The last analysis scheme, optimistic_median_analysis, gets its name from the optimistic assumption that the students' grades on the homework that they didn't turn in would have been the same as those on the homework that they did turn in. With that assumption, we would like to compute the median of just the homework that each student submitted. We'll call this computation an optimistic median, and we'll begin by writing a function to compute it. Of course, we have to contend with the possibility that a student did no homework at all, in which case we'll use 0 as the overall homework grade:

```// median of the nonzero elements of s.homework, or 0 if no
such elements exist double optimistic_median
(const Student_info& s) { vector<double> nonzero;
remove_copy(s.homework.begin(), s.homework.end(),
back_inserter(nonzero), 0);
if (nonzero.empty()) return grade(s.midterm, s.final, 0);
else return grade(s.midterm, s.final, median(nonzero)); } ```

This function works by extracting the nonzero elements from the homework vector and putting them into a new vector, called nonzero. Once we have the nonzero homework grades, we call the correct version of grade to compute the final score based on the median of the homework assignments that were actually submitted.

The only new idea in this function is how we get values into nonzero, which we do by calling the remove_copy algorithm. To understand the call to remove_copy, you may find it useful to know that the library provides "copying" versions of many of the algorithms. So, for example, remove_copy does what remove does but copies its results to an indicated destination.

The remove function finds all values that match a given value and "removes" those values from the container. All the values in the input sequence that are not "removed" will be copied into the destination. We'll have more to say shortly about what "remove" means in this context.

The remove_copy function takes three iterators and a value. As with most algorithms, the first two iterators denote the input sequence. The third denotes the beginning of the destination for the copy. As with copy, the remove_copy algorithm assumes that there is enough space in the destination to hold all the elements that are copied. We call back_inserter to grow nonzero as needed.

We should now be able to see that the effect of the remove_copy call is to copy into nonzero all the nonzero elements in s.homework. We then check whether nonzero is empty, and, if not, we do the normal grade calculation based on the median of the nonzero grades. If nonzero is empty, then we use 0 as the homework grade.

Of course, to complete our analysis, we need to write an analysis function to call our optimistic_median function. We leave doing so as an exercise.

• 🔖 Save To Your Account

### InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.

## Overview

Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

## Collection and Use of Information

To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

### Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

### Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.

### Surveys

Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

### Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.

If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

### Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

### Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

## Other Collection and Use of Information

### Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

### Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

### Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

### Do Not Track

This site currently does not respond to Do Not Track signals.

## Security

Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.

## Children

This site is not directed to children under the age of 13.

## Marketing

Pearson may send or direct marketing communications to users, provided that

• Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
• Such marketing is consistent with applicable law and Pearson's legal obligations.
• Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
• Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

## Correcting/Updating Personal Information

If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.

## Choice/Opt-out

Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

## Sale of Personal Information

Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

## Supplemental Privacy Statement for California Residents

California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

## Sharing and Disclosure

Pearson may disclose personal information, as follows:

• As required by law.
• With the consent of the individual (or their parent, if the individual is a minor)
• In response to a subpoena, court order or legal process, to the extent permitted or required by law
• To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
• In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
• To investigate or address actual or suspected fraud or other illegal activities
• To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
• To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
• To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.

This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.