Re: Ranking algorithm

[Yannick Tremblay]

In article <48***********************@reader4.news.tin.it>,
Giuliano Bertoletti <gb******@libero.itwrote:

>
Good. It seems to be working.

I just have to be carefull when defining the < operator since it has to
correctly handle different items with the same score.

Correctly: operator< should return false for two items that have the
same score.

So if a.score == b.score:

a < b = false
a b = false
a <= b = true
a >= b = true

One of < or is perfectly sufficient for sorting anything efficiently.

>For example:

======================= cut =======================

class CItem {
public:
char name[20];
int score;

public:
bool operator<(const CItem &I) const
{
// if i were to compare only scores, items with the same
// score would just overwrite one another.

if(score != I.score) return score < I.score;

return strcmp(name,I.name) < 0;
Pointless.
You are artificially sorting on "name" which is not in your
requirements. You may as well just keep the first one found.
You are adding one comparison to your critical loop
which if M >N is likely to have more effect than any efficiency
issue discussed aboutstd::set.

Just use the correct operator in your loop.

Want the N smallest:

if( current_item < current_stored_max )
{
// store in set
// resize set to N
// current_stored_max = get current max from set
}