Sign in to follow this  
Amma

[STL] How to use find_if on a pointerbased container?

Recommended Posts

Can someone tell me if how to use find_if ala; struct CTest2 { }; struct CTest { bool Equals( const CTest2& _comparer) const { return false; } }; std::vector<CTest*> g_container; void main() { // How?? std::find_if( g_container.begin(), g_container.end(), &CTest::Equals ); } How can I use the CTest::Equals function if the container, as stated, holds pointers?

Share this post


Link to post
Share on other sites
The Equals function needs to use the same argument type as the template (i.e. a pointer).
bool Equals(const CTest2 *p) const
{
return false;
}

Share this post


Link to post
Share on other sites
You won't be able to use Equals like that because Equals operates on two objects - the object to which the member function belongs and the object passed as an argument (object1.Equals(object2)), but find_if only looks at objects one at a time, which would end up as either object.Equals(?what?) or ?what?.Equals(object).

If you're searching for a specific object then what you want to do is pass the object to compare against to the member function. This can be achieved either by a functor:
class FindTestEquivalentToTest2
:
public std::unary_function< Test const * const, bool >
{

public:

FindTestEquivalentToTest2(Test2 comparisonObject)
:
comparisonObject_(comparisonObject)
{
}
bool operator()(Test const * const object)
{
return object->Equals(comparisonObject_);
}

private:

Test2 comparisonObject_
};

std::find_if(container.begin(), container.end(), FindTestEquivalentToTest2(myTest2Object));

This will find the first Test object in container for which object.Equals(myTest2Object) is true.

Alternatively you can use the boost bind library to write it without the functor:
std::find_if(container.begin(), container.end(), boost::bind(std::mem_fun(&Test::Equals), _1, myTest2Object));

That may look like gobbledeygook. std::mem_fun is an adaptor which allows you to call a member function from a pointer, i.e. it turns object.memberFunction() into object->memberFunction(). Since you have a container of pointers this is needed to make things match up. boost::bind binds arguments to a function and creates a function object. _1 is a placeholder for a parameter which will be passed later. So in this case the boost::bind call turns the function [parameter]->Equals([parameter]) into [parameter]->Equals(myTest2Object). Now the find_if call will call the resulting function object for each pointer in the container, passing it as the missing parameter.

I hope I didn't confuse too much there. I thoroughly recommend boost. It is a set of very powerful libraries. They do take some getting used to (since when did anything worthwhile not require some effort?) but they will help you write much better, cleaner, more correct code.

Enigma

Share this post


Link to post
Share on other sites
Quote:
Original post by Enigma
std::find_if(container.begin(), container.end(), boost::bind(std::mem_fun(&Test::Equals), _1, myTest2Object));

That may look like gobbledeygook. std::mem_fun is an adaptor which allows you to call a member function from a pointer, i.e. it turns object.memberFunction() into object->memberFunction(). Since you have a container of pointers this is needed to make things match up. boost::bind binds arguments to a function and creates a function object. _1 is a placeholder for a parameter which will be passed later. So in this case the boost::bind call turns the function [parameter]->Equals([parameter]) into [parameter]->Equals(myTest2Object). Now the find_if call will call the resulting function object for each pointer in the container, passing it as the missing parameter.


It's not neccessary to use std::mem_fun with boost::bind.

Share this post


Link to post
Share on other sites
Or you can just give up on trying to cram a concept that pretty much requires lambda functions (most of <algorithm> basically) into a language that doesn't support them. I haven't personally tried the boost stuff - it's always seemed like a pretty incredible piece of work but basically a really nasty hack.

Seriously. I would argue that a simple loop is clearer than trying to get find_if (or for_each, etc, etc) to work:

(untested)

std::vector<CTest*>::iterator i;
for (i = g_container.begin(); i != g_container.end(); ++i)
if ( Whatever(*i) )
break;

Share this post


Link to post
Share on other sites
I am inclined to agree with Anon Mike. I know I'm not the world's best programmer but I'm not the worst either, and generally speaking I would rather write out the explicit loop than jump through the hoops required to get these things working in C++.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anon Mike
I haven't personally tried the boost stuff - it's always seemed like a pretty incredible piece of work but basically a really nasty hack.


The only real hacks involved are to do with getting the library working on every C++ compiler possible, all c++ compilers have there peculiarity as none of them implement the standard by 100% and even the bits which are implementated it may not be implementated correctly resulting in wrong behaviour.

Quote:
Original post by Anon Mike
Seriously. I would argue that a simple loop is clearer than trying to get find_if (or for_each, etc, etc) to work:

(untested)

std::vector<CTest*>::iterator i;
for (i = g_container.begin(); i != g_container.end(); ++i)
if ( Whatever(*i) )
break;


Not an attack on you but your code already shows two reasons to use algorithms over hand-written explicit loop code, arguments for algorithms:

1. begin/end are typically overloaded by constantness thus when using algorithms depending on the context the compiler selects const_iterator or iterator automatically.

2. Your code doesn't take advantage of the fact your using random accessible iterators, it has virtually no chance of optimizing the loop (loop unrolling), most algorithms do take advantage of this fact by doing compile-time tag dispatching and using a different method of iteration instead of the idiomatic "itr != end; ++itr".

3. Some operations can be done more efficiently with containers of POD-types, for example using memmove/memcpy, when such a case exists algorithms take advantage of this fact by doing compile-time type dispatching and using the more efficient method.

4. algorithms supports the "Liskov Substitution Principle" because of iterators and static compile-time polymorphism that templates can give you.

5. In most cases algorithms do make code more concise and less prone to bugs.

6. There are more but i've forgotten them at the moment [grin].

The best example of this is std::copy, not only does it take advantage of the kind of iterator used, it also typically dispatches to use memmove for POD-types instead of the more generic copy method, you don't need to worry about it, its all automated for you, efficient and mostly inlined away.

Share this post


Link to post
Share on other sites
This sort of thing is a great object lesson on the weaknesses of C++ as a multiparadigm language. The lack of support for lambdas leads to either a hideously complicated grouping of bind1sts, composes, and mem_fun_refs, or a functor whose operation is separated by dozens of lines of code from the point of use. (Or boost::lambda; if you ever feel like going prematurely bald, read the source to boost::lambda... the sorts of hoops they have to jump through to get that syntax to [sometimes] work boggle the mind.)

The tragedy of all this is that it forces the programmer to choose between different forms of unreadability.

Share this post


Link to post
Share on other sites
snk_kid - you're absolutely right that using <algorithm> is the way to go when it can be done easily. The problem is that for a large percentage of the cases (in my experience anyway) it's not easy. The line-noise that results in trying to get it to work is just asking for bugs. And god help you if an entry-level new-hire who isn't an expert C++ person has to do maintenance.

It's not STL's fault. C++ was just not designed for these scenarios. Boost presumably makes it better but I don't really know.

Share this post


Link to post
Share on other sites
Quote:
Original post by Anon Mike
Or you can just give up on trying to cram a concept that pretty much requires lambda functions (most of <algorithm> basically) into a language that doesn't support them. I haven't personally tried the boost stuff - it's always seemed like a pretty incredible piece of work but basically a really nasty hack.

Seriously. I would argue that a simple loop is clearer than trying to get find_if (or for_each, etc, etc) to work:

(untested)

std::vector<CTest*>::iterator i;
for (i = g_container.begin(); i != g_container.end(); ++i)
if ( Whatever(*i) )
break;


Actually, that one's pretty easy:

struct bad_test : std::exception
{
bad_test() throw() {}
~bad_test() throw() {}
const char * what() const throw() {
return "Bad test";
}
};

try {
std::for_each( container.begin() , container.end()
, succeed_or_throw< bad_test >( std::ptr_fun( & Whatever ) )
);
}
catch ( bad_test ) {
//...
}




Of course, it uses exceptions, and in this case a non standard library functor (although it's not so bad and can be reused...)

Here's an example succeed_or_throw that compiles this example, although a truely reusable version should have a predicate argument to allow for another meaning besides "if ( result ) == success".

template < typename exception_t , typename function_t >
struct succeed_or_throw_f {
typedef exception_t exception_type;
typedef typename function_t::argument_type argument_type;
typedef typename function_t::result_type result_type;
private:
function_t function;
public:
succeed_or_throw_f( function_t function )
: function( function )
{
}

result_type operator()( argument_type argument ) throw( exception_type ) {
result_type result = function( argument );
if ( result ) return result;
else throw exception_type();
}
};

template < typename exception_t , typename function_t >
succeed_or_throw_f< exception_t , function_t > succeed_or_throw( function_t function )
{
return succeed_or_throw_f< exception_t , function_t >( function );
}



If you ask me, functors are to C++ as lambdas are to $FAVORITE_LANG_WITH_LAMBDA. Yes, they're more verbose and you have to write them yourself, but at the end of the day, this isn't stuff that I myself particularly mind, since they're reusable, and I can type 80WPM* :-).


* this includes correcting errors - I usually get 35-40 when typing gibberish instead of meaningfull sentances or the like.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this