Writing custom std::set comparator for object containing array in c++

Question

I am trying to make my question simple here. I have one structure with int array as member variable.

struct elem
{
    elem (int a, int b, int c) {id[0]=a; id[1]=b; id[2]=c;}
    int id[3];
};

I want to put elem pointers into std::set and I want to use find() to search specific object from that set later, so I want to provide custom comparator to this std::set.

struct compare
{
    bool operator() (elem *one, elem *two )
    {
            // logic 
    }
};

int main(int argc, char* argv[])
{
    std::set< elem *, compare> elemSet;
    std::set< elem *, compare>::iterator itr;

    elem ob1(2,5,9), ob2(5,9,7), ob3(4,3,7);

    elemSet.insert(&ob1);
    elemSet.insert(&ob2);
    elemSet.insert(&ob3);

    elem temp(4,3,7);
    itr = elemSet.find(&temp);

    if(itr != elemSet.end())
    {
        cout << endl << (*itr)->id[0] << " " << (*itr)->id[1] << " " << (*itr)->id[2]; 
    }

    return 0;
}

Can you please help me with logic for comparator? Is there any generic logic for array of any size?

What kind of help do you need? Only you should know what the operator less should do for your class — BЈовић, Nov 29 '11 at 09:12
@v01d - i cant use vector as number of elements can be more than 20 lakhs.. — Shrik, Nov 29 '11 at 09:16
@VladimirJovic i want some logic which will satisfy strict weak ordering.. — Shrik, Nov 29 '11 at 09:18
@BjörnPollex I want to compare ids like if(one->id[0] > two->id[0]) return true;... — Shrik, Nov 29 '11 at 09:19
I think if you have enough memory for array, there is no problem to use vector. I may be wrong just don't understand how the array will exist with this element count and the vector won't? — v01d, Nov 29 '11 at 09:21

score 2 · Answer 1 · edited May 23 '17 at 11:55

Since std::set (and std::map and their multi variants) want strict-weak ordering, you need to provide that ordering through the comparator. Strict-weak ordering demands that

(x < x) == false
(x < y) == !(y < x)
((x < y) && (y < z)) == (x < z)

Which can be complicated to implement for classes with many members (an array is just a collection of members if you so want).

In this question of mine I asked if it was sensible to implement strict-weak ordering through tuple and tie, which make it ridiculously easy:

struct compare
{
    bool operator() (elem const* one, elem const* two )
    {   // take 'tie' either from Boost or recent stdlibs
        return tie(one->id[0], one->id[1], one->id[2]) <
               tie(two->id[0], two->id[1], two->id[2]);
    }
};

Also notice that I take the arguments as pointers-to-const.

Writing custom std::set comparator for object containing array in c++

1 Answers1