Re: Ranking algorithm
In article <48fccfcf$0$18158$4fafbaef@reader3.news.tin.it>,
Giuliano Bertoletti <gbe32241@libero.it> wrote:
Yannick Tremblay ha scritto:
In article <48f775a6$0$41660$4fafbaef@reader4.news.tin.it>,
Correctly: operator< should return false for two items that have the
same score.
[snip]
One of < or > is perfectly sufficient for sorting anything efficiently.
[snip]
Pointless.
You are artificially sorting on "name" which is not in your
requirements. You may as well just keep the first one found.
No, that was exactly what confused me in the first place and led me to
ask here.
Suppose I have "Joe" and "Nick" which both score 20.
If I were simply to define the operator as:
bool operator<(const CItem &I) const
{
return score < I.score;
}
then the library would have no way of knowing that "Joe" and "Nick" are
different items scoring the same and rank them separately.
Since an std::set cannot hold multiple equal items, either "Joe"
overwrites "Nick" or "Nick" overwrites "Joe" depending on the order in
which they're seen, eitherway yielding only one player with a score of
20 in the final rank and that's of course not what I want.
Yes, that's correct with std::set, you need to use std::multiset.
Check the difference while using set vs multiset in asmall sample
program. E.g.:
#include <set>
#include <string>
#include <iostream>
struct Item
{
Item(int valueIn, std::string const nameIn):value(valueIn), name(nameIn) {};
int value;
std::string name;
bool operator<(Item const & rhs) const
{
return value < rhs.value;
}
};
std::ostream & operator<<(std::ostream & outStream, Item const & item )
{
return outStream << "Value = " << item.value << " Name = " << item.name;
}
typedef std::multiset<Item> coll_t;
//typedef std::set<Item> coll_t;
int main()
{
coll_t theSet;
theSet.insert(Item(20, "John20"));
theSet.insert(Item(12, "Alan12"));
theSet.insert(Item(20, "Annie20"));
theSet.insert(Item(10, "Lise10"));
theSet.insert(Item(40, "Isaac40"));
theSet.insert(Item(30, "Steve30"));
theSet.insert(Item(20, "John20"));
for(coll_t::const_iterator it = theSet.begin();
it != theSet.end(); ++it)
{
std::cout << (*it) << std::endl;
}
return 0;
}
With multiset, all Item object are stored, with set, only the first
encountered Item object for a particular value is stored. So multiset
with a normal operator< checking only value would meet your needs.
Just enclose the multiset in a class that compare with the current max and
keep the size of the multiset to the desired size.
Anyway, I'd be insulted if I'd score the same thing as you to be
ranked lower just because my name starts by 'Y'. That's just unfair,
isn't it? :-)
Yannick