Type Functors

D

desktop

I have this class:

class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}


private:
int pp;
};


Now I would like to insert it into a set:

std::set<test, std::less<test> > my_set;
test t1;
my_set.insert(t1);

This does not work (missing a '<' operator) so I add the following to test:


class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}

bool operator <(test const& t) const {

return (*this).getpp() < t.getpp();
}

private:
int pp;
};

Which does not work either.

std::less implements something like:

bool operator() (T const& x, T const& y) const {
return x < y;


}
So I don't quite see why I need to define '<' in 'test' when I supply
std::less<test> to my_set. It seems like double work. What is wrong in
the body of:

test::eek:perator<(test const& t) const
 
A

Alan Johnson

desktop said:
I have this class:

class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}


private:
int pp;
};


Now I would like to insert it into a set:

std::set<test, std::less<test> > my_set;
Click to expand...

std::less<T> is the default for that template parameter. You do not
need to explicitly specify it (though it doesn't hurt). The only time
you'll use the second template parameter is if your type does not
implement operator< or you want an ordering other than that imposed by
operator<. Because you are implementing operator< below you can change
this to just:

test t1;
my_set.insert(t1);

This does not work (missing a '<' operator) so I add the following to test:


class test {
public:
int getpp()
Click to expand...

This function does not change the state of the class. It should be
declared 'const':
int getpp() const
{
return pp;
}

void setpp(int i) {
pp = i;
}

bool operator <(test const& t) const {

return (*this).getpp() < t.getpp();
Click to expand...

Without the above change, you cannot do this. operator< has been
declared const, so you cannot call non-const member functions.
 
D

desktop

Alan said:
std::less<T> is the default for that template parameter. You do not
need to explicitly specify it (though it doesn't hurt). The only time
you'll use the second template parameter is if your type does not
implement operator< or you want an ordering other than that imposed by
operator<.
Click to expand...

The problem seems to occur when I do an insert:

test t1;
my_set.insert(t1);

as long as I don't insert I can make a set with or without specifying
std::less<test> and without implementing the '<' in test.

When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<test> or not.

But I am not sure what to put in the body of '<'. Currently I have:

bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}

but that was just to fill in the body.
 
?

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=

I have this class:

class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}


private:
int pp;
};


Now I would like to insert it into a set:

std::set<test, std::less<test> > my_set;
test t1;
my_set.insert(t1);

This does not work (missing a '<' operator) so I add the following to test:


class test {
public:
int getpp()
{
return pp;
}

void setpp(int i) {
pp = i;
}

bool operator <(test const& t) const {

return (*this).getpp() < t.getpp();
}

private:
int pp;
};

Which does not work either.

std::less implements something like:

bool operator() (T const& x, T const& y) const {
return x < y;


}
So I don't quite see why I need to define '<' in 'test' when I supply
std::less<test> to my_set. It seems like double work.
Click to expand...

By using std::less as the comparator in the set you say that you want
the objects sorted using your < operator, (since std::less will call
your < operator).
 
R

Rolf Magnus

desktop said:
std::less implements something like:

bool operator() (T const& x, T const& y) const {
return x < y;


}
So I don't quite see why I need to define '<' in 'test' when I supply
std::less<test> to my_set. It seems like double work.
Click to expand...

You just provided the reason. std::less uses operator<, so you need to have
an operator< for your class.
What is wrong in the body of:

test::eek:perator<(test const& t) const
Click to expand...

It uses a non-const member function (getpp) on a const object.
 
V

V.R. Marinov

The problem seems to occur when I do an insert:

test t1;
my_set.insert(t1);

as long as I don't insert I can make a set with or without specifying
std::less<test> and without implementing the '<' in test.

When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<test> or not.
Click to expand...

OK. So std::set<> sorts the elements when they are inserted. In order
to sort them it needs
a criteria. The default criteria used by std::sort is the template
function (or functor/function object) called std::less<>. Here is how
std::less<> might look like:

template <class _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x < __y; }
};

So as you can see the std::less<test> uses the < operator.
So *you* need to provide < operator in way possible for std::less to
use it.
But I am not sure what to put in the body of '<'. Currently I have:

bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}

but that was just to fill in the body.
Click to expand...

The thing is that if you decide to std::greater<test> instead of
std::less<test>
you would have to provide a > operator.
Plus you might need to provide some more operators,
so I would suggest you create a separate header
file (e.g. test_op.h) and provide all operators needed.
This is how the < operator might look like
if you decide your class not have friend operators ;)

bool operator<(const test& lhs, const test& rhs)
{
return lhs.get() < rhs.get();
}
 
V

V.R. Marinov

OK. So std::set<> sorts the elements when they are inserted. In order
to sort them it needs
a criteria. The default criteria used by std::sort is the template
function (or functor/function object) called std::less<>. Here is how
std::less<> might look like:
Click to expand...

