Re: Speeding up access to STL vectors?
Steve555 wrote:
On 5 Dec, 09:31, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
Steve555 wrote:
Hi
My vector ( ? typedef vector<movieRatingPair*> ratingsV ? ?) ?contains
this struct:
typedef struct{
unsigned short ? ? ? ?movieID;
unsigned short ? ? ? ?rating;
} movieRatingPair;
a) You can ditch the typedef:
struct movieRatingPair {
unsigned short movieID;
unsigned short rating;
};
will do.
b) Is there a reason to use vector<movieRatingPair*> instead of
vector<movieRatingPair>? Note that dynamic allocation of objects usually
has some overhead: (1) the pointer (2) some size information about the
allocated object. You might end up using 12 bytes (4 in the pointer and 8
in the pointee) instead of 4 (which is what two unsigned shorts might
give you, but that is platform specific).
...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.
Provide a functor to compare movieRatingPair (or movieRatingPair*) by the
movieID. Then, sort the vector using std::sort() and then test for
entries with std::binary_search(). You can also find iterators to the
entries with std::lower_bound() and std::upper_bound().
[snip]
Best
Kai-Uwe Bux
Thanks Kai but I'm completely lost with getting binary_search to work
with a vector containing structs. They are already sorted upon
creation, so I didn't understand how re-sorting them would help.
It wouldn't. I missed the part about the vector being sorted already.
Here is a bit of code that might help you:
#include <vector>
#include <algorithm>
#include <cassert>
struct rating {
unsigned short ID;
unsigned short value;
};
rating make_rating ( unsigned short id, unsigned short val ) {
rating result;
result.ID = id;
result.value = val;
return ( result );
}
bool compare_by_ID ( rating lhs, rating rhs ) {
return ( lhs.ID < rhs.ID );
}
int main ( void ) {
std::vector< rating > r;
r.push_back( make_rating( 1, 23 ) );
r.push_back( make_rating( 13, 10 ) );
r.push_back( make_rating( 24, 1 ) );
assert( std::binary_search( r.begin(), r.end(),
make_rating( 13, 0 ), &compare_by_ID ) );
assert( ! std::binary_search( r.begin(), r.end(),
make_rating( 10, 0 ), &compare_by_ID ) );
}
Best
Kai-Uwe Bux