Home > Articles > Programming > C/C++

  • Print
  • + Share This
This chapter is from the book

This chapter is from the book

How to Design a Generic Algorithm

Here is our task. We are given a vector of integer values. We are asked to return a new vector holding all the values that are less than 10. A quick but inflexible solution is the following:

vector<int> less_than_10( const vector<int> &vec )
{
  vector<int> nvec;
  for ( int ix = 0; ix < vec.size(); ++ix )
     if ( vec[ ix ] < 10 )
        nvec.push_back( vec[ ix ] );
  return nvec;
}

If the user wants all the elements less than 11, we must either create a new function or generalize this one to allow the user to specify a value against which to compare the elements—for example:

vector<int> less_than( const vector<int> &vec, int less_than_val );

But our next task is actually somewhat more difficult. We must allow the user to specify an alternative operation, such as greater than, less than, and so on. How can we parameterize an operation?

One solution is to replace the less-than operator with a function call. We add a third parameter, pred, specifying a pointer to a function having a parameter list of two integers and returning a bool. less_than() isn't the right name any longer, so let's call it filter():

vector<int> filter( const vector<int> &vec, 
          int filter_value, 
          bool (*pred)( int, int ));

For our user's convenience, we also define a number of relational functions that can be passed to filter():

bool less_than( int v1, int v2 ) 
   { return v1 < v2 ? true : false; }

bool greater_than( int v1, int v2 ) 
   { return v1 > v2 ? true : false; }

and so on. The user can then either pass one of these functions to an invocation of filter() or define her own relational function. The only constraint is that the function passed must return bool and accept two integers in its parameter list. Here is how filter() might be invoked:

vector<int> big_vec;
int value;
// ... fill big_vec and value
vector<int> lt_10 = filter( big_vec, value, less_than );

The only task left for us is actually to implement filter():

vector<int> filter( const vector<int> &vec, 
          int filter_value, 
          bool (*pred)( int, int ))
{
  vector<int> nvec;

  for ( int ix = 0; ix < vec.size(); ++ix )
     // invokes the function addressed by pred
     // tests element vec[ix] against filter_value
     if ( pred( vec[ ix ], filter_value ))
        nvec.push_back( vec[ ix ] );

  return nvec;
}

This implementation of filter() explicitly iterates across each element using a for loop. Let's replace the use of the for loop with the find_if() generic algorithm. We repeatedly apply find_if() to the sequence to identify each element that meets the criteria defined by the user-specified pointer to function. How might we do that?

Let's start with finding every element equal to 10. The find() generic algorithm takes three arguments: the two iterators marking the first and 1 past the last element to examine, and the value we are looking for. In the following code, count_occurs() illustrates how to apply find() repeatedly to a container without looking at any element twice:

int count_occurs( const vector<int> &vec, int val ) 
{
  vector<int>::const_iterator iter = vec.begin();
  int occurs_count = 0;
  while (( iter = find( iter, vec.end(), val )) != vec.end() )
  {
     ++occurs_count; 
     ++iter; // address next element
  }
  return occurs_count;
}

The while loop assigns iter the return value of find(). find() returns an iterator addressing an element equal to val or, if no matching element is found, an iterator equal to vec.end(). When iter is equal to vec.end(), the loop terminates.

The success of the while loop depends on our advancing iter 1 past the matching element with each iteration of the loop. For example, let's say that vec contains the following elements: {6,10,8,4,10,7,10}. The declaration statement

vector<int>::const_iterator iter = vec.begin();

initializes iter to address the first element of the vector that holds the value 6. find() returns an iterator addressing the second element. Before we reinvoke find(), we must advance iter by 1. find() is next invoked with iter addressing the third element. find() returns an iterator addressing the fifth element, and so on.

Function Objects

Before we reimplement filter() to support find_if(), let's look at the predefined function objects provided by the standard library. A function object is an instance of a class that provides an overloaded instance of the function call operator. Overloading the call operator allows a function object to be used just as if it were a function.

