Sign in to follow this  
Nuean

Bailing out early with std::algorithms

Recommended Posts

Is there any way to use remove_if (or any other algorithm)and have it quit after n matches? With binding and a functor I can make it stop manipulating the container elements after n matches, but is it destined to finish searching everything even though I got what I wanted in the first half of it? Nuean

Share this post


Link to post
Share on other sites
I think the idea is that you only use something like remove_if when you do want to apply it to every item between two iterators, but what you can't do it just stop when you feel like it.
The built-in algorithms only cover about 95% of things people need to do. If you need the kind of control logic you describe then I'm pretty sure that you're expected to code it up yourself, in this case using the normal erase-loop the performs either an erase, saving the resulting iterator or an increment, each loop, breaking whenever. The built-in stuff is never going to cover everything.

You could always modify your functor to just return a fixed result for all other items once you decide you've got what you want. But that seems like a bad thing to do as it would need to know stuff that it probably has no business knowing.

Share this post


Link to post
Share on other sites
Quote:
Original post by Dmytry
You can bail out with an exception, however that may be or not be inefficient depending to the implementation details.


It's also something to get fired for. This would be prime example for abuse of exceptions.



Quote:
I got what I wanted in the first half of it?


What is it that you wanted? Perhaps there's a different approach to this?

Share this post


Link to post
Share on other sites
Quote:
Original post by Nuean
Is there any way to use remove_if (or any other algorithm)and have it quit after n matches?


Why would you want to do that? I'm having difficulty imagining a situation where "remove the first N things matching a condition from the container" is a valid design requirement.

Share this post


Link to post
Share on other sites
If you're bailing after n matches, that's a different algorithm than remove_if is doing. Just implement it directly. You can make your own generic algorithm if you prefer... just have a second "quit early" test functor.

Share this post


Link to post
Share on other sites
Thank you everyone for the answers! I just implemented a normal iterator loop and got the job done. I have been diving into boost and functors and algorithms quite a bit lately, and I think I was trying to force the problem to be a nail for my new hammer :)

@Sneftel I will look into your suggestion on the side. I never even considered that. It is probably overkill for this little situation, but it's going to be a great learning experience for me regardless.



@Anteus & Zahlman
Basically what I have is a waiting list and an in-progress list. (vector and map actually) each object contains a task, and there is a limit on how many concurrent tasks can be handled. I need to keep the in-progress objects as close to the limit as possible at all times.

So as I go to top off the in-progress map, I know how many tasks I'm allowed to add, so I don't want to waste time searching through 1500 objects in the waiting list when I know I only need say, 75 right now.

the reason I can't just use remove_if on a range of 75, is some objects are active and some are inactive and waiting on a retry timer, and they cant be sorted because the oldest tasks need to go out first.

After typing this out I think I've convinced myself a better approach is to have a third container holding the waiting-on-retry-timer objects. That will make some other parts of code a bit cleaner as well.....hmm

If you guys have another approach to this kind of problem that you think might be better I'd love to hear it. I'm always up for learning something new.


Nuean

Share this post


Link to post
Share on other sites
Quote:
Original post by Nuean

Basically what I have is a waiting list and an in-progress list. (vector and map actually) each object contains a task, and there is a limit on how many concurrent tasks can be handled. I need to keep the in-progress objects as close to the limit as possible at all times.


Multi-threaded task scheduler?

That's a separate domain which has seen quite some attention at all levels. They tend to emphasize as little data movement as possible.

Quote:
75


This is quite a big number. What kind of algorithms process this? Are you sure you need to move this data around, and can't process it in place, simply by specifying array offsets?

Share this post


Link to post
Share on other sites
Quote:
Original post by Nuean
After typing this out I think I've convinced myself a better approach is to have a third container holding the waiting-on-retry-timer objects. That will make some other parts of code a bit cleaner as well.....hmm
I agree, that is probably a good idea. Best of luck with that.

Share this post


Link to post
Share on other sites
I also would love the various STL looping constructs (especially for_each) to allow you to break out of the loop. I always wished the function could just return false to break out of the loop...

Share this post


Link to post
Share on other sites
its completely legitimate and perhaps even necessary to do your own algorithms. scott meyer's makes the point that to use the stl effectively you need to extend the stl <cite needed>. common examples would be for_each_if where you pass a predicate and an action and i dont think stl covers copy_if either which are both generic and useful functionality but ommitted from the std library.

Share this post


Link to post
Share on other sites
Fortunately, this kind of thing is dead simple to implement.

template < typename Iterator, typename F > void for_each_while( const Iterator& begin, const Iterator& end, F f ) {
for ( Iterator i = begin ; i != end ; ++i ) if (!f(*i)) return;
}


(the SC++L uses the postfix _if to mean something other than early bail out, hence my use of _while instead)

For a lot of non reusable things, though, I'd just use BOOST_FOREACH.

BOOST_FOREACH( T& element, elements ) {
...
if ( ... ) break;
}


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