How To Optimize This find_if Code?

Question

I have function to check if a string contains only alphanumeric and underscore character...

inline bool IsValidChar(char x) 
{ 
    return (isalnum(x) || (x == '_')); 
} 

My find_if code is:

if(find_if(str.begin(), str.end(), IsValidChar) != str.end()) 
{ 
    ... 
} 

I just want to remove the IsValidChar function and directly put it's contents in the find_if line of code..

Answer 1

You're basically looking for C++0x lambda expressions:

if (find_if(str.begin(), str.end(),
    [](char x) { return (isalnum(x) || x == '_'); })
    != str.end()) {
    // Do something.
} 

Answer 2

Frédéric Hamidi gave you a good example of how to use a lambda expression to do what you literally asked. However, the title of the question is "How To Optimize This find_if Code" (emphasis mine). The performance difference between the anonymous function and the named function is going to be negligible (hopefully zero!). Ideally either version can be fully inlined (assuming find_if is inline) and even the slight differences between a lambda expression and a named function are irrelevant.

If (and that's a big if) you have profiled your code and find that this expression is the root of a performance bottleneck, then you would want to explore another algorithm for getting the same result. Since this is such a simple test (and unlikely to simplify further) you'd need to look at how you could make this test less frequently at a higher level.

Answer 3

Standard C++

A Standard-C++ approach starts with the <functional> header, but it doesn't provide everything needed. We must or two predicate conditions, and though SGI's STL (and hence GCC) and others provide it as an extension called "compose2", if your compiler lacks such a function then you can copy the implementation from (and read about it at) http://accu.org/index.php/journals/443.

With compose2, you can write:

#include <functional>
#include <ext/functional> // where GNU g++ hides its compose2

find_if(str.begin(), str.end(),
        __gnu_cxx::compose2(
            std::logical_or<bool>(),
            std::ptr_fun(isalnum),
            std::bind1st(std::equal_to<int>(), '_')));

It's all very logical, but verbose and slow to read.

Using the BOOST library

The leading non-Standard C++ "toolbox" library - BOOST - provides a variety of alternatives. I'll illustrate Lambda - see http://www.boost.org/doc/libs/1_44_0/doc/html/lambda.html.

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>
...
    find_if(str.begin(), str.end(),
            bind(isalnum, boost::lambda::_1) || boost::lambda::_1 == '_');

If you prefer:

...
using namespace boost::lambda;
...
            bind(isalnum, _1) || _1 == '_');

C++0x

FWIW, the next C++ Standard (due out real soon now, and already partially implemented in very recent versions of several popular compilers) will provide better inbuilt support for lambdas:

...
            [](char x) { return isalnum(x) || x == '_'; });

Discussion

Given how much trouble all this is, you must be wondering whether it's best to stick to what you started with. Probably. Still, these lambda things do help if you've got a lot of places you want to use them and the predicates are different in each.

Answer 4

You could do this:

if(str.find_first_not_of("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789_")!=std::string::npos)
{
    ...
}

I really don't think this is any clearer in this case. (This approach is cleanest if you have smaller or more arbitrary char sets.) It gets rid of the extra function, though. And, if it's important, it is compatible with the previous C++ standard.

Answer 5

The main problem I see with this as it stands is that it locates the first valid character.

Seems like you need to reverse the sense of the predicate if you want to rule out invalid data in the string.

inline bool IsNotValidChar(char x) 
{ 
    return (!isalnum(x) && (x != '_')); 
}

if(find_if(str.begin(), str.end(), IsNotValidChar) != str.end()) 
{ 
    ... 
} 

As others have noted, lambda notation makes this more concise but not necessarily cleaner, and definitely not faster.