Kai-Uwe Bux
12/5/2008 9:03:00 PM
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