list<OBJECT*>::iterator it;
for(it=lstList.begin();it!=lstList.end();++it)
{
if((*it)->test=true)
//do stuff
}
list<OBJECT*>::iterator it=lstList.begin();
while(it!=lstList.end())
{
if((*it)->test=true)
//do stuff
++it
}
What's the fastest way to find something in an std::list
Author
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:
This method:
Or some other method. I read somewhere about something called std::find, though I don't know how to use it.
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.
More idiomatic, and possibly easier for the compiler to optimize is to use a function object instead of a function pointer.
Or, if you've grabbed the Boost library
#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) );
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.
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.
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) if((*it)->test == true) Otherwise it would always assign and return true.
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:
Check here for more info.
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 stuffCheck here for more info.
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.
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.
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.
Quote:Original post by snk_kidI suppose you could reduce the number of comparsions by applying a binary search. But that hardly makes the search logarithmic.
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.
Quote:Original post by doynaxQuote:Original post by snk_kidI suppose you could reduce the number of comparsions by applying a binary search. But that hardly makes the search logarithmic.
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.
Your wright, number of comparisons is logarithmic with random access iterators number of steps is also logarithmic which std::list iterators are not.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