A function object implements what we would otherwise define as an independent function. Why do we bother? The primary reason is efficiency. We can inline the call operator, thereby eliminating the function call overhead that comes with invoking the operation through a pointer to function.

The standard library predefines a set of arithmetic, relational, and logical function objects. In the following list, type is replaced by a built-in or class type in an actual use of the function object:

  • Six arithmetic function objects: plus<type>, minus<type>, negate<type>, multiplies<type>, divides<type>, and modulus<type>

  • Six relational function objects: less<type>, less_equal<type>, greater<type>, greater_equal<type>, equal_to<type>, and not_equal_to<type>

  • Three logical function objects, using the &&, ||, and ! operators, respectively: logical_and<type>, logical_or<type>, and logical_not<type>

To use the predefined function objects, we must include the associated header file:

#include <functional>

For example, by default, sort() orders its elements in ascending order using the less-than operator of the underlying element type. If we pass sort() the greater-than function object, the elements are now sorted in descending order:

sort( vec.begin(), vec.end(), greater<int>() );

The syntax

greater<int>()

causes an unnamed greater class template object to be created and passed into sort().

binary_search() expects the elements that it searches to be sorted by the less-than operator. For it to search our vector correctly, we must now pass it an instance of the function object used to sort our vector:

binary_search( vec.begin(), vec.end(), elem, greater<int>() );

Let's display the Fibonacci series in a series of increasingly impenetrable disguises: each element added to itself, each element multiplied by itself, each element added to its associated Pell series element, and so on. One way to do this is by using the transform() generic algorithm and the function objects plus<int> and multiplies<int>.

transform() must be passed (1) a pair of iterators to mark the element range to transform, (2) an iterator to point to the beginning of the container from which to fetch the values to apply to the transformation, (3) an iterator to point to the beginning of the container where we are to place the result of each transformation, and (4) the function object (or pointer to function) representing the operation to apply. For example, here is our addition of the Pell elements to those of the Fibonacci:

transform( fib.begin(), fib.end(), // (1)
      pell.begin(),      // (2)
      fib_plus_pell.begin(), // (3)
      plus< int >() );    // (4)

In this example, the target vector, pell, must be at least as large as fib, or else the transform() algorithm will overflow pell.

In this next call of transform(), we multiply each element by itself and store the result by overriding the original element:

transform( fib.begin(), fib.end(),  // (1)
      fib.begin(), fib.begin(), // (2), (3)
      multiplies< int >() );   // (4)

Function Object Adapters

These function objects do not quite work with what we need to do with find_if(). The less<type> function object, for example, expects two values. It evaluates to true if the first value is less than the second. In our case, each element must be compared against the value specified by the user. Ideally, what we need to do is to turn less<type> into a unary operator by binding the second value to that specified by the user. In this way, less<type> compares each element against that value. Can we actually do that? Yes. The standard library provides an adapter mechanism to do just that.

A function object adapter modifies a function object. A binder adapter converts a binary function object into a unary object by binding one of the arguments to a particular value. This is just what we need. There are two binder adapters: bind1st, which binds the value to the first operand, and bind2nd, which binds the value to the second. Here is a possible modification of filter() using the bind2nd adapter:

vector<int> filter( const vector<int> &vec, 
           int val, less<int> &lt )
{
  vector<int> nvec;
  vector<int>::const_iterator iter = vec.begin();
  
  // bind2nd( less<int>, val )
  // binds val to the second value of less<int>
  // less<int> now compares each value against val

  while (( iter = 
       find_if( iter, vec.end(), 
           bind2nd( lt, val ))) != vec.end() )
  {
       // each time iter != vec.end(), 
       // iter addresses an element less than val
       nvec.push_back( *iter );
       iter++;
  }
  return nvec;
}

How might we generalize filter() further to eliminate its dependence both on the element type of the vector and on the vector container itself? To eliminate the dependency on the element type, we turn filter() into a template function and add the type to our template declaration. To eliminate the vector container dependency, we pass in a first,last iterator pair. Instead, we add another iterator to the parameter list indicating where we should begin copying the elements. Here is our reimplementation:

template <typename InputIterator, typename OutputIterator,
     typename ElemType, typename Comp>
OutputIterator 
filter( InputIterator first, InputIterator last,
    OutputIterator at, const ElemType &val, Comp pred )
{
  while (( first = 
       find_if( first, last, 
           bind2nd( pred, val ))) != last )
  {
       // just to see what is going on ...
       cout << "found value: " << *first << endl;

       // assign value, then advance both iterators
       *at++ = *first++;
  }
  return at;
}

Can you see how you might actually call filter()? Let's write a small program to test it using both a built-in array and a vector. We need two of each container type: one to hold the values to be filtered, and one to hold the elements that get filtered. For the moment, we define the target container to be the same size as the original container. In another section, we look at an alternative solution using insert iterator adapters.

int main()
{
  const int elem_size = 8;

  int ia[ elem_size ] = { 12, 8, 43, 0, 6, 21, 3, 7 };
  vector<int> ivec( ia, ia+elem_size );

  // containers to hold the results of our filter()
   int ia2[ elem_size ];
  vector<int> ivec2( elem_size );

  cout << "filtering integer array for values less than 8\n";
  filter( ia, ia+elem_size, ia2, elem_size, less<int>() );

  cout << "filtering integer vector for values greater than 8\n";
  filter( ivec.begin(), ivec.end(), ivec2.begin(), 
      elem_size, greater<int>() );
}

When compiled and executed, this program generates the following output:

filtering integer array for values less than 8
found value: 0
found value: 6
found value: 3
found value: 7

filtering integer vector for values greater than 8
found value: 12
found value: 43
found value: 21

A negator adapter reverses the truth value of a function object. not1 reverses the truth value of a unary function object. not2 reverses the truth value of a binary function object. For example, to identify the elements greater than or equal to 10, we can negate the result of the less<int>() function object:

while (( iter =
     find_if( iter, vec.end(),
         not1( bind2nd( less<int>, 10 )))) 
        != vec.end() )

In general, there is no one solution to a problem. Our approach to finding all the elements less than a value, for example, involves looking at each element in turn and copying each value if it is less than the specified value. That solves our problem but is not the only approach we might have taken.

An alternative approach is the following: First, we sort the vector. Next, using find_if(), we locate the first element that is greater than the value. Finally, we delete all the elements from that found element to the end of the vector. Actually, we'll sort a local copy of the vector. Users might not appreciate our changing the element order of their vector. Here is a nontemplate version of this solution:

vector<int> sub_vec( const vector<int> &vec, int val )
{ 
  vector<int> local_vec( vec );
  sort( local_vec.begin(), local_vec.end() );

  vector<int>::iterator iter =
     find_if( local_vec.begin(), 
          local_vec.end(),
          bind2nd( greater<int>, val ));

  local_vec.erase( iter, local_vec.end() );
  return local_vec;
}

Okay, whew. This is an intense section, and making sense of it might require a second reading and possibly writing some code. A good exercise is to try your hand at turning sub_vec() into a template function along the lines of filter(). Let me summarize what we've done.

We start with a function to find the elements in a vector of integers that have a value less than 10. We decide that hard-coding the value is too restrictive.

We first add a value parameter to allow the user to indicate a value against which to compare the vector elements.

We next add a pointer to a function parameter to allow the user to indicate which comparison filter to apply.

We then introduce function objects, which provide an alternative, more efficient method of passing an operation into a function. We briefly review the built-in function objects provided by the standard library. (In Chapter 4, we look at how to write our own function objects.)

Finally, we reimplement the function as a template function. To support multiple container types, we pass an iterator pair marking the first and 1 past the last element to traverse. To support multiple element types, we parameterize the element type. To support both pointers to functions and function objects, we parameterize the comparison operation to apply to the elements.

Our function is now independent of the element type, the comparison operation, and the container. In short, we have transformed our original function into a generic algorithm.

  • + Share This
  • 🔖 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.

Newsletters

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.

Links


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.

Requests and Contact


Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice


We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020