Re: Speeding up access to STL vectors?
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 dealing
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