Sign in to follow this  

What's the fastest way to find something in an std::list

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Let's say I have a list of objects (struct that contains a bool test). I want to go through the list and find an object where the bool test=true. What's the fastest way to do this. Is is this method:
list<OBJECT*>::iterator it;    

for(it=lstList.begin();it!=lstList.end();++it)
{
    if((*it)->test=true)
    //do stuff
}


This method:
list<OBJECT*>::iterator it=lstList.begin();
while(it!=lstList.end())
{
    if((*it)->test=true)
    //do stuff
    ++it
}


Or some other method. I read somewhere about something called std::find, though I don't know how to use it.

Share this post


Link to post
Share on other sites
Well, in all cases, it boils down to walking down the list until you find an object which matches your predicate, so it's not like there is much room for algorithmic magic. The 'fastest' solution will largely depend on your compiler.


#include <list>
#include <algorithm>

bool test_pred(const OBJECT* const obj) { return obj->test; }

std::list<OBJECT*>::iterator it;

it = std::find_if( lstList.begin(), lstList.end(), test_pred);




More idiomatic, and possibly easier for the compiler to optimize is to use a function object instead of a function pointer.


#include <list>
#include <algorithm>
#include <functional>

struct test_pred :
std::unary_function<OBJECT*, bool>
{
bool operator()(const OBJECT* const obj) const
{
return obj->test;
}
};

std::list<OBJECT*>::iterator it;

it = std::find_if( lstList.begin(), lstList.end(), test_pred());




Or, if you've grabbed the Boost library


#include <list>
#include <algorithm>
#include <boost/mem_fn.hpp>

std::list<OBJECT*>::iterator it;
it = std::find_if( lstList.begin(), lstList.end(), boost::mem_fn(&OBJECT::test) );


Share this post


Link to post
Share on other sites
AFAIK know finding something in a std::list<> will always be linear, and in fact that's the way std::find() is implemented. With arrays you can use lower_bound() or something of that sort, although that requires your objects to be sorted in some meaningful way.

Actually, I'd think finding an object in pretty much any container by a simple boolean value would pretty much always be linear, as there's no meaningful way to sort the objects. In cases like this, I usually have two lists (or vectors or stacks), one for 'true' and one for 'false', and just pop one off the appropriate list. This makes sense for, say, 'active' and 'inactive' entities, but may not work for your case.

Share this post


Link to post
Share on other sites
Quote:
Original post by utilae
Let's say I have a list of objects (struct that contains a bool test). I want to go through the list and find an object where the bool test=true. What's the fastest way to do this.

Is is this method:
*** Source Snippet Removed ***

This method:
*** Source Snippet Removed ***

Or some other method. I read somewhere about something called std::find, though I don't know how to use it.


I also would like to point out not to use
 if((*it)->test=true) 
But rather
 if((*it)->test == true) 


Otherwise it would always assign and return true.

Share this post


Link to post
Share on other sites
Either of those loops will run just as fast, as they're pretty much the same thing.

The STL function you could use instead is std::find_if. It takes a first and last iterator, and a predicate object to test with. Using it would look like:


struct check_test (
bool operator() (const TOBJECT* obj) const {
return obj->test == true;
}
};

list<OBJECT*>::iterator iter = std::find_if(lstList.begin(),lstList.end(),check_test());
if (iter != lstList.end())
// do stuff



Check here for more info.

Share this post


Link to post
Share on other sites
You'll gain very little from optimising a list search, since the datastructure itself isn't adapted for fast searches. Any algorithm you choose will have to search through large parts of the list to find random elements.

To gain any performance at all you should consider switching to something else (such as a sorted vector, hash table or binary tree) or complement it with some additional datastructure for the task.
The only method I can think of that doesn't involve switching datastructures or consume more space would be to move the last accessed element to the head of the list and thus (in some cases) finding it faster the next time.

Share this post


Link to post
Share on other sites
You can use a sorted std::list with STL algorithms lower_bound, upper_bound, equal_range, binary_search, to obtain logarithmic time but you need to have meaning-full sort & search criteria.

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
You can use a sorted std::list with STL algorithms lower_bound, upper_bound, equal_range, binary_search, to obtain logarithmic time but you need to have meaning-full sort & search criteria.
I suppose you could reduce the number of comparsions by applying a binary search. But that hardly makes the search logarithmic.

Share this post


Link to post
Share on other sites
Quote:
Original post by doynax
Quote:
Original post by snk_kid
You can use a sorted std::list with STL algorithms lower_bound, upper_bound, equal_range, binary_search, to obtain logarithmic time but you need to have meaning-full sort & search criteria.
I suppose you could reduce the number of comparsions by applying a binary search. But that hardly makes the search logarithmic.


Your wright, number of comparisons is logarithmic with random access iterators number of steps is also logarithmic which std::list iterators are not.

Share this post


Link to post
Share on other sites

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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