views:

263

answers:

2

I am using a set because, i want to use the quick look up property of a sorted container such as a set. I am wondering if I have to use the find member method to get the benefit of a sorted container, or can I also use the static find method in the STL algorithms?

My hunch is that using the static version will use a linear search instead of a binary search like I want.

+7  A: 

You are right that the non-member version does a linear search, while the member version will do a O(log N) search. std::set is optimized for O(log N) insertion, retrieval and deletion.

As a point of definition, the std::find method is not a static function. See here for a description of the various things static can mean in C++.

Eclipse
+1  A: 

This is implementation-dependent as someone might have implemented a partial specialisation for the static 'find' that uses a binary search on sets, but all things considered, the member function version is likely to perform better.

IIRC, Scott Meyers suggests in his book 'Effective STL' to always prefer the member version of common functions like find, swap etc over the non-member functions simply because they are more likely to be an optimal implementation compared to the non-member versions and you normally can rely on the performance advantage of the member version, whereas you cannot always rely on the fact that a partial specialisation for a given function will be present.

Timo Geusch