-
std::list question
Just a quickie I'm not sure about.
If I did a linear search (t'is linear, right?) like this:
Code:
/* GetItemByName
*/
Item* ItemManager::GetItemByName( const std::string& name ) const
{
std::list<Item*>::const_iterator it = items.begin();
for ( ; it != items.end(); it++ )
{
Item* i = (*it);
if ( i->name == name ) return i;
}
return 0; // Doesn't exist
}
How does that compare to the std::find() function? Or is it (std::find()) implementation specific?
-
linear not difference
Kuphryn
-
What?
EDIT: I mean, explain. Evidence.
-
I'm not sure how it compares. I'm sure performance wise, find() will be faster. However, list implements a linear (or sequential) search too.
-
Actually nevermind, I did some profiling.
-
And what did you find? They should be roughly the same, although the fact that you are storing pointers might make it more difficult to use find(). I would prefer the algorithm, though, if you can use it.
-
std::find exists for a reason. For starters it's shorter, and less likely to have a bug than hand-rolled code.
Though if you ever find yourself coding a linear search, then there is a very very good chance that you're not using the best container for the job.
-
I assume std:: list is implemented as doubly linked list and I think that your search and find algorithm will have same performace (both will be linear- O(N)),.
-
They were both roughly the same after getting past some difficulties as Daved said. I'm pretty sure I'm using the wrong container: it took about 4 seconds to find the 9999th item (or was it 99999th. Can't remember).
Which would be more appropriate (in case I don't get around to reading it up today)?
-
Maybe it is better to use map/multimap container when inserting elements. Searching will be logarithmic since internally map is a Balanced Binary Tree. So if search/find operation is often use I suggest multimap container.
-
Multimap it is. First, I've got to learn how to use it.
To arms!
Or google.
-
http://www.sgi.com/tech/stl/
It also tells you for most things what the O(n) complexity of the various things are.
-
-
If you are doing all your insertions at once in the beginning, and then searching afterwards, then a vector would probably be even better than a map/multimap/set/multiset. Fill the vector with all your data, then sort it, then use binary_search, lower_bound, and/or upper_bound to find what you are looking for. This will be even better than the map solutions because those keep the data sorted as you are inserting which is a bit slower than sorting it once at the end. In addition, the vector uses less memory overhead than the map solutions.
Another option is the unordered_map/unordered_multimap that will be part of the next standard. You can find an implementation from boost if your library doesn't have one. They're basically hashed maps, which have even faster lookups than the regular map or binary_search.
-
You should put the call to items.end() outside the for loop for best results, i.e.
Code:
std::list<Item*>::const_iterator it = items.begin();
std::list<Item*>::const_iterator end = items.end();
for ( ; it != end; it++ ) {
}