Sorry it must be "std::set<>" instead of "std::sort()".
 
A

Alan Johnson

desktop said:
The problem seems to occur when I do an insert:

test t1;
my_set.insert(t1);

as long as I don't insert I can make a set with or without specifying
std::less<test> and without implementing the '<' in test.

When doing an insert I must implement the '<' operator in test and it
makes no difference if I specify std::less<test> or not.

But I am not sure what to put in the body of '<'. Currently I have:

bool operator <(test const& t) const {
return (*this).getpp() < t.getpp();
}

but that was just to fill in the body.
Click to expand...

One more, you cannot call a non-const member function from within a
const member function. To implement operator< the way you are trying to
do it, you need to make getpp const.

#include <set>

class test {
public:
int getpp() const
{
return pp;
}

void setpp(int i) {
pp = i;
}

bool operator<(const test & t) const
{
return getpp() < t.getpp();
}

private:
int pp;
};

int main()
{
std::set<test> my_set;
test t1;
my_set.insert(t1);
}
 
D

desktop

V.R. Marinov said:
OK. So std::set<> sorts the elements when they are inserted. In order
to sort them it needs
a criteria. The default criteria used by std::sort is the template
function (or functor/function object) called std::less<>. Here is how
std::less<> might look like:

template <class _Tp>
struct less : public binary_function<_Tp, _Tp, bool>
{
bool
operator()(const _Tp& __x, const _Tp& __y) const
{ return __x < __y; }
};

So as you can see the std::less<test> uses the < operator.
So *you* need to provide < operator in way possible for std::less to
use it.


The thing is that if you decide to std::greater<test> instead of
std::less<test>
you would have to provide a > operator.
Plus you might need to provide some more operators,
so I would suggest you create a separate header
file (e.g. test_op.h) and provide all operators needed.
This is how the < operator might look like
if you decide your class not have friend operators ;)

bool operator<(const test& lhs, const test& rhs)
{
return lhs.get() < rhs.get();
}
Click to expand...


I get an error that the operator must take exactly one argument. But I
still don't understand how each of my test objects get a unique key that
the std::less function can use to insert the object the correct place.
 
V

V.R. Marinov

I get an error that the operator must take exactly one argument.
Click to expand...

If you decide that your operator should be a member
function of the test class, you don't need the second argument.
Because every member function gets as a first ("hidden")
argument a pointer to the current object AKA *this.
So all you need is to specify the second argument only.

struct test{
...
bool operator<(const test& rhs) const
{
return this->pp < rhs.pp;
}
};

OTOH if you decide to use a global function (not a member function of
class test)
You need to point out both arguments. Note that the global function
does not have
access to the private/protected variable pp.

bool operator<(const test& lhs, const test& rhs)
{
return lhs.getpp() < rhs.getpp();
}
But I
still don't understand how each of my test objects get a unique key that
the std::less function can use to insert the object the correct place.
Click to expand...

This is implementation specific.
 
?

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=

I get an error that the operator must take exactly one argument. But I
still don't understand how each of my test objects get a unique key that
the std::less function can use to insert the object the correct place.
Click to expand...

There is no unique key, the tree does not need any key. All the tree/
algorithm is concerned with is nodes and in connecting them in a
specific order, this order is determined by comparing the value of each
node with the value of all the other nodes. and This is where the <
operator comes in, it compares a value with another and tells the tree
if it is greater or less than the other, and from that information a
decision is made of where to place the node.

This is why you can store anything in a set/map since the container does
not care what it is, just it's relation (as defined by a comparison
operation) to the other stuff you put in. From this we can see that the
difference between a set and a map is quite small, the only difference
is that in a map you insert a key-value pair and perform all comparisons
on the key, whereas in the set you insert only the value and perform all
the comparisons on that (you can think of it as a map with a key-key pair).
 
V

V.R. Marinov

But I
still don't understand how each of my test objects get a unique key that
the std::less function can use to insert the object the correct place.
Click to expand...


There is no unique key, the tree does not need any key. All the tree/
algorithm is concerned with is nodes and in connecting them in a
specific order, this order is determined by comparing the value of each
node with the value of all the other nodes. and This is where the <
operator comes in, it compares a value with another and tells the tree
if it is greater or less than the other, and from that information a
decision is made of where to place the node.
Click to expand...

And there is that thing called Strict Weak Ordering that allows the
algorithm to check if the key that's to be inserted is unique.
So you don't need to provide the '==' operator. Given
Strict weak ordering is enforced the equality of two operands can
be proven like that:


if (!(a<b || b<a))
// a==b
 
D

desktop

Erik said:
There is no unique key, the tree does not need any key. All the tree/
algorithm is concerned with is nodes and in connecting them in a
specific order, this order is determined by comparing the value of each
node with the value of all the other nodes. and This is where the <
operator comes in, it compares a value with another and tells the tree
if it is greater or less than the other, and from that information a
decision is made of where to place the node.
Click to expand...

I have implemented insert as described in Cormen section 13:


my_red_black_tree::insert(value_type const& e) {

....
....

if (e == value[x]) {
return std::make_pair(x, false);
}


if (e < value[x]) {
x = left[x];
}
else {
x = right[x];
}
....
....
}

Which does a lot of comparisons based on the key 'e' (have only shown a
fragment of the code). Since set does only support unique keys it
returns if 'e' is already in the tree.

It all works fine if I only use integers. But if I try to insert my
'test' objects I somehow need to extract an int key and use that as 'e'
to do the comparison.

I know this is not correct and that insert should somehow use std::less
instead and each time a '<' appears in the code call this operator in
the 'test' object. But I have some difficulty seeing how it actually works.

Another thing besides from '<' it also seems that '==' should be defined.
 
D

desktop

V.R. Marinov said:
If you decide that your operator should be a member
function of the test class, you don't need the second argument.
Because every member function gets as a first ("hidden")
argument a pointer to the current object AKA *this.
So all you need is to specify the second argument only.

struct test{
...
bool operator<(const test& rhs) const
{
return this->pp < rhs.pp;
}
};

OTOH if you decide to use a global function (not a member function of
class test)
You need to point out both arguments. Note that the global function
does not have
access to the private/protected variable pp.

bool operator<(const test& lhs, const test& rhs)
{
return lhs.getpp() < rhs.getpp();
}


This is implementation specific.
Click to expand...

But I am doing the implementation from scratch so this is what I am
trying to figure out. In set no duplicate keys are allowed. So each time
I make an 'test' object that I would like to insert in the tree I would
like to generate an unique key for each test object.

I have also considered to make the comparison between 2 objects instead
of a number in the object like:

test t1;
test t2;

t1 < t2;

where '<' is defined like

bool operator<(const test& t) const
{
return (*this) < t;
}

then I just compare the pointers to t and this, since no two pointers
can be identical to 2 different objects this should also work.
 
C

Charles Bailey

test t1;
test t2;

t1 < t2;

where '<' is defined like

bool operator<(const test& t) const
{
return (*this) < t;
}

then I just compare the pointers to t and this, since no two pointers
can be identical to 2 different objects this should also work.
Click to expand...

Assuming this is "bool test::eek:perator<(const test& t) const" then this
function looks very recursive.

If you mean:
bool test::eek:perator<(const test& t) const
{
return this < &t;
}

Even if this did not, in general, cause undefined behaviour it would
still noe work, as code like this fragment should not assert as t1 and
t2 should have the same value:

test t1;
test t2(t1);

assert(!(t1 < t2));
assert(!(t2 < t1));
 
?

=?ISO-8859-1?Q?Erik_Wikstr=F6m?=

Erik said:
There is no unique key, the tree does not need any key. All the tree/
algorithm is concerned with is nodes and in connecting them in a
specific order, this order is determined by comparing the value of each
node with the value of all the other nodes. and This is where the <
operator comes in, it compares a value with another and tells the tree
if it is greater or less than the other, and from that information a
decision is made of where to place the node.
Click to expand...

I have implemented insert as described in Cormen section 13:


my_red_black_tree::insert(value_type const& e) {

...
...

if (e == value[x]) {
return std::make_pair(x, false);
}


if (e < value[x]) {
x = left[x];
}
else {
x = right[x];
}
...
...
}

Which does a lot of comparisons based on the key 'e' (have only shown a
fragment of the code). Since set does only support unique keys it
returns if 'e' is already in the tree.

It all works fine if I only use integers. But if I try to insert my
'test' objects I somehow need to extract an int key and use that as 'e'
to do the comparison.
Click to expand...

Do you understand how templates work? If not you need to read up on that
before you can get any further. I don't know how Cormen did but if you
are lucky you should be able to just replace any mentioning of int with
T and it should work. If I were you I would consider trying to create a
simpler generic container first (like a vector) since you then don't
have to bother with the Red-Black tree problem along with the problem of
creating a generic container.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Problems with std::less 3
Functors 2
Custom matrix multiplication produces different results to glm 0
Lexical Analysis on C++ 1
Chatbot 0
Whether to choose an overload of template function or a partialspecialization of a functor(function 0
A simpler Pimpl Idiom ? 6
Need help in debugging tic tac toe (beginner) 2

Members online

No members online now.
Total: 87 (members: 1, guests: 86)
Robots: 459

Forum statistics

Threads
473,995
Messages
2,570,230
Members
46,819
Latest member
masterdaster

Latest Threads

Top