How to create a set with my customized comparison in c++

Question

Could someone explain me what is going on in this example here?

They declare the following:

bool fncomp (int lhs, int rhs) {return lhs<rhs;}

And then use as:

bool(*fn_pt)(int,int) = fncomp;
std::set<int,bool(*)(int,int)> sixth (fn_pt)

While the example for the sort method in algorithm library here

can do like this:

bool myfunction (int i,int j) { return (i<j); }
std::sort (myvector.begin()+4, myvector.end(), myfunction);

I also didn't understand the following:

struct classcomp {
    bool operator() (const int& lhs, const int& rhs) const
       {return lhs<rhs;}
};

this keyword operator (not being followed by an operator as in a op. overload)... what is the meaning of it? Any operator applied there will have that behavior? And this const modifier... what is the effect caused by it?

I was trying to make a set of C-style string as follows:

typedef struct 
{
   char grid[7];
} wrap;

bool compare(wrap w1, wrap w2)
{
   return strcmp(w1.grid, w2.grid) == -1;
}
set <wrap, compare> myset;

I thought I could create a set defining my sorting function in a similar as when I call sort from algorithm library... once it didn't compile I went to the documentation and saw this syntax that got me confused... Do I need to declare a pointer to a function as in the first example i pasted here?

Answer 1

struct classcomp {
    bool operator() (const int& lhs, const int& rhs) const
       {return lhs<rhs;}
};

Defines a functor by overloading the function call operator. To use a function you can do:

int main() {
    std::set <wrap, bool (*)(wrap,wrap)> myset(compare);
    return 0;

}

Another alternative is to define the operator as a part of the wrap class:

struct wrap {
    char grid[7];
    bool operator<(const wrap& rhs) const {
        return strcmp(this->grid, rhs.grid) == -1; 
    }
};

int main() {
    wrap a;
    std::set <wrap> myset;
    myset.insert(a);
    return 0;
}

Answer 2

You're almost there... here's a "fixed" version of your code (see it run here at ideone.com):

#include <iostream>
#include <set>
#include <cstring>

using namespace std;

typedef struct 
{
   char grid[7];
} wrap;

bool compare(wrap w1, wrap w2) // more efficient: ...(const wrap& e1, const wrap@ w2)
{
   return strcmp(w1.grid, w2.grid) < 0;
}

set <wrap, bool(*)(wrap, wrap)> myset(compare);

int main() {
    wrap w1 { "abcdef" };
    wrap w2 { "ABCDEF" };
    myset.insert(w1);
    myset.insert(w2);
    std::cout << myset.begin()->grid[0] << '\n';
}

"explain [to] me what is going on in this example"

Well, the crucial line is...

std::set<wrap, bool(*)(wrap, wrap)> myset(compare);

...which uses the second template parameter to specify the type of function that will perform comparisons, then uses the constructor argument to specify the function. The set object will store a pointer to the function, and invoke it when it needs to compare elements.

"the example for the sort method in algorithm library..."

std::sort in algorithm is great for e.g. vectors, which aren't automatically sorted as elements are inserted but can be sorted at any time. std::set though needs to maintain sorted order constantly, as the logic for inserting new elements, finding and erasing existing ones etc. all assumes the existing elements are always sorted. Consequently, you can't apply std::sort() to an existing std::set.

"this keyword operator (not being followed by an operator as in a op. overload)... what is the meaning of it? Any operator applied there will have that behavior? And this const modifier... what is the effect caused by it?

operator()(...) can be invoked on the object using the same notation used to call a function, e.g.:

classcomp my_classcomp;
if (my_classcomp(my_int1, my_int_2))
    std::cout << "<\n";

As you can see, my_classcomp is "called" as if it were a function. The const modifier means that the code above works even if my_classcomp is defined as a const classcomp, because the comparison function does not need to modify any member variables of the classcomp object (if there were any data members).

Answer 3

You almost answered your question:

bool compare(wrap w1, wrap w2)
{
   return strcmp(w1.grid, w2.grid) == -1;
}

struct wrap_comparer
{
    bool operator()(const wrap& _Left, const wrap& _Right) const
    {
        return strcmp(_Left.grid, _Right.grid) == -1;
    }
};

// declares pointer to function
bool(*fn_pt)(wrap,wrap) = compare;
// uses constructor with function pointer argument
std::set<wrap,bool(*)(wrap,wrap)> new_set(fn_pt);
// uses the function directly
std::set<wrap,bool(*)(wrap,wrap)> new_set2(compare);
// uses comparer
std::set<wrap, wrap_comparer> new_set3;

std::sort can use either a function pointer or a function object (http://www.cplusplus.com/reference/algorithm/sort/), as well as std::set constructor.

const modifier after function signature means that function can't modify object state and so can be called on a const object.