This article has been completely rewritten since I first published it this morning, and posted my question on the Channel9 forums.

So yesterday I was tinkering around with the Standard Template Library (STL), trying to learn better ‘generic’ practices. But ended up getting stuck trying to solve a problem that occurs when you try to create a Predicate of string::compare() - the adaptors end up trying to create a reference of a reference, and the Compiler effectively says, no, go away.

OK, now some of you are probably saying: “Um, string ? Why are trying to use string::compare, just use the built-in operators. They have overloads”.

Well, as tends to happen with these types of things, it started innocently enough, but was rooted in a stupid mistake. I was converting a Microsoft (ptr_fun) sample which used a vector of char pointers. I thought, that was too old-school, and modified it to use std::string instead. The problem was that I forgot to rename the #include <cstring> to <string>, as was kindly pointed out to me by Sven. Thanks Sven.

This had the curious effect of not defining various parts of std::basic_string, such that Functors like equal_to failed to compile with complaints about operator==. Anyway, this lead to me trying to workaround the ‘missing’ operators by attempting to construct a suitable Predicate calling a member function, in this case string::compare().

Anyway, having been suitably embarrassed, I'm still curious about whether it can be done. Say, for example, because I need to use a Class that does define Iterators, but not a full compliment of operator overloads.

So let's just start off with the definition of find_if, and then go into to some of the concepts behind what I'm trying to do. Having said that, I suppose I should point out that I'm not an Academic, so I'm probably going to mess up the terminology - but let's give it a crack, anyway...

Here's the basic definition of find_if:

template<class _InIt, class _Pr> inline
    _InIt find_if(_InIt _First, _InIt _Last, _Pr _Pred)
    { ...

find_if uses two generic classes: an Input Iterator and a Predicate. OK, an Iterator is pretty easy to understand, but what is a Predicate ?

Well in this context, it's a Function that is passed an “item” (dereferenced Iterator) and returns a boolean result. So what find_if does is iterate over a range that you specify via the _First and _Last Input Iterators, and it continues until it either reaches the end of the range, or the Predicate _Pred returns true.

When I was first introduced to this algorithm, the predicate would usually be an ordinary C++ function call. That made it easy to understand, but from a practical point of view, a PITA to use.

Functors
At this point, if you've been lucky, you'll have next been introduced to Functors. A Functor is basically an object that has defined (overloaded) the function operator - operator(). Because of this, a Functor (object) can basically be used as though you were calling an ordinary C++ function, with a twist:

  int a=2, b=1;
  if ( std::greater<int>()(a, b) )
    cout << "a is Greater than b." << endl;

Notice how in the if statement, I have to explicitly specify the brackets () before the parameter list. That's in addition to explicitly specifying the “Type” Template parameter - <int> in this case.

Binding
The next thing is Binding. STL has two Binders: bind1st and bind2nd. Actually, these are helpers for binder1st and binder2nd, but you wouldn't normally use these, directly.

A Binder basically allows you bind one of the parameters of a Function (or Functor), effectively changing a two parameter Function call into single parameter one: bind1st statically binds to the first parameter, and bind2nd with the second parameter.

  int c=2, d=1;
  std::binder1st<std::greater<int> > b1fn = bind1st(std::greater<int>(), c);
  if ( b1fn(d) )  // Equivalent to std::greater<int>()(c, d)
    cout << "c is Greater then d." << endl;

Bringing it all together
Now this is where I'm having trouble. In the following code, v1 is a vector of string, where each item is a word.

1. & 2. After I setup v1, I print out each word using a for loop and Iterators.

Next, I tried searching for the word “pearly” using various techniques.

3. Searching using find. Once I had the correct header included, it worked fine.

4. Using find_if and the equal_to Functor, adapted as a Predicate using bind2nd.

5. This is where I run into the reference to reference problem. I attempt to create a Predicate using mem_fun_ref and bind2nd., but I can't get it to compile:

error C2529: '_Right' : reference to reference is illegal C:\Program Files\Microsoft Visual Studio 8\VC\include\functional    312

From that point on, I tried breaking up the Predicate into it's various concepts, in the hopes of trying to locate where it was failing.

6. The first thing was trying to get mem_fun_ref working using a parameterless function. Nothing too spectacular here, though I chose to include the explicit call (6.3).

7. Finally, I try to get mem_fun_ref working using a single-parametered function - compare. You'll notice that I could not get the implicit call (7.2) to work. It fails with errors about not being able to deduce the template parameters - compare() has 6 overloads.

This therefore means that you must use explicit calls, as shown with 7.3 and 7.4.

All in all, it's been an interesting exercise. My original hopes of producing more easily consumed source code has quickly evaporated with the realisation that we must use an explicit call - trying to create a Predicate from a member function worsens the consumability, quite considerably.

However, I'd still like to see whether the reference from reference issue can be solved, even though now it's just an academic one.

The following code is for a console program:

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

int main( )
{
  using namespace std;

  // 1. Setup and tinker with a vector of string.
  vector <std::string>            v1;
  vector <std::string>::iterator  Iter1, RIter;
  
  v1.push_back ( "Open" );
  v1.push_back ( "up" );
  v1.push_back ( "the" );
  v1.push_back ( "pearly" );
  v1.push_back ( "gates" );

  // 2. Let's start off by printing out the original sequence.
  cout << "Original sequence contains: " ;
  for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
    cout << Iter1->c_str() << " ";
  cout << endl;

  ///////////////////////////////////////////////////////////////////////////
  // Now lets try various ways of searching for "pearly"
  ///////////////////////////////////////////////////////////////////////////
  
  const string kSRCH("pearly");
  
  // 3. use std::find
  RIter = std::find(v1.begin(), v1.end(), kSRCH );
  if ( RIter != v1.end() )
    cout << "using std::find ->" << *RIter << endl;

  // 4. use equal_to Functor for predicate.
  RIter = find_if( v1.begin(), v1.end(), 
    bind2nd ( equal_to<string>(), kSRCH )
    );  
  if ( RIter != v1.end() )
    cout << "using std::find_if and equal_to Functor ->" << *RIter << endl;

  // 5. Now assume the object (std::string) doesn't have the appropriate operator
  // overloads, but does have a compare() member. DOES NOT COMPILE !.
  RIter = find_if( v1.begin(), v1.end(), 
    bind2nd (mem_fun_ref<int, string, const string&>(&string::compare), string("pearly") )
    );  
  if ( RIter != v1.end() )
    cout << "using std::find_if and mem_func_ref ->" << *RIter << endl;
  
  // 6. OK, the above fails. So lets break the above predicate down, and see
  //    what we can get to compile. Well start with a parameterless member
  //    function (method) call. string::size().
  size_t z = v1[0].size();  // 6.1 Simulate an iteration, where an item is passed in.
  z = mem_fun_ref(&string::size)(v1[0]);                            // 6.2 implicit.
  z = mem_fun_ref<string::size_type, string>(&string::size)(v1[0]); // 6.3 explicit.

  // 7. Now let's try single parametered member function (method) function.
  //    string::compare().
  v1[0].compare(kSRCH);   // 7.1 Simulate a single iteration, again.
  mem_fun_ref(&string::compare)(v1[0], kSRCH); // 7.2 Doesn't compile: can't deduce template argument.
  mem_fun_ref<int, string, const string&>(&string::compare)(v1[0], "pearly" );  // 7.3 explicit 1
  mem_fun_ref<int, string, const string&>(&string::compare)(v1[0], kSRCH );     // 7.4 explicit 2

  // Done.
  getchar();
}

Just to add another data point, I tried compiling this under Ubuntu Linux 7.10 with GCC 4.1.3, and it fails as well (manually edited by me):

/usr/include/c++/4.1.3/bits/stl_function.h: In instantiation of 
  ‘std::binder2nd
  <
    std::const_mem_fun1_ref_t
    <
      int,
      std::basic_string
      <
        char,
        std::char_traits,
        std::allocator 
      >,
      const std::string&
    >
  >’:
  stl_mem_fun_ref_01.cpp:48: instantiated from here /usr/include/c++/4.1.3/bits/stl_function.h:435:
  error: forming reference to reference type ‘const std::string&’
  
/usr/include/c++/4.1.3/bits/stl_function.h: In function 
  ‘std::binder2nd<_Operation> std::bind2nd(const _Operation&, const _Tp&) 
  [
    with _Operation = std::const_mem_fun1_ref_t
    <
      int,
      std::basic_string
      <
        char,
        std::char_traits,
        std::allocator
      >,
      const std::string&
    >,
    _Tp = std::string
  ]’:
  stl_mem_fun_ref_01.cpp:48:  instantiated from here /usr/include/c++/4.1.3/bits/stl_function.h:455:
  error: no matching function for call to 
  ‘std::binder2nd
  <
    std::const_mem_fun1_ref_t
    <
      int,
      std::basic_string
      <
        char,
        std::char_traits,
        std::allocator
      >,
      const std::string&
    >
  >::binder2nd
  (
    const std::const_mem_fun1_ref_t
    <
      int,
      std::basic_string
      <
        char,
        std::char_traits,
        std::allocator
      >,
      const std::string&
    >&,
    const std::basic_string
    <
      char,
      std::char_traits,
      std::allocator
    >&
  )’
  /usr/include/c++/4.1.3/bits/stl_function.h:429:
  note: candidates are:
    std::binder2nd
    <
      std::const_mem_fun1_ref_t
      <
        int,
        std::basic_string
        <
          char,
          std::char_traits,
          std::allocator
        >,
        const std::string&
      >
    >::binder2nd
    (
      const std::binder2nd
      <
        std::const_mem_fun1_ref_t
        <
          int,
          std::basic_string
          <
            char,
            std::char_traits,
            std::allocator
          >,
          const std::string&
        >
      >&
    )