CODEWITHSUNDEEP
c++dictionaryoverloadingoperator-keyword
user1285674
user1285674

Reputation:

How to correctly overload operator< for use in std::map with my user-defined type?

I have a class called set that is a dynamically allocated array in the inside that acts as a container with the required overloaded operators. This array (1D) stores a (astronomically large, at times) number of integers which I sort with std::sort when the entire set is inserted into this array (much faster than using std::set). These sets are put into std::map where they act as a key to a double, which gets incremented when the std::map already has the set and if the current set is not in the std::map container then it gets inserted with the counter "0". I tried to overload operator< since std::map requires it. But its causing a segmentation fault. The first member of the array (named arr) stores the number of integers in the set aka total array length is arr[0]+1.

The reason why Im not using vector or the new array type is because I run fast out of RAM (64GB), these sets are at size 2^10 to 2^11 at peak moments (generating subsets) so I want to create my own version of a vector with minimum space overhead. 

bool operator<(const set& s1, const set& s2)
{
    if (s1.arr[0] < s2.arr[0])
        return true;
    else if (s1.arr[0] > s2.arr[0])
        return false;

    if (s1.arr[0] == s2.arr[0])
    {
        for (int i = 1; i < s1.arr[0]+1; i++)
        {
            if (s1.arr[i] > s2.arr[i]) return false;
        }
    }
    return true;

}

Upvotes: 0

Views: 3070

Answers (1)

jpalecek
jpalecek

Reputation: 47762

You should change your inner loop comparison akin to your length conparison:

    for (int i = 1; i < s1.arr[0]+1; i++)
    {
        if (s1.arr[i] < s2.arr[i])
            return true;
        else if (s1.arr[i] > s2.arr[i])
            return false;
    }

That way, your comparison operator will implement a strict weak ordering. Your original operator did not, for example, (2 0 2) is incomparable with (2 1 1), (2 1 1) is incomparable with (2 0 3), but (2 0 2) < (2 0 3) which breaks the transitivity of equivalence.

Upvotes: 2

Related Questions