Using comparator for STL set

Question

Check the following code:

string toLowerCase(const string& str) {
    string res(str);
    int i;

    for (i = 0; i < (int) res.size(); i++)
        res[i] = (char) tolower(res[i]);

    return res;
}

class LeagueComparator
{
public:
    bool operator()(const string& s1, const string& s2)
    {
        return toLowerCase(s1) < toLowerCase(s2);
    }
};

int main()
{
    set<string, LeagueComparator> leagues;
    set<string, LeagueComparator>::iterator iter;

    leagues.insert("BLeague");
    leagues.insert("aLeague");    // leagues = {"aLeague", "BLeague"}
    leagues.insert("ALeague");

    for (iter = leagues.begin(); iter != leagues.end(); iter++)
        cout << *iter << endl;

    return 0;
}

The output is:

aLeague
BLeague

which is shocking to me. I thought (and expecting) the output would be:

aLeague
ALeague
BLeague

Before the execution of leagues.insert("ALeague");, the leagues contains "aLeague" and "BLeague". My question is, while executing leagues.insert("ALeague"); why the machine treats "ALeague" == "aleague"? According to my understanding, there is no element "ALeague" in leagues. So "ALeague" should be inserted into leagues. The comparator should determine where to put "ALeague".

Thanks in advance.

PS: Please don't hit me for using C style cast. :P I'm too lazy to type static_cast.

Answer 1

Given the comparator you provided, "ALeague" is indeed equivalent "aLeague".

Given two values, x and y, and a less-than comparator z:

• If z(x, y) is true, then x is less than y
• If z(y, x) is true, then y is less than x
• If neither is true, then x is equivalent to y
• If both are true, then you have a broken comparator.

Answer 2

Your comparator, thanks to the toLowerCase, says that "aLeague" == "ALeague". Since (according to your comparator) "aLeague" < "ALeague" == false and "ALeague" < "aLeague" == false, they must be equivalent. And inserting an equivalent element into a set doesn't do anything.

Answer 3

When you insert any value to a set, the object checks to see whether it already contains that value. Your LeagueComparator object compares ALeague with the other two values already in the set. It determines that the existing value aLeague is neither greater than nor less than the proposed new entry (ALeague), so they must be equal, and so it doesn't proceed with the insert. The set remains with just two elements. That's the whole point of providing a customer comparison object, so you can control how the set determines whether two elements match.

Answer 4

Replace your LeagueComparator with

class LeagueComparator
{
public:
    bool operator()(const string& s1, const string& s2)
    {
        return toLowerCase(s1) < toLowerCase(s2)   ||  
               !(toLowerCase(s2) < toLowerCase(s1))  &&  s1 < s2;
    }
};