Re: Speeding up access to STL vectors?

From:

peter koch <peter.koch.larsen@gmail.com>

Newsgroups:

comp.lang.c++

Date:

Fri, 5 Dec 2008 12:57:32 -0800 (PST)

Message-ID:

<4a0552cf-b0cd-4de8-ade8-5e35458eb3a7@s9g2000prg.googlegroups.com>

On 5 Dec., 21:44, Steve555 <foursh...@btinternet.com> wrote:

On 5 Dec, 19:15, peter koch <peter.koch.lar...@gmail.com> wrote:

On 5 Dec., 10:09, Steve555 <foursh...@btinternet.com> wrote:

Hi

My vector ( typedef vector<movieRatingPair*> ratingsV =

) contains

Why do you have a pointer of vectors? You probably should have a
vector of MovieRatingPair.

this struct:

typedef struct{
unsigned short movieID;
unsigned short rating;

} movieRatingPair;

Why do you use a C-notation? In C++ the preferred notation is
struct movieRatingPair
{
...};

...and on average will contain 200 such structs;
The structs are always stored in the vector in ascending order of
movieID.

I need to find a quick way to check if the vector contains a specific
movieID. I can not use a map instead of a vector, because the extra
few bytes they use creates a problem.(*)

Simply iterating through the vector is proving a bit slow; I guess I
can write some binary search code, but just wanted to check I wasn't
re-inventing the wheel, or simply missing a much better way of dealin=

with the whole thing.

There is std::binary_search, std::lower_bound and std::upper_bound for
that. Using that, having much better cache-coherency when searching
values instead of pointers and using far less memory (when not newing
your elements) should combine to give you a rather huge speed-up (I
would estimate a factor of more than ten).

/Peter

Thanks, I like your estimate! Unfortunately I've got really stuck on
figuring out how to use binary_search
with a vector that contains structs. Any hints anyone can give me
using my data types would be greatly appreciated.

One way would be to make your structs comparable, but to me this seems
wrong as you seemingly only want to compare part of the struct.

So write a function or a functor that compares the movieID's of two
movieRatingPairs. The functor way would be:

struct lessmovieIDs
{
   bool operator()(movieRatingPair const& lhs,movieRatingPair const&
rhs)
   // returns true iff the movieID of lhs is less than the movieID of
rhs
   {
      ...
   }
};

/Peter