Re: searching in set vs. vector

From:

Alan Johnson <alanwj@no.spam.stanford.edu>

Newsgroups:

comp.lang.c++.moderated

Date:

30 Apr 2006 11:03:44 -0400

Message-ID:

<e326q3$pj9$1@news.Stanford.EDU>

Mehturt@gmail.com wrote:

I have found an article with 50 STL tips.. I am wondering about tip
#23:

-- snip --
23) Consider replacing associative containers with sorted vectors.

Associative containers are implemented as balanced binary search trees,
good for a mix of insertions, erasures and lookups. If insertions are
mostly separate from lookups, you can use vectors which would take less
memory, sort it and use lookups at a cost of log n.
-- snip --

I have made a test on GNU/Linux using g++ 4.0 comparing searches in
std::vector<int> and std::set<int> and it seems searches in sorted
vector are faster only for small sizes (about 10 elements), for
anything bigger std::set<int> is much faster (the more elements, the
greater the difference). I mean I'm using std::set<> and std::map<>
not only to store sorted data, but only to have fast searches in the
container.. The memory usage is not really a case for me..

So perhaps somebody can explain this tip a bit further.. I can post the
code I did for testing - if that is relevant..
Thanks

How are you searching the vector? From your tests it sounds like you
are using a linear search, for example a simple loop or std::find. The
tip you cite mentions "use lookups at a cost of log n", implying that
you should use a binary search. The STL way of doing this is to use
std::lower_bound or std::upper_bound.

--
Alan Johnson

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]