C++ bind1st and bind2nd

This document aims to help you understand bind1st and bind2nd, which may seem a rather odd and arbitrary objective, but

these routines appear in otherwise simple examples of generic code – you can use them without understanding what they do, but to make the most of them it helps
to know more
to understand the value of these functions you need to learn about several important C++ concepts and use them in combination, so even if you never need to use
bind1st or bind2nd the journey’s an interesting one

C++ is quite a strongly typed language – if a function requires an argument of type int and you provide a string, the compiler will complain. This is a good thing in that errors are reduced but it makes generic code (code which will work with different types of arguments) harder to write. Some of the apparent complexity of C++ (bind1st, for example) is due to the methods required to resolve this conflict of needs.

Templates

Templates can help with producing generic code. Consider the following simple routine.

bool greater_than(int a, int b){
return a>b;
}

The basic code would be the same if the arguments were floating point numbers or even strings, but because C++ is fussy about types we’d have to write a separate routine for each type, replacing int each time. This is where templates prove useful

template <class T>
bool greater_than(T a, T b){
return a>b;
}

This uses the same basic code as the earlier example but instead of int we have T, which at compile time is replaced by whatever is required by subsequent code. So

int a=6, b=9;
string s=”apple”, t=”pear”;
cout << greater_than(a,b);
cout << greater_than(s,t);

will work, the compiler creating the appropriate code. If we try

greater_than(a,t);

however, compilation won’t work, so we haven’t compromised on safety.

Using standard library routines

The standard library makes heavy use of templates internally, making it possible to use generic routines without having to learn all the template-related syntax. A little knowledge can go a long way. For example, in the code below,

vector<int> v(3) means “create a vector of ints big enough to hold 3 elements”. Note the use of the “< >” characters
s.end() gets the location just beyond the end of the s collection of things. This is what find needs to know when to stop searching. It’s also the value returned by find if the value can’t be found.

Here’s a complete program showing how how find is used in the same way whether you’re search for characters or integers.

#include <algorithm>
#include <vector>
#include <iostream>
#include <string>

using namespace std;
int main() {
string s=”apple”;
vector<int> v(3);
v[0]=1; v[1]=2; v[2]=3;
// the following line checks if find returns s.end()
cout << (find(s.begin(),s.end(),’l’) != s.end()) << endl;
cout << (find(v.begin(),v.end(),4) != v.end()) << endl;
}

Another routine is find_if which is like find except that it doesn’t take a value as its 3rd argument. Instead it needs the name of a predicate – a routine which is given an element and returns true only for elements which fulfill the required condition. This offers more flexibility but before we exploit that, let’s replicate using find_if what the previous example does, dealing with the integer case first.

bool equal_to_4(int it)
{
return it==4;
}

vector<int> v(3);
v[0]=1; v[1]=2; v[2]=3;

cout << (find_if(v.begin(),v.end(), equal_to_4)!= v.end()) << endl;
v[1]=4;
cout << (find_if(v.begin(),v.end(), equal_to_4)!= v.end()) << endl;

find_if finds the first instance. Now we’ll use another standard library routine, count_if, which counts the instances, incrementing the 4th argument accordingly

bool equal_to_4(int it)
{
return it==4;
}

int how_many=0;
vector<int> v(3);
v[0]=1; v[1]=2; v[2]=3;

count_if(v.begin(),v.end(), equal_to_4, how_many);
cout << how_many << endl;
v[1]=4;
how_many=0;
count_if(v.begin(),v.end(), equal_to_4, how_many);
cout << how_many << endl;

It’s now a small step to be able to count how many elements are greater than 2.

bool greater_than_2(int it)
{
return it>2;
}

int how_many=0;
vector<int> v(3);
v[0]=1; v[1]=2; v[2]=3;

count_if(v.begin(),v.end(), greater_than_2, how_many);
cout << how_many << endl;
v[0]=4;
how_many=0;
count_if(v.begin(),v.end(), greater_than_2, how_many);
cout << how_many << endl;

There’s another way to do this using functors. When you create a new class you can define what “+” does for objects of that class. Other operators can be defined too. Objects with “()” defined are called function objects or functors. Here’s a simple example

class more_than_2 {
public:
bool operator() (int val) {return val>2;}
};

which we can use with count_if

count_if(v.begin(),v.end(), more_than_2(), how_many);

Nearly there

Time to take stock. We first used find to look for particular values in collections of elements. We progressed onto using count_if to count the number of elements that match a particular condition. And all without using loops! But on the way we’ve lost some generic behaviour (I’ve silently dropped the string handling). Worse still, if we wanted to count how many values were more than 3, we’d not only have to change the count_if call, but also write another routine greater_than_3. We’d like the predicate to take 2 arguments (the element, and the value we’re comparing it with) but because of strong-typing, count_if would complain (the predicate should take only 1 argument). So what can we do?

When we used templates earlier to write the greater_than routine, a different version of source code was produced (behind the scenes by the compiler) for each new type of argument used. It’s possible to do a similar thing so that functions like our greater_than_2 can be generated on demand. We’ll do this in 2 ways – first using a comparison function of our own, then using a standard routine.

We’ll turn our functor into a template
template <int fixed_val>
class more_than {
public:
bool operator() (int val) {return val>fixed_val;}
};

This is a rather different use of the template idea. Here, different instantiations of the template differ not in the type of the variables, but in the value of an integer. Using more_than<2>() in the code makes the compiler generate the same source code as the above more_than_2. There’s a risk of code bloat here – whenever a new integer value is used, more code is generated – but it does give us a way to pass an argument to the comparison function by using something like

count_if(v.begin(),v.end(), more_than<2>() , how_many);
There’s a standard way to do this which uses similar mechanisms as our more_than does. First the code, then the explanation
#include <functional>
…
int how_many=0;
vector<int> v(3);
v[0]=1; v[1]=2; v[2]=3;

count_if(v.begin(),v.end(),bind2nd(greater<int>(), 0), how_many);
cout << how_many << ” values more than 0″ << endl;
how_many=0;
count_if(v.begin(),v.end(),bind2nd(greater<int>(), 1), how_many);
cout << how_many << ” values more than 1″ << endl;

The count_if call may look bewildering, but even if you don’t want to understand it you can still adapt and use it. For example, if you wanted to count how many floats in a vector were greater than 5.67, you could use

count_if(v.begin(),v.end(),bind2nd(greater<float>(), 5.67), how_many);

But how does it work? Let’s first consider greater. It’s defined in the <functional> header file. It’s a binary functor – something that can be used like a function and takes 2 arguments. bind2nd is an adaptor, a kind of wrapper that in this case lets us use a binary function when a unary function is required. So in this example count_if passes an element to what it thinks is a unary function, which in turn passes this element plus a comparison value (0, 1 or 5.67 in these examples) to a binary function whose return value is given back to count_if.

bind1st and bind2nd differ in the order that they give the arguments to the binary function.

Other Functors

greater is only one of several functors in <functional>. They all take 2 arguments

greater_equal
less
less_equal
greater
not_equal_to
equal_to
modulus
divides
plus
minus
times
logical_and
logical_or
logical_not

They’re all used in the same way. So for example, if you wanted to divide all the floats in a vector by 3, you could use

transform(v.begin(),v.end(),v.begin(),bind2nd(divides<float>(), 3));

Here’s Eratosthenes’ Sieve using few explicit loops but many of the above features

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <numeric>
#include <iterator>

using namespace std;

int main() {
  vector<int> v(100);
  fill(v.begin(), v.end(), 1);
  partial_sum(v.begin(), v.end(),v.begin() ); 
  vector<int>::iterator itnum=v.begin();
  while(true) {
    if (itnum++==v.end())
       break;
    v.erase(remove_if (itnum+1, v.end(), bind2nd(not2(modulus<int>()),*itnum)), v.end()); 
  }

  copy (v.begin(),v.end(), ostream_iterator<int>(cout," ")); 
  cout << endl;
}

Technical Details

The above description glosses over some details.

Both bind1st() and bind2nd() are functions that take as arguments a binary function object and a value, and return, respectively, classes binder1st and binder2nd. The underlying function object must be derived from binary_function.

binder2nd is a function object adaptor: if f is an object of class binder2nd<AdaptableBinaryFunction>, then f(x) returns F(x, c), where F is
an object of class AdaptableBinaryFunction and where c is a constant. Both F and c are passed as arguments to binder2nd’s constructor.

The easiest way to create a binder2nd is not to call the constructor explicitly, but instead to use the helper function bind2nd.

Definitions

Function Objects – When you create a new class you can define what “+” does for objects of
that class. Other operators can be defined too. Objects with “()” defined are called function objects or functors. They’re used in place of pointers to functions as arguments to templated algorithms. Unary function objects take one argument, binary function objects takes two.
Predicate – A function or a function object that returns a boolean (true/false) value or an integer value. They’re often used in algorithms. For example, the find_if algorithm allows you to search for the first element in a sequence that satisfies a particular condition.
Adaptor – something that converts the interface of a class into another interface that clients expect